×

On the efficient generation of prime-order elliptic curves. (English) Zbl 1195.94063

Summary: We consider the generation of prime-order elliptic curves (ECs) over a prime field \(\mathbb{F}_{p}\) using the Complex Multiplication (CM) method. A crucial step of this method is to compute the roots of a special type of class field polynomials with the most commonly used being the Hilbert and Weber ones. These polynomials are uniquely determined by the CM discriminant \(D\). In this paper, we consider a variant of the CM method for constructing elliptic curves (ECs) of prime order using Weber polynomials. In attempting to construct prime-order ECs using Weber polynomials, two difficulties arise (in addition to the necessary transformations of the roots of such polynomials to those of their Hilbert counterparts). The first one is that the requirement of prime order necessitates that \(D\equiv 3 \, (\text{mod} \,8)\), which gives Weber polynomials with degree three times larger than the degree of their corresponding Hilbert polynomials (a fact that could affect efficiency). The second difficulty is that these Weber polynomials do not have roots in \(\mathbb{F}_{p}\) .
In this work, we show how to overcome the above difficulties and provide efficient methods for generating ECs of prime order focusing on their support by a thorough experimental study. In particular, we show that such Weber polynomials have roots in the extension field \(\mathbb{F}_{p^{3}}\) and present a set of transformations for mapping roots of Weber polynomials in \(\mathbb{F}_{p^{3}}\) to roots of their corresponding Hilbert polynomials in \(\mathbb{F}_{p}\) . We also show how an alternative class of polynomials, with degree equal to their corresponding Hilbert counterparts (and hence having roots in \(\mathbb{F}_{p}\) ), can be used in the CM method to generate prime-order ECs. We conduct an extensive experimental study comparing the efficiency of using this alternative class against the use of the aforementioned Weber polynomials. Finally, we investigate the time efficiency of the CM variant under four different implementations of a crucial step of the variant and demonstrate the superiority of two of them.

MSC:

94A60 Cryptography
11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
14H52 Elliptic curves

Software:

ECPP; gmp; LiDIA
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Atkin, A. O.L.; Morain, F., Elliptic curves and primality proving, Math. Comput., 61, 29-67 (1993) · Zbl 0792.11056 · doi:10.2307/2152935
[2] Baier, H., Elliptic curves of prime order over optimal extension fields for use in cryptography, Progress in Cryptology—INDOCRYPT 2001, 99-107 (2001), Berlin: Springer, Berlin · Zbl 1011.94553
[3] H. Baier, Efficient algorithms for generating elliptic curves over finite fields suitable for use in cryptography. PhD Thesis, Dept. of Computer Science, Technical Univ. of Darmstadt, May 2002
[4] Baier, H.; Buchmann, J., Efficient construction of cryptographically strong elliptic curves, Progress in Cryptology—INDOCRYPT 2000, 191-202 (2000), Berlin: Springer, Berlin · Zbl 0974.11043
[5] Berlekamp, E. R., Factoring polynomials over large finite fields, Math. Comput., 24, 713-735 (1970) · Zbl 0247.12014 · doi:10.2307/2004849
[6] Blake, I.; Seroussi, G.; Smart, N., Elliptic Curves in Cryptography (1999), Cambridge: Cambridge University Press, Cambridge · Zbl 0937.94008
[7] Boneh, D.; Lynn, B.; Shacham, H., Short signatures from the Weil pairing, ASIACRYPT 2001, 514-532 (2001), Berlin: Springer, Berlin · Zbl 1064.94554
[8] Cohen, H., A Course in Computational Algebraic Number Theory (1993), Berlin: Springer, Berlin · Zbl 0786.11071
[9] Cornacchia, G., Su di un metodo per la risoluzione in numeri interi dell’ equazione ∑_h=0^nC_hx^n−hy^h=P, G. Mat. Battaglini, 46, 33-90 (1908) · JFM 39.0258.02
[10] Cox, D. A., Primes of the Form x^2+ny^2 (1989), New York: Wiley, New York · Zbl 0701.11001
[11] Enge, A.; Morain, F., Comparing invariants for class fields of imaginary quadratic fields, Algebraic Number Theory—ANTS V, 252-266 (2002), Berlin: Springer, Berlin · Zbl 1058.11077
[12] A. Enge, R. Schertz, Constructing elliptic curves from modular curves of positive genus. Preprint (2003) · Zbl 1158.11322
[13] Enge, A.; Schertz, R., Modular curves of composite level, Acta Arith., 118, 2, 129-141 (2005) · Zbl 1158.11322 · doi:10.4064/aa118-2-3
[14] Frey, G.; Rück, H. G., A remark concerning m-divisibility and the discrete logarithm problem in the divisor class group of curves, Math. Comput., 62, 865-874 (1994) · Zbl 0813.14045 · doi:10.2307/2153546
[15] Galbraith, S.; McKee, J., The probability that the number of points on an elliptic curve over a finite field is prime, J. Lond. Math. Soc., 62, 3, 671-684 (2000) · Zbl 1010.11033 · doi:10.1112/S0024610700001502
[16] GNU multiple precision library, edition 3.1.1, September 2000. Available at: http://www.swox.com/gmp
[17] IEEE P1363/D13, Standard Specifications for Public-Key Cryptography, 1999. http://grouper.ieee.org/groups/1363/tradPK/draft.html
[18] E. Kaltofen, N. Yui, Explicit construction of the Hilbert class fields of imaginary quadratic fields by integer lattice reduction. Research Report 89-13, Rensselaer Polytechnic Institute, May 1989 · Zbl 0737.11034
[19] E. Kaltofen, T. Valente, N. Yui, An improved Las Vegas primality test, in Proc. ACM-SIGSAM 1989 International Symposium on Symbolic and Algebraic Computation (1989), pp. 26-33
[20] Konstantinou, E.; Stamatiou, Y.; Zaroliagis, C., A software library for elliptic curve cryptography, Proc. 10th European Symposium on Algorithms—ESA 2002 (Engineering and Applications Track), 625-637 (2002), Berlin: Springer, Berlin · Zbl 1019.94500
[21] Konstantinou, E.; Stamatiou, Y.; Zaroliagis, C., On the efficient generation of elliptic curves over prime fields, Cryptographic Hardware and Embedded Systems—CHES 2002, 333-348 (2002), Berlin: Springer, Berlin · Zbl 1028.94507
[22] Konstantinou, E.; Stamatiou, Y. C.; Zaroliagis, C., On the construction of prime order elliptic curves, Progress in Cryptology—INDOCRYPT 2003, 309-322 (2003), Berlin: Springer, Berlin · Zbl 1123.14300
[23] Konstantinou, E.; Kontogeorgis, A.; Stamatiou, Y.; Zaroliagis, C., Generating prime order elliptic curves: difficulties and efficiency considerations, International Conference on Information Security and Cryptology—ICISC 2004, 261-278 (2005), Berlin: Springer, Berlin · Zbl 1133.94325
[24] Lay, G. J.; Zimmer, H., Constructing elliptic curves with given group order over large finite fields, Algorithmic Number Theory—ANTS-I, 250-263 (1994), Berlin: Springer, Berlin · Zbl 0833.11024
[25] LiDIA. A library for computational number theory. Technical University of Darmstadt. Available from http://www.informatik.tu-darmstadt.de/TI/LiDIA/Welcome.html
[26] Menezes, A. J.; Okamoto, T.; Vanstone, S. A., Reducing elliptic curve logarithms to a finite field, IEEE Trans. Inf. Theory, 39, 1639-1646 (1993) · Zbl 0801.94011 · doi:10.1109/18.259647
[27] Miyaji, A.; Nakabayashi, M.; Takano, S., Characterization of elliptic curve traces under FR-reduction, International Conference on Information Security and Cryptology—ICISC 2000, 90-108 (2001), Berlin: Springer, Berlin · Zbl 0990.94024
[28] Miyaji, A.; Nakabayashi, M.; Takano, S., New explicit conditions of elliptic curve traces for FR-reduction, IEICE Trans. Fundam., E84-A, 5, 1234-1243 (2001)
[29] F. Morain, Modular curves and class invariants. Preprint, June 2000
[30] F. Morain, Computing the cardinality of CM elliptic curves using torsion points. Preprint, October 2002 · Zbl 1196.11085
[31] Y. Nogami, Y. Morikawa, Fast generation of elliptic curves with prime order over \(F_{p^{2^c}}\!\) , in Proc. of the International workshop on Coding and Cryptography, March 2003
[32] Pohlig, G. C.; Hellman, M. E., An improved algorithm for computing logarithms over GF(p) and its cryptographic significance, IEEE Trans. Inf. Theory, 24, 106-110 (1978) · Zbl 0375.68023 · doi:10.1109/TIT.1978.1055817
[33] Satoh, T.; Araki, K., Fermat quotients and the polynomial time discrete log algorithm for anomalous elliptic curves, Comment. Math. Univ. St. Pauli, 47, 81-91 (1998) · Zbl 1044.11591
[34] Savaş, E.; Schmidt, T. A.; Koç, Ç. K., Generating elliptic curves of prime order, Cryptographic Hardware and Embedded Systems—CHES 2001, 145-161 (2001), Berlin: Springer, Berlin
[35] Schertz, R., Weber’s class invariants revisited, J. Théor. Nr. Bordx., 4, 325-343 (2002) · Zbl 1022.11056
[36] Schoof, R., Counting points on elliptic curves over finite fields, J. Théor. Nr. Bordx., 7, 219-254 (1995) · Zbl 0852.11073
[37] M. Scott, P.S.L.M. Barreto, Generating more MNT elliptic curves, Cryptology ePrint Archive, Report 2004/058 (2004) · Zbl 1172.14309
[38] Silverman, J. H., The Arithmetic of Elliptic Curves (1986), Berlin: Springer, Berlin · Zbl 0585.14026
[39] Stewart, I., Galois Theory (2004), Boca Raton: Chapman & Hall/CRC, Boca Raton · Zbl 1049.12001
[40] Stewart, I.; Tall, D., Algebraic Number Theory (1987), London: Chapman & Hall, London · Zbl 0663.12001
[41] T. Valente, A distributed approach to proving large numbers prime. Rensselaer Polytechnic Institute Troy, New York, PhD Thesis, August 1992
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.