Abstract
Previously known techniques to construct pairing-friendly curves of prime or near-prime order are restricted to embedding degree \(k \leqslant 6 \). More general methods produce curves over \({\mathbb F}_{p}\) where the bit length of p is often twice as large as that of the order r of the subgroup with embedding degree k; the best published results achieve ρ ≡ log(p)/log(r) ~ 5/4. In this paper we make the first step towards surpassing these limitations by describing a method to construct elliptic curves of prime order and embedding degree k = 12. The new curves lead to very efficient implementation: non-pairing operations need no more than \({\mathbb F}_{p^4}\) arithmetic, and pairing values can be compressed to one third of their length in a way compatible with point reduction techniques. We also discuss the role of large CM discriminants D to minimize ρ; in particular, for embedding degree k = 2q where q is prime we show that the ability to handle log(D)/log(r) ~ (q–3)/(q–1) enables building curves with ρ ~ q/(q–1).
Chapter 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., Lynn, B., Scott, M.: On the selection of pairing-friendly groups. In: Matsui, M., Zuccherato, R.J. (eds.) SAC 2003. LNCS, vol. 3006, pp. 17–25. Springer, Heidelberg (2004)
Barreto, P.S.L.M., Lynn, B., Scott, M.: Efficient implementation of pairing based cryptosystems. Journal of Cryptology 17(4), 321–334 (2004)
Blake, I., Seroussi, G., Smart, N.: Advances in Elliptic Curve Cryptography. London Mathematical Society Lecture Note Series, vol. 317. Cambridge University Press, Cambridge (2005)
Boneh, D., Franklin, M.: Identity-based encryption from the Weil pairing. SIAM Journal of Computing 32(3), 586–615 (2003)
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 (2002)
Boneh, D., Lynn, B., Shacham, H.: Short signatures from the Weil pairing. Journal of Cryptology 17(4), 297–319 (2004)
Brezing, F., Weng, A.: Elliptic curves suitable for pairing based cryptography. Cryptology ePrint Archive, Report 2003/143 (2003), Available from: http://eprint.iacr.org/2003/143
Dupont, R., Enge, A., Morain, F.: Building curves with arbitrary small MOV degree over finite prime fields. Journal of Cryptology 18(2), 79–89 (2005)
Galbraith, S., McKee, J., Valença, P.: Ordinary abelian varieties having small embedding degree. Cryptology ePrint Archive, Report 2004/365 (2004), Available from: http://eprint.iacr.org/2004/365
Granger, R., Page, D., Stam, M.: On small characteristic algebraic tori in pairing-based cryptography. Cryptology ePrint Archive, Report 2004/132, Available from: http://eprint.iacr.org/2004/132
IEEE Computer Society, New York, USA. IEEE Standard Specifications for Public- Key Cryptography – IEEE Std 1363-2000 (2000)
Lay, G.-J., Zimmer, H.G.: Constructing elliptic curves with given group order over large finite fields. In: Huang, M.-D.A., Adleman, L.M. (eds.) ANTS 1994. LNCS, vol. 877, pp. 250–263. Springer, Heidelberg (1994)
Lenstra, A.K., Verheul, E.R.: The XTR Public Key System. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, pp. 1–19. Springer, Heidelberg (2000)
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)
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)
Rubin, K., Silverberg, A.: Supersingular abelian varieties in cryptology. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 336–353. Springer, Heidelberg (2002)
Scott, M., Barreto, P.S.L.M.: Compressed pairings. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 140–156. Springer, Heidelberg (2004)
Scott, M., Barreto, P.S.L.M.: Generating more MNT elliptic curves. Designs, Codes and Cryptography (2005) (to appear)
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
Barreto, P.S.L.M., Naehrig, M. (2006). Pairing-Friendly Elliptic Curves of Prime Order. In: Preneel, B., Tavares, S. (eds) Selected Areas in Cryptography. SAC 2005. Lecture Notes in Computer Science, vol 3897. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11693383_22
Download citation
DOI: https://doi.org/10.1007/11693383_22
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-33108-7
Online ISBN: 978-3-540-33109-4
eBook Packages: Computer ScienceComputer Science (R0)Springer Nature Proceedings Computer Science
