Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



On the number of isogeny classes of pairing-friendly elliptic curves and statistics of MNT curves

Authors: Jorge Jiménez Urroz, Florian Luca and Igor E. Shparlinski
Journal: Math. Comp. 81 (2012), 1093-1110
MSC (2010): Primary 11G07, 11T71, 14H52
Published electronically: September 29, 2011
MathSciNet review: 2869051
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We give an upper bound on the number of finite fields over which elliptic curves of cryptographic interest with a given embedding degree and small complex multiplication discriminant may exist, and present some heuristic arguments which indicate that this bound is tight. We also refine some heuristic arguments on the total number of so-called MNT curves with prime cardinalities which have been recently presented by various authors.

References [Enhancements On Off] (What's this?)

  • 1. R. Avanzi, H. Cohen, C. Doche, G. Frey, T. Lange, K. Nguyen and F. Vercauteren, Elliptic and hyperelliptic curve cryptography: Theory and practice, CRC Press, 2005.
  • 2. R. Balasubramanian and N. Koblitz, `The improbability that an elliptic curve has subexponential discrete log problem under the Menezes-Okamoto-Vanstone algorithm', J. Cryptology, 11 (1998), 141-145. MR 1620936 (2000f:94024)
  • 3. P. T. Bateman and R. A. Horn, `A heuristic asymptotic formula concerning the distribution of prime numbers', Math. Comp., 16 (1962), 363-367. MR 0148632 (26:6139)
  • 4. I. Blake, G. Seroussi and N. Smart, Elliptic curves in cryptography, London Math. Soc., Lecture Note Series, 265, Cambridge Univ. Press, 1999. MR 1771549 (2001i:94048)
  • 5. I. Blake, G. Seroussi and N. Smart, Advances in elliptic curves in cryptography, London Math. Soc., Lecture Note Series, 317, Cambridge Univ. Press, 2005.
  • 6. D. Boneh and M. Franklin, `Identity-based encryption from the Weil pairing', SIAM J. Comp., 32 (2003), 586-615. MR 2001745 (2004m:94035)
  • 7. D. Boneh, B. Lynn and H. Shacham, `Short signatures from the Weil pairing', J. Cryptology, 17 (2004), 297-319. MR 2090559 (2005h:94040)
  • 8. A. C. Cojocaru and I. E. Shparlinski, `On the embedding degree of reductions of an elliptic curve', Inform. Proc. Letters, 109 (2009), 652-654. MR 2527697 (2010d:11066)
  • 9. K. Ford, `The distribution of integers with a divisor in a given interval', Annals Math., 168 (2008), 367-433. MR 2434882 (2009m:11152)
  • 10. D. Freeman, M. Scott and E. Teske, `A taxonomy of pairing-friendly elliptic curves', J. Cryptology, 23 (2010), 224-280. MR 2578668 (2011a:11112)
  • 11. S. D. Galbraith, J. McKee and P. Valenca, `Ordinary abelian varieties having small embedding degree', Proc. Workshop on Math. Problems and Techniques in Cryptology, CRM, Barcelona, 2005, 29-45.
  • 12. R.  R.  Hall and G.  Tenenebaum, Divisors, Cambridge University Press, Cambridge, 1988. MR 964687 (90a:11107)
  • 13. G. H. Hardy and E. M. Wright, An introduction to the theory of numbers, Oxford Univ. Press, Oxford, 1979. MR 568909 (81i:10002)
  • 14. H. Iwaniec and E. Kowalski, Analytic number theory, Amer. Math. Soc., Providence, RI, 2004. MR 2061214 (2005h:11005)
  • 15. A. Joux, `A one round protocol for tripartite Diffie-Hellman', Lect. Notes in Comp. Sci., vol. 1838, Springer-Verlag, Berlin, 2000, 385-393. MR 1850619 (2002i:14029)
  • 16. A. Joux and K. Nguyen, `Separating decision Diffie-Hellman from computational Diffie-Hellman in cryptographic groups', J. Cryptology, 16 (2000), 239-247. MR 2002044 (2004h:94045)
  • 17. E. J. Kachisa, E. F. Schaefer and M. Scott, `Constructing Brezing-Weng pairing-friendly elliptic curves using elements in the cyclotomic field', Lect. Notes in Comp. Sci., vol. 5209 Springer-Verlag, Berlin, 2008, 126-135.
  • 18. K. Karabina and E. Teske, `On prime-order elliptic curves with embedding degrees $ k = 3$, $ 4$ and $ 6$', Lect. Notes in Comp. Sci., vol. 5011, Springer-Verlag, Berlin, 2008, 102-117. MR 2467839 (2010a:11114)
  • 19. A. Languasco and A. Zaccagnini, `A note on Mertens formula for arithmetic progressions', Number Theory, 127 (2007), 37-46. MR 2351662 (2009g:11136)
  • 20. F. Luca, D. J. Mireles and I. E. Shparlinski, `MOV attack in various subgroups on elliptic curves', Illinois J. Math., 48 (2004), 1041-1052. MR 2114268 (2005h:11126)
  • 21. F. Luca and I. E. Shparlinski, `On the exponent of the group of points on elliptic curves in extension fields', Intern. Math. Research Notices, 2005 (2005), 1391-1409. MR 2152235 (2006h:11072)
  • 22. F. Luca and I. E. Shparlinski, `Elliptic curves with low embedding degree', J. Cryptology, 19 (2006), 553-562. MR 2267556 (2007h:14034)
  • 23. F. Luca and I. E. Shparlinski, `On finite fields for pairing based cryptography', Adv. Math. of Commun., 1 (2007), 281-286. MR 2327047 (2008d:11059)
  • 24. A. Miyaji, M. Nakabayashi and S. Takano, `New explicit conditions of elliptic curve traces for FR-reduction', IEICE Trans. Fundamentals, E84-A (2001), 1234-1243.
  • 25. A. Menezes, T. Okamoto and S. A. Vanstone, `Reducing elliptic curve logarithms to logarithms in a finite field', IEEE Transactions on Information Theory, 39 (1993), 1639-1646. MR 1281712 (95e:94038)
  • 26. R. Sakai, K. Ohgishi and M. Kasahara, `Cryptosystems based on pairing', Proc. Symp.on Cryptography and Inform. Security, SCIS'2000, Okinawa, Japan, 2000.
  • 27. J. H. Silverman, The arithmetic of elliptic curves, Springer-Verlag, Berlin, 1995.
  • 28. A. V. Sutherland, `Computing Hilbert class polynomials with the Chinese Remainder Theorem', Math. Comp, 80 (2011), 501-538. MR 2728992
  • 29. S. Tanaka and K. Nakamula, `Constructing pairing-friendly elliptic curves using factorization of cyclotomic polynomials', Lect. Notes in Comp. Sci., vol. 5209 Springer-Verlag, Berlin, 2008, 136-145.
  • 30. E. Wirsing, `Das asymptotische Verhalten von Summen uber multip- likative Funktionen,' Math. Ann., 143 (1961), 75-102. MR 0131389 (24:A1241)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 11G07, 11T71, 14H52

Retrieve articles in all journals with MSC (2010): 11G07, 11T71, 14H52

Additional Information

Jorge Jiménez Urroz
Affiliation: Departamento de Matemática Aplicada IV, Universidad Politecnica de Catalunya, Barcelona, 08034, España

Florian Luca
Affiliation: Instituto de Matemáticas, Universidad Nacional Autonoma de México, C.P. 58089, Morelia, Michoacán, México

Igor E. Shparlinski
Affiliation: Department of Computing, Macquarie University, Sydney, NSW 2109, Australia

Keywords: Elliptic curves, pairing based cryptography, embedding degree, MNT curves
Received by editor(s): February 23, 2010
Received by editor(s) in revised form: February 11, 2011
Published electronically: September 29, 2011
Article copyright: © Copyright 2011 American Mathematical Society

American Mathematical Society