A CM construction for curves of genus 2 with \(p\)-rank 1. (English) Zbl 1218.11060
Let \(p\) be a prime number and \(k=\mathbb{F}_{p^2}\) the finite field of \(p^2\) elements. The paper contains algorithms to construct genus two curves over \(k\) whose Jacobian \(J\) has \(p\)-rank one, the group \(J(k)\) has a subgroup of prescribed prime order \(r\), and the embedding degree of \(J\) with respect to \(r\) is also prescribed. Similar constructions were known for the ordinary and supersingular Jacobians, but for the \(p\)-rank one case no such construction existed yet.
The crucial ingredient of the algorithms is an accurate analysis of the arithmetic properties of Weil numbers of \(p\)-rank one simple abelian surfaces over \(k\), and the non-Galois CM quartic fields generated by them. Once the right Weil numbers are constructed, the curves are obtained by standard variants of the CM method. The \(p\)-rank one Weil numbers lead to specific problems concerning class polynomials that are dealt with in the paper as well. The algorithms allow the construction of curves with parameters in the range of cryptographic applications in a few seconds on a standard PC.
The crucial ingredient of the algorithms is an accurate analysis of the arithmetic properties of Weil numbers of \(p\)-rank one simple abelian surfaces over \(k\), and the non-Galois CM quartic fields generated by them. Once the right Weil numbers are constructed, the curves are obtained by standard variants of the CM method. The \(p\)-rank one Weil numbers lead to specific problems concerning class polynomials that are dealt with in the paper as well. The algorithms allow the construction of curves with parameters in the range of cryptographic applications in a few seconds on a standard PC.
Reviewer: Enric Nart Viñals (Barcelona)
MSC:
| 11G10 | Abelian varieties of dimension \(> 1\) |
| 11G20 | Curves over finite and local fields |
| 11T71 | Algebraic coding theory; cryptography (number-theoretic aspects) |
| 94A60 | Cryptography |
References:
| [1] | Atkin, A. O.L.; Morain, F., Elliptic curves and primality proving, Math. Comp., 61, 29-68 (1993) · Zbl 0792.11056 |
| [2] | Cohen, H., A Course in Computational Algebraic Number Theory, Grad. Texts in Math., vol. 138 (1993), Springer-Verlag · Zbl 0786.11071 |
| [3] | Eisentraeger, K.; Lauter, K., A CRT algorithm for constructing genus 2 curves over finite fields, (Arithmetic, Geometry and Coding Theory (AGCT-10), Proceedings of the conference AGCT-10, held in Marseille in September 2005. Arithmetic, Geometry and Coding Theory (AGCT-10), Proceedings of the conference AGCT-10, held in Marseille in September 2005, Séminaires et Congrès, vol. 21 (2009), Société Mathématique de France: Société Mathématique de France Paris), 161-176 · Zbl 1270.11060 |
| [4] | Freeman, D., Constructing pairing-friendly genus 2 curves over prime fields with ordinary Jacobians, (Pairing-Based Cryptography - Pairing 2007. Pairing-Based Cryptography - Pairing 2007, Lecture Notes in Comput. Sci., vol. 4575 (2007), Springer-Verlag: Springer-Verlag Berlin), 152-176 · Zbl 1151.11354 |
| [5] | Freeman, D.; Stevenhagen, P.; Streng, M., Abelian varieties with prescribed embedding degree, (van der Poorten, A. J.; Stein, A., ANTS. ANTS, Lecture Notes in Comput. Sci., vol. 5011 (2008), Springer-Verlag), 60-73 · Zbl 1209.11056 |
| [6] | Frey, G.; Lange, T., Complex multiplication, (Cohen, H.; Frey, G.; Avanzi, R.; Doche, C.; Lange, T.; Nguyen, K.; Vercauteren, F., Handbook of Elliptic and Hyperelliptic Curve Cryptography (2006), Chapman & Hall/CRC), 455-473 · Zbl 1082.94001 |
| [7] | Gaudry, P.; Houtmann, T.; Kohel, D.; Ritzenthaler, C.; Weng, A., The 2-adic CM method for genus 2 curves with application to cryptography, (Advances in Cryptology - ASIACRYPT 2006. Advances in Cryptology - ASIACRYPT 2006, Lecture Notes in Comput. Sci., vol. 4284 (2006), Springer-Verlag: Springer-Verlag Berlin), 114-129 · Zbl 1172.94576 |
| [8] | González, J., On the \(p\)-rank of an abelian variety and its endomorphism algebra, Pub. Math., 42, 1, 119-130 (1998) · Zbl 0941.14015 |
| [9] | Goren, E. Z., On certain reduction problems concerning abelian surfaces, Manuscripta Math., 94, 1, 33-43 (1997) · Zbl 0924.14023 |
| [10] | Hardy, G. H.; Wright, E. M., An Introduction to the Theory of Numbers (1938), Oxford University Press · Zbl 0020.29201 |
| [11] | Hitt, L., On the minimal embedding field, (Pairing-Based Cryptography - Pairing 2007. Pairing-Based Cryptography - Pairing 2007, Lecture Notes in Comput. Sci., vol. 4575 (2007), Springer-Verlag), 294-301 · Zbl 1151.94518 |
| [12] | Honda, T., Isogeny classes of abelian varieties over finite fields, J. Math. Soc. Japan, 20, 83-95 (1968) · Zbl 0203.53302 |
| [13] | Igusa, J.-I., Arithmetic variety of moduli for genus 2, Ann. of Math., 72, 3, 612-649 (1960) · Zbl 0122.39002 |
| [14] | Kohel, D., ECHIDNA databases for elliptic curves and higher dimensional analogues |
| [15] | Maisner, D.; Nart, E., Abelian surfaces over finite fields as Jacobians, Experiment. Math., 11, 3, 321-337 (2002), with an appendix by Everett W. Howe · Zbl 1101.14056 |
| [16] | Mestre, J.-F., Construction de courbes de genre 2 à partir de leurs modules, (Effective Methods in Algebraic Geometry. Effective Methods in Algebraic Geometry, Castiglioncello, 1990. Effective Methods in Algebraic Geometry. Effective Methods in Algebraic Geometry, Castiglioncello, 1990, Progr. Math., vol. 94 (1991), Birkhäuser, Boston: Birkhäuser, Boston Boston, MA), 313-334 · Zbl 0752.14027 |
| [17] | Neukirch, J., Algebraische Zahlentheorie (1992), Springer · Zbl 0747.11001 |
| [18] | Rubin, K.; Silverberg, A., Supersingular abelian varieties in cryptology, (Proceedings of the 22nd Annual International Cryptology Conference on Advances in Cryptology. Proceedings of the 22nd Annual International Cryptology Conference on Advances in Cryptology, Lecture Notes in Comput. Sci., vol. 2442 (2002), Springer-Verlag), 336-353 · Zbl 1026.94540 |
| [19] | Shimura, G., Abelian Varieties with Complex Multiplication and Modular Functions (1961), Princeton University Press: Mathematical Society of Japan, Sections 1-16 essentially appeared before in G. Shimura and Y. Taniyama, Complex Multiplication of Abelian Varieties and Its Applications to Number Theory · Zbl 0112.03502 |
| [20] | Shimura, G.; Taniyama, Y., Complex Multiplication of Abelian Varieties and Its Applications to Number Theory, Publications of the Mathematical Society of Japan, vol. 6 (1961), Mathematical Society of Japan: Mathematical Society of Japan Tokyo · Zbl 0112.03502 |
| [21] | A.-M. Spallek, Kurven vom Geschlecht 2 und ihre Anwendung in Public-Key-Kryptosystemen, PhD thesis, Institut für Experimentelle Mathematik, Universität GH Essen, 1994, http://www.uni-due.de/zahlentheorie/theses_en.shtml; A.-M. Spallek, Kurven vom Geschlecht 2 und ihre Anwendung in Public-Key-Kryptosystemen, PhD thesis, Institut für Experimentelle Mathematik, Universität GH Essen, 1994, http://www.uni-due.de/zahlentheorie/theses_en.shtml · Zbl 0974.11501 |
| [22] | Stevenhagen, P., The arithmetic of number rings, (Buhler, J.; Stevenhagen, P., Surveys in Algorithmic Number Theory (2008), Cambridge University Press) · Zbl 1216.11099 |
| [23] | Streng, M., Computing Igusa class polynomials (2008) · Zbl 1322.11066 |
| [24] | Tate, J., Classes d’isogénie des variétés abéliennes sur un corps fini (d’après T. Honda), Sémin. Bourbaki, 1968/69, 352, 95-110 (1971) · Zbl 0212.25702 |
| [25] | van Wamelen, P., Examples of genus two CM curves defined over the rationals, Math. Comp., 68, 225, 307-320 (1999) · Zbl 0906.14025 |
| [26] | A. Weng, Konstruktion kryptographisch geeigneter Kurven mit komplexer Multiplikation, PhD thesis, Institut für Experimentelle Mathematik, Universität GH Essen, 2001, http://www.iem.uni-due.de/zahlentheorie/preprints/wengthesis.pdf; A. Weng, Konstruktion kryptographisch geeigneter Kurven mit komplexer Multiplikation, PhD thesis, Institut für Experimentelle Mathematik, Universität GH Essen, 2001, http://www.iem.uni-due.de/zahlentheorie/preprints/wengthesis.pdf |
| [27] | Weng, A., Constructing hyperelliptic curves of genus 2 suitable for cryptography, Math. Comp., 72, 241, 435-458 (2003) · Zbl 1013.11023 |
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.
