Abstract
Finding suitable elliptic curves for pairing-based cryptosystems is a crucial step for their actual deployment. Miyaji, Nakabayashi and Takano [12] (MNT) were the first to produce ordinary pairing-friendly elliptic curves of prime order with embedding degree \( k \in \lbrace 3, 4, 6 \rbrace \). Scott and Barreto [16] as well as Galbraith et al. [10] extended this method by allowing the group order to be non-prime. The advantage of this idea is the construction of much more suitable elliptic curves, which we will call generalized MNT curves. A necessary step for the construction of such elliptic curves is finding the solutions of a generalized Pell equation. However, these equations are not always solvable and this fact considerably affects the efficiency of the curve construction. In this paper we discuss a way to construct generalized MNT curves through Pell equations which are always solvable and thus considerably improve the efficiency of the whole generation process. We provide analytic tables with all polynomial families that lead to non-prime pairing-friendly elliptic curves with embedding degree \( k \in \lbrace 3, 4, 6 \rbrace \) and discuss the efficiency of our method through extensive experimental assessments.
This is a preview of subscription content, log in via an institution to check access.
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
Atkin, A.O.L., Morain, F.: Elliptic Curves and Primality Proving. Mathematics of Computation 61, 29–68 (1993)
Barreto, P.S.L.M., Kim, H.Y., Lynn, B., Scott, M.: Efficient Algorithms for Pairing-Based Cryptosystems. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 354–368. Springer, Heidelberg (2002)
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)
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 (2001)
Duan, P., Cui, S., Wah Chan, C.: Finding More Non-Supersingular Elliptic Curves for Pairing-Based Cryptosystems. International Journal of Information Technology 2(2), 157–163 (2005)
Freeman, D., Scott, M., Teske, E.: A Taxonomy of Pairing-Friendly Elliptic Curves. Journal of Cryptology 23, 224–280 (2010)
Galbraith, S.D., Harrison, K., Soldera, D.: Implementing the Tate Pairing. In: Fieker, C., Kohel, D.R. (eds.) ANTS 2002. LNCS, vol. 2369, pp. 324–337. Springer, Heidelberg (2002)
Galbraith, S.D., McKee, J., Valença, P.: Ordinary Abelian Varieties Having Small Embedding Degree. Finite Fields and Their Applications 13(4), 800–814 (2007)
Karabina, K., Teske, E.: On Prime-Order Elliptic Curves with Embedding Degrees k = 3, 4, and 6. In: van der Poorten, A.J., Stein, A. (eds.) ANTS-VIII 2008. LNCS, vol. 5011, pp. 102–117. Springer, Heidelberg (2008)
Miyaji, A., Nakabayashi, M., Takano, S.: New Explicit Conditions of Elliptic Curve Traces for FR-Reduction. IEICE Transactions Fundamentals E84-A(5), 1234–1243 (2001)
Mollin, R.A.: Fundamental Number Theory with Applications. CRC Press, Boca Raton (1998)
Mollin, R.A.: Simple Continued Fraction Solutions for Diophantine Equations. Expositiones Mathematicae 19, 55–73 (2001)
Robertson, J.P.: Solving the Generalized Pell Equation x 2 − Dy 2 = N (2004), http://hometown.aol.com/jpr2718/
Scott, M., Barreto, P.S.L.M.: Generating more MNT Elliptic Curves. Designs, Codes and Cryptography 38, 209–217 (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fotiadis, G., Konstantinou, E. (2013). On the Efficient Generation of Generalized MNT Elliptic Curves. In: Muntean, T., Poulakis, D., Rolland, R. (eds) Algebraic Informatics. CAI 2013. Lecture Notes in Computer Science, vol 8080. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-40663-8_15
Download citation
DOI: https://doi.org/10.1007/978-3-642-40663-8_15
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-40662-1
Online ISBN: 978-3-642-40663-8
eBook Packages: Computer ScienceComputer Science (R0)