Mathematics of Computation

			Journals Home Search Author Info Subscribe Tech Support My Subscriptions Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

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
Posted: September 29, 2011
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

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 Neal Koblitz, The improbability that an elliptic curve has subexponential discrete log problem under the Menezes-Okamoto-Vanstone algorithm, J. Cryptology 11 (1998), no. 2, 141–145. MR 1620936 (2000f:94024), http://dx.doi.org/10.1007/s001459900040
3. Paul T. Bateman and Roger A. Horn, A heuristic asymptotic formula concerning the distribution of prime numbers, Math. Comp. 16 (1962), 363–367. MR 0148632 (26 #6139)
4. I. F. Blake, G. Seroussi, and N. P. Smart, Elliptic curves in cryptography, London Mathematical Society Lecture Note Series, vol. 265, Cambridge University Press, Cambridge, 2000. Reprint of the 1999 original. 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. Dan Boneh and Matthew Franklin, Identity-based encryption from the Weil pairing, SIAM J. Comput. 32 (2003), no. 3, 586–615. MR 2001745 (2004m:94035), http://dx.doi.org/10.1137/S0097539701398521
7. Dan Boneh, Ben Lynn, and Hovav Shacham, Short signatures from the Weil pairing, J. Cryptology 17 (2004), no. 4, 297–319. MR 2090559 (2005h:94040), http://dx.doi.org/10.1007/s00145-004-0314-9
8. Alina Carmen Cojocaru and Igor E. Shparlinski, On the embedding degree of reductions of an elliptic curve, Inform. Process. Lett. 109 (2009), no. 13, 652–654. MR 2527697 (2010d:11066), http://dx.doi.org/10.1016/j.ipl.2009.02.018
9. Kevin Ford, The distribution of integers with a divisor in a given interval, Ann. of Math. (2) 168 (2008), no. 2, 367–433. MR 2434882 (2009m:11152), http://dx.doi.org/10.4007/annals.2008.168.367
10. David Freeman, Michael Scott, and Edlyn Teske, A taxonomy of pairing-friendly elliptic curves, J. Cryptology 23 (2010), no. 2, 224–280. MR 2578668 (2011a:11112), http://dx.doi.org/10.1007/s00145-009-9048-z
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. Richard R. Hall and Gérald Tenenbaum, Divisors, Cambridge Tracts in Mathematics, vol. 90, Cambridge University Press, Cambridge, 1988. MR 964687 (90a:11107)
13. G. H. Hardy and E. M. Wright, An introduction to the theory of numbers, 5th ed., The Clarendon Press Oxford University Press, New York, 1979. MR 568909 (81i:10002)
14. Henryk Iwaniec and Emmanuel Kowalski, Analytic number theory, American Mathematical Society Colloquium Publications, vol. 53, American Mathematical Society, Providence, RI, 2004. MR 2061214 (2005h:11005)
15. Antoine Joux, A one round protocol for tripartite Diffie-Hellman, Algorithmic number theory (Leiden, 2000) Lecture Notes in Comput. Sci., vol. 1838, Springer, Berlin, 2000, pp. 385–393. MR 1850619 (2002i:14029), http://dx.doi.org/10.1007/10722028_23
16. Antoine Joux and Kim Nguyen, Separating decision Diffie-Hellmann from computational Diffie-Hellman in cryptographic groups, J. Cryptology 16 (2003), no. 4, 239–247. MR 2002044 (2004h:94045), http://dx.doi.org/10.1007/s00145-003-0052-4
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. Koray Karabina and Edlyn Teske, On prime-order elliptic curves with embedding degrees 𝑘=3, 4, and 6, Algorithmic number theory, Lecture Notes in Comput. Sci., vol. 5011, Springer, Berlin, 2008, pp. 102–117. MR 2467839 (2010a:11114), http://dx.doi.org/10.1007/978-3-540-79456-1_6
19. A. Languasco and A. Zaccagnini, A note on Mertens’ formula for arithmetic progressions, J. Number Theory 127 (2007), no. 1, 37–46. MR 2351662 (2009g:11136), http://dx.doi.org/10.1016/j.jnt.2006.12.015
20. Florian Luca, David Jose Mireles, and Igor E. Shparlinski, MOV attack in various subgroups on elliptic curves, Illinois J. Math. 48 (2004), no. 3, 1041–1052. MR 2114268 (2005h:11126)
21. Florian Luca and Igor E. Shparlinski, On the exponent of the group of points on elliptic curves in extension fields, Int. Math. Res. Not. 23 (2005), 1391–1409. MR 2152235 (2006h:11072), http://dx.doi.org/10.1155/IMRN.2005.1391
22. Florian Luca and Igor E. Shparlinski, Elliptic curves with low embedding degree, J. Cryptology 19 (2006), no. 4, 553–562. MR 2267556 (2007h:14034), http://dx.doi.org/10.1007/s00145-006-0544-0
23. Florian Luca and Igor E. Shparlinski, On finite fields for pairing based cryptography, Adv. Math. Commun. 1 (2007), no. 3, 281–286. MR 2327047 (2008d:11059), http://dx.doi.org/10.3934/amc.2007.1.281
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. Alfred J. Menezes, Tatsuaki Okamoto, and Scott A. Vanstone, Reducing elliptic curve logarithms to logarithms in a finite field, IEEE Trans. Inform. Theory 39 (1993), no. 5, 1639–1646. MR 1281712 (95e:94038), http://dx.doi.org/10.1109/18.259647
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. Andrew V. Sutherland, Computing Hilbert class polynomials with the Chinese remainder theorem, Math. Comp. 80 (2011), no. 273, 501–538. MR 2728992 (2011k:11177), http://dx.doi.org/10.1090/S0025-5718-2010-02373-7
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. Eduard Wirsing, Das asymptotische Verhalten von Summen über multiplikative Funktionen, Math. Ann. 143 (1961), 75–102 (German). MR 0131389 (24 #A1241)

	Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
\|