Point compression for the trace zero subgroup over a small degree extension field. (English) Zbl 1319.14033
The article is devoted to the study of the trace zero variety of an elliptic curve defined over the finite field \(\mathbb{F}_q\) of \(q\) elements. More precisely, a description of the \(\mathbb{F}_q\)-rational points of the trace zero variety of a given elliptic curve is obtained, a new representation of these points is proposed, and an algorithm for compression and decompression is described and analyzed.
Let \(E\) be an elliptic curve defined over \(\mathbb{F}_q\). For a field extension \(\mathbb{F}_q|\mathbb{F}_{q^n}\), denote by \(E(\mathbb{F}_{q^n})\) the group of \(\mathbb{F}_{q^n}\)-rational points of \(E\). The kernel of the trace map \(\varphi:E(\mathbb{F}_{q^n})\to E(\mathbb{F}_q)\) is the trace zero subgroup \(T_n\) of \(E(\mathbb{F}_{q^n})\). By Weil restriction the points of \(T_n\) can be viewed as the \(\mathbb{F}_q\)-rational points of an abelian variety \(V\) of dimension \(n-1\) defined over \(\mathbb{F}_q\), which is called the trace zero variety.
In the paper under review, a new representation for the elements of \(T_n\) is discussed. Choosing a basis of \(\mathbb{F}_{q^n}\) as \(\mathbb{F}_q\)-vector space, a point \(P\in T_n\) is represented by its first \(n-1\) coordinates \((X_0,\dots,X_{n-2})\in\mathbb{F}_q^{n-1}\) in this basis, together with an equation in \(\mathbb{F}_q[x_0,\dots,x_{n-1}]\) which vanishes on the coordinates of any \(P\in T_n\), where \(x_0,\dots,x_{n-1}\) are indeterminates over \(\mathbb{F}_q\). This representation, although not injective, identifies a small number of points, and is of optimal size.
In order to obtain the equation for the representation of the elements of \(T_n\), the authors rely on the Semaev summation polynomials [I. Semaev, “Summation polynomials and the discrete logarithm problem on elliptic curves”, preprint, http://eprint.iacr.org/2004/031.pdf (2004)]. These polynomials provide conditions on the \(x\)-coordinates of a finite number of points on an elliptic curve summing to \(\mathcal{O}\). The authors consider such polynomials applied to the Frobenius conjugates of any point \(P\in T_n\). Further, taking into account that each Semaev summation polynomial is a symmetric element of \(\mathbb{F}_q[x_0,\dots,x_{n-1}]\), it is expressed in terms of the elementary symmetric polynomials \(\mathbb{F}_q[z_1,\dots,z_n]\). As a consequence, a compression of the representation of the points of \(T_n\) is obtained by computing the elementary symmetric polynomials in the \(x\)–coordinates of the Frobenius conjugates of a given \(P\in T_n\). The decompression is obtained by using the “symmetrized” version of the corresponding Semaev summation polynomial.
Finally, explicit equations are given for extensions of degree 3 and 5, and the cost of compression and decompression is analyzed.
Let \(E\) be an elliptic curve defined over \(\mathbb{F}_q\). For a field extension \(\mathbb{F}_q|\mathbb{F}_{q^n}\), denote by \(E(\mathbb{F}_{q^n})\) the group of \(\mathbb{F}_{q^n}\)-rational points of \(E\). The kernel of the trace map \(\varphi:E(\mathbb{F}_{q^n})\to E(\mathbb{F}_q)\) is the trace zero subgroup \(T_n\) of \(E(\mathbb{F}_{q^n})\). By Weil restriction the points of \(T_n\) can be viewed as the \(\mathbb{F}_q\)-rational points of an abelian variety \(V\) of dimension \(n-1\) defined over \(\mathbb{F}_q\), which is called the trace zero variety.
In the paper under review, a new representation for the elements of \(T_n\) is discussed. Choosing a basis of \(\mathbb{F}_{q^n}\) as \(\mathbb{F}_q\)-vector space, a point \(P\in T_n\) is represented by its first \(n-1\) coordinates \((X_0,\dots,X_{n-2})\in\mathbb{F}_q^{n-1}\) in this basis, together with an equation in \(\mathbb{F}_q[x_0,\dots,x_{n-1}]\) which vanishes on the coordinates of any \(P\in T_n\), where \(x_0,\dots,x_{n-1}\) are indeterminates over \(\mathbb{F}_q\). This representation, although not injective, identifies a small number of points, and is of optimal size.
In order to obtain the equation for the representation of the elements of \(T_n\), the authors rely on the Semaev summation polynomials [I. Semaev, “Summation polynomials and the discrete logarithm problem on elliptic curves”, preprint, http://eprint.iacr.org/2004/031.pdf (2004)]. These polynomials provide conditions on the \(x\)-coordinates of a finite number of points on an elliptic curve summing to \(\mathcal{O}\). The authors consider such polynomials applied to the Frobenius conjugates of any point \(P\in T_n\). Further, taking into account that each Semaev summation polynomial is a symmetric element of \(\mathbb{F}_q[x_0,\dots,x_{n-1}]\), it is expressed in terms of the elementary symmetric polynomials \(\mathbb{F}_q[z_1,\dots,z_n]\). As a consequence, a compression of the representation of the points of \(T_n\) is obtained by computing the elementary symmetric polynomials in the \(x\)–coordinates of the Frobenius conjugates of a given \(P\in T_n\). The decompression is obtained by using the “symmetrized” version of the corresponding Semaev summation polynomial.
Finally, explicit equations are given for extensions of degree 3 and 5, and the cost of compression and decompression is analyzed.
Reviewer: Guillermo Matera (Buenos Aires)
MSC:
| 14G50 | Applications to coding theory and cryptography of arithmetic geometry |
| 11G25 | Varieties over finite and local fields |
| 14H52 | Elliptic curves |
| 11T71 | Algebraic coding theory; cryptography (number-theoretic aspects) |
Keywords:
elliptic curves; trace zero variety; point compression; summation polynomials; discrete logarithm problem, elliptic curve cryptographySoftware:
MagmaReferences:
| [1] | Avanzi R.M., Cesena E.: Trace zero varieties over fields of characteristic 2 for cryptographic applications. In: Proceedings of the First Symposium on Algebraic Geometry and Its Applications (SAGA ’07), pp. 188-215 (2007). · Zbl 1151.14308 |
| [2] | Barbulescu R., Bouvier C., Detrey J., Gaudry P., Jeljeli H., Thomé E., Videau M., Zimmermann P.: Discrete logarithm in GF \[(2^{809}2809)\] with FFS. http://hal.inria.fr/hal-00818124/. · Zbl 1335.94029 |
| [3] | Barbulescu R., Gaudry P., Joux A., Thomé E.: A quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic. http://arxiv.org/abs/1306.4244 (2013). · Zbl 1326.11080 |
| [4] | Bernstein D.J., Duif N., Lange T., Schwabe P., Yang B.Y.: High-speed high-security signatures. J. Cryptogr. Eng. 2(2), 77-89 (2012). · Zbl 1321.94039 |
| [5] | Blady G.: Die Weil-Restriktion elliptischer Kurven in der Kryptographie. Master’s thesis, Univerität GHS Essen, Dresden (2002). |
| [6] | Bos J.W., Costello C., Hisil H., Lauter K.: High-performance scalar multiplication using 8-dimensional GLV/GLS decomposition. http://eprint.iacr.org/2013/146 (2013). |
| [7] | Bosma W., Cannon J., Playoust C.: The Magma algebra system. I. The user language. J. Symb. Comput. 24, 235-265 (1997). · Zbl 0898.68039 |
| [8] | Cesena E.: Trace zero varieties in pairing-based cryptography. Ph.D. thesis, Università degli studi Roma Tre, Roma. http://ricerca.mat.uniroma3.it/dottorato/Tesi/tesicesena.pdf (2010). |
| [9] | Diem C.: The GHS attack in odd characteristic. Ramanujan Math. Soc. 18(1), 1-32 (2003). · Zbl 1041.94010 |
| [10] | Diem C.: An index calculus algorithm for plane curves of small degree. In: Hess F., Pauli S., Pohst M. (eds.) Algorithmic Number Theory (ANTS VII), LNCS, vol. 4076, pp. 543-557. Springer, Berlin (2006). · Zbl 1143.11361 |
| [11] | Diem C., Kochinke S.: Computing discrete logarithms with special linear systems. http://www.math.uni-leipzig.de/diem/preprints/dlp-linear-systems.pdf (2013). |
| [12] | Diem C., Scholten J.: An attack on a trace-zero cryptosystem. http://www.math.uni-leipzig.de/diem/preprints. |
| [13] | Eagle P.N.J., Galbraith S.D., Ong J.: Point compression for Koblitz curves. Adv. Math. Commun. 5(1), 1-10 (2011). · Zbl 1213.94099 |
| [14] | Faz-Hernández A., Longa P., Sánchez A.H.: Efficient and secure algorithms for GLV-based scalar multiplication and their implementation on GLV-GLS curves. http://eprint.iacr.org/2013/158 (2013). · Zbl 1294.94045 |
| [15] | Frey G.: Applications of arithmetical geometry to cryptographic constructions. In: Proceedings of the 5th International Conference on Finite Fields and Applications, pp. 128-161. Springer, Berlin (1999). · Zbl 1015.94545 |
| [16] | Galbraith S.D., Lin X.: Computing pairings using \[x\] x-coordinates only. Des. Codes Crytogr. 50(3), 305-324 (2009). · Zbl 1222.14051 |
| [17] | Galbraith S.D., Lin X., Scott M.: Endomorphisms for faster elliptic curve cryptography on a large class of curves. J. Cryptol. 24(3), 446-469 (2011). · Zbl 1258.94036 |
| [18] | Galbraith S.D., Smith B.A.: Discrete logarithms in generalized Jacobians. http://uk.arxiv.org/abs/math.NT/0610073 (2006). |
| [19] | Gallant R.P., Lambert R.J., Vanstone S.A.: Faster point multiplication on elliptic curves with efficient endomorphisms. In: Kilian J. (ed.) Advances in Cryptology: Proceedings of CRYPTO ’01. LNCS, vol. 2139, pp. 190-200. Springer, Berlin (2001). · Zbl 1002.94022 |
| [20] | Gaudry P.: Index calculus for abelian varieties of small dimension and the elliptic curve discrete logarithm problem. J. Symb. Comput. 44(12), 1690-1702 (2009). · Zbl 1177.94148 |
| [21] | Gaudry P., Hess F., Smart N.: Constructive and destructive facets of Weil descent. J. Cryptol. 15(1), 19-46 (2002). · Zbl 0996.94036 |
| [22] | Gerhard J., von zur Gathen J.: Modern Computer Algebra. Cambridge University Press, Cambridge (1999). · Zbl 0936.11069 |
| [23] | Göloğlu F., Granger R., McGuire G., Zumbrägel J.: On the function field sieve and the impact of higher splitting probabilities: application to discrete logarithms in \[{\mathbb{F}}_{2^{1971}}\] F21971. http://eprint.iacr.org/2013/074 (2013). · Zbl 1316.11114 |
| [24] | Göloğlu F., Granger R., McGuire, G., Zumbrägel J.: Solving a 6120-bit DLP on a desktop computer. http://eprint.iacr.org/2013/306 (2013). · Zbl 1321.11125 |
| [25] | Gong G., Harn L.: Public-key cryptosystems based on cubic finite field extensions. IEEE Trans. Inf. Theory 45(7), 2601-2605 (1999). · Zbl 0986.94027 |
| [26] | Gorla E.: Torus-based cryptography. In: Jajodia S., Tilborg H. (eds.) Encyclopedia of Cryptography, 2nd edn., pp. 1306-1308. Springer, Berlin (2011). |
| [27] | Granger R., Vercauteren F.: On the discrete logarithm problem on algebraic tori. In: Shoup V. (ed.) Advances in Cryptology: Proceedings of CRYPTO ’05. LNCS, vol. 3621, pp. 66-85. Springer, Berlin (2005). · Zbl 1145.94442 |
| [28] | Joux A.: A new index calculus algorithm with complexity \[{L}(1/4 + o(1))\] L(1/4+o(1)) in very small characteristic. http://eprint.iacr.org/2013/095 (2013). · Zbl 1362.94034 |
| [29] | Joux A., Vitse V.: Elliptic curve discrete logarithm problem over small degree extension fields. Application to the static Diffie-Hellman problem on \[{E}(\mathbb{F}_{q^5})\] E(Fq5). J. Cryptol. doi:10.1007/s00145-011-9116-z (2012). · Zbl 1291.94107 |
| [30] | Koblitz N.: CM-curves with good cryptographic properties. In: Feigenbaum J. (ed.) Advances in Cryptology: Proceedings of CRYPTO ’91. LNCS, vol. 576, pp. 179-287. Springer, Berlin (1991). · Zbl 0780.14018 |
| [31] | Lange T.: Efficient arithmetic on hyperelliptic curves. Ph.D. thesis, University of Essen, Essen (2001). · Zbl 1047.94008 |
| [32] | Lange T.: Trace zero subvarieties of genus 2 curves for cryptosystem. Ramanujan Math. Soc. 19(1), 15-33 (2004). · Zbl 1109.94003 |
| [33] | Lenstra A.K., Verheul E.R.: The XTR public key system. In: Bellare M. (ed.) Advances in Cryptology: Proceedings of CRYPTO ’00. LNCS, vol. 1880, pp. 1-19. Springer, Berlin (2000). · Zbl 0995.94538 |
| [34] | Longa P., Sica F.: Four-dimensional Gallant-Lambert-Vanstone scalar multiplication. In: Wang X., Sako K. (eds.) Advances in Cryptology: Proceedings of ASIACRYPT ’12. LNCS, vol. 7658, pp. 718-739. Springer, Berlin (2012). · Zbl 1292.94107 |
| [35] | Naumann N.: Weil-Restriktion abelscher Varietäten. Master’s thesis, Univerität GHS Essen, Dresden. http://web.iem.uni-due.de/ag/numbertheory/dissertationen (1999). |
| [36] | Oliveira T., López J., Aranha D.F., Rodríguez-Henríquez F.: Lambda coordinates for binary elliptic curves. http://eprint.iacr.org/2013/131 (2013). · Zbl 1366.94523 |
| [37] | Rubin K., Silverberg A.: Supersingular abelian varieties in cryptology. In: Yung M. (ed.) Advances in Cryptology: Proceedings of CRYPTO ’02. LNCS, vol. 2442, pp. 336-353. Springer, Berlin (2002). · Zbl 1026.94540 |
| [38] | Rubin K., Silverberg A.: Torus-based cryptography. In: Boneh D. (ed.) Advances in Cryptology: Proceedings of CRYPTO ’03. LNCS, vol. 2729, pp. 349-365. Springer, Berlin (2003). · Zbl 1122.94400 |
| [39] | Rubin K., Silverberg A.: Using primitive subgroups to do more with fewer bits. In: Buell D. (ed.) Algorithmic Number Theory (ANTS VI). LNCS, vol. 3076, pp. 18-41. Springer, Berlin (2004). · Zbl 1125.94328 |
| [40] | Rubin K., Silverberg A.: Using abelian varieties to improve pairing-based cryptography. J. Cryptol. 22(3), 330-364 (2009). · Zbl 1170.94013 |
| [41] | Semaev I.: Summation polynomials of the discrete logarithm problem on elliptic curves. http://eprint.iacr.org/2004/031 (2004). |
| [42] | Silverberg A.: Compression for trace zero subgroups of elliptic curves. Trends Math. 8, 93-100 (2005). |
| [43] | Smith P., Skinner C.: A public-key cryptosystem and a digital signature system based on the Lucas function analogue to discrete logarithms. In: Pieprzyk J., Safavi-Naini R. (eds.) Advances in Cryptology: Proceedings of ASIACRYPT ’94. LNCS, vol. 917, pp. 357-364. Springer, Berlin (1995). · Zbl 0872.94041 |
| [44] | Weimerskirch A.: The application of the Mordell-Weil group to cryptographic systems. Master’s thesis, Worcester Polytechnic Institute, Worcester. http://www.emsec.rub.de/media/crypto/attachments/files/2010/04/ms_weika.pdf (2001). |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
