Abstract
We present a general framework for constructing families of elliptic curves of prime order with prescribed embedding degree. We demonstrate this method by constructing curves with embedding degree k = 10, which solves an open problem posed by Boneh, Lynn, and Shacham [6]. We show that our framework incorporates existing constructions for k = 3, 4, 6, and 12, and we give evidence that the method is unlikely to produce infinite families of curves with embedding degree k > 12.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Barreto, P.S.L.M., Lynn, B., Scott, M.: Constructing elliptic curves with prescribed embedding degrees. In: Cimato, S., Galdi, C., Persiano, G. (eds.) SCN 2002. LNCS, vol. 2576, pp. 257–267. Springer, Heidelberg (2003)
Barreto, P.S.L.M., Naehrig, M.: Pairing-friendly elliptic curves of prime order. In: Preneel, B., Tavares, S. (eds.) SAC 2005. LNCS, vol. 3897, pp. 319–331. Springer, Heidelberg (2006)
Blake, I., Seroussi, G., Smart, N.: Elliptic Curves in Cryptography. LMS Lecture Note Series, vol. 265. Cambridge University Press, Cambridge (1999)
Blake, I., Seroussi, G., Smart, N. (eds.): Advances in Elliptic Curve Cryptography. LMS Lecture Note Series, vol. 317. Cambridge University Press, Cambridge (2005)
Boneh, D., Franklin, M.: Identity based encryption from the Weil pairing. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 213–229. Springer, Heidelberg (2001)
Boneh, D., Lynn, B., Shacham, H.: Short signatures from the Weil pairing. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 514–532. Springer, Heidelberg (2001)
Brezing, F., Weng, A.: Elliptic curves suitable for pairing based cryptography. Designs, Codes, and Cryptography 37, 133–141 (2005)
Cocks, C., Pinch, R.G.E.: Identity-based cryptosystems based on the Weil pairing (unpublished manuscript, 2001)
Cornell, G., Silverman, J. (eds.): Arithmetic Geometry. Springer, New York (1986)
Cui, S., Duan, P., Chan, C.W.: A new method of building more non-supersingular elliptic curves. In: Gervasi, O., Gavrilova, M.L., Kumar, V., Laganá, A., Lee, H.P., Mun, Y., Taniar, D., Tan, C.J.K. (eds.) ICCSA 2005. LNCS, vol. 3481, pp. 657–664. Springer, Heidelberg (2005)
Freeman, D.: Constructing families of pairing-friendly elliptic curves. Hew-lett-Packard Laboratories technical report HPL-2005-155 (2005), Available at: http://www.hpl.hp.com/techreports/2005/HPL-2005-155.html
Galbraith, S., McKee, J., Valença, P.: Ordinary abelian varieties having small embedding degree. In: Cramer, R., Okamoto, T. (eds.) Proceedings of a Workshop on Mathematical Problems and Techniques in Cryptology, CRM Barcelona, pp. 29–45 (2005)
Joux, A.: A one round protocol for tripartite Diffie-Hellman. In: Bosma, W. (ed.) ANTS 2000. LNCS, vol. 1838, pp. 385–394. Springer, Heidelberg (2000)
Luca, F., Shparlinski, I.: Elliptic curves with low embedding degree (preprint), Available at: http://eprint.iacr.org/2005/363
Matthews, K.: The diophantine equation x 2 − Dy 2 = N, D > 0, in integers. Expositiones Mathematicae 18, 323–331 (2000)
Menezes, A., Okamoto, T., Vanstone, S.: Reducing elliptic curve logarithms to logarithms in a finite field. IEEE Transactions on Information Theory 39, 1639–1646 (1993)
Miyaji, A., Nakabayashi, M., Takano, S.: New explicit conditions of elliptic curve traces for FR-reduction. IEICE Transactions on Fundamentals E84-A(5), 1234–1243 (2001)
Mollin, R.: Fundamental Number Theory with Applications. CRC Press, Boca Raton (1998)
Morain, F.: Building cyclic elliptic curves modulo large primes. In: Davies, D.W. (ed.) EUROCRYPT 1991. LNCS, vol. 547, pp. 328–336. Springer, Heidelberg (1991)
Neukirch, J.: Algebraic Number Theory. Springer, Berlin (1999)
Robertson, J.: Solving the generalized Pell equation (unpublished manuscript, 2004), Available at: http://hometown.aol.com/jpr2718/pell.pdf
Scott, M.: Personal communication (November 7, 2005)
Silverman, J.: The Arithmetic of Elliptic Curves. GTM, vol. 106. Springer, Heidelberg (1986)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Freeman, D. (2006). Constructing Pairing-Friendly Elliptic Curves with Embedding Degree 10. In: Hess, F., Pauli, S., Pohst, M. (eds) Algorithmic Number Theory. ANTS 2006. Lecture Notes in Computer Science, vol 4076. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11792086_32
Download citation
DOI: https://doi.org/10.1007/11792086_32
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-36075-9
Online ISBN: 978-3-540-36076-6
eBook Packages: Computer ScienceComputer Science (R0)