Abstract
We present a new method to evaluate large degree isogenies between elliptic curves over finite fields. Previous approaches all have exponential running time in the logarithm of the degree. If the endomorphism ring of the elliptic curve is ‘small’ we can do much better, and we present an algorithm with a running time that is polynomial in the logarithm of the degree. We give several applications of our techniques to pairing based cryptography.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
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)
Bostan, A., Morain, F., Salvy, B., Schost, E.: Fast algorithms for computing isogenies between elliptic curves. Math. Comp. 77, 1755–1778 (2008)
Bröker, R., Stevenhagen, P.: Constructing elliptic curves of prime order. Contemp. Math. 463, 17–28 (2008)
Cohen, H.: A course in computational algebraic number theory. Springer Graduate Texts in Mathematics, vol. 138 (1993)
Jao, D., Venkatesan, R.: Use of isogenies for design of cryptosystems, http://www.freepatentsonline.com/EP1528705.html
Kohel, D.: Endomorphism Rings of Elliptic Curves over Finite Fields, PhD thesis, University of California at Berkeley (1996)
Konstantinou, E., Stamatiou, Y.C., Zaroliagis, C.D.: On the construction of prime order elliptic curves. In: Johansson, T., Maitra, S. (eds.) INDOCRYPT 2003. LNCS, vol. 2904, pp. 309–322. Springer, Heidelberg (2003)
Lang, S.: Elliptic functions, 2nd edn. Springer Graduate Texts in Mathematics, vol. 112 (1987)
Miyaji, A., Nakabayashi, M., Takano, S.: New explicit conditions of elliptic curve traces for FR-reduction. IEICE Trans. on Fund. E84-A(5), 1234–1243 (2001)
Schoof, R.: Counting points on elliptic curves over finite fields. J. Théor. Nombres Bordeaux 7, 219–254 (1995)
Silverman, J.: Advanced topics in the arithmetic of elliptic curves. Springer Graduate Texts in Mathematics, vol. 151 (1994)
Silverman, J.: The arithmetics of elliptic curves, 2nd edn. Springer Graduate Texts in Mathematics, vol. 106 (1992)
Vélu, J.: Isogénies entre courbes elliptiques. C. R. Acad. Sci. Paris Sér. A–B 273, A238–A241 (1971)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bröker, R., Charles, D., Lauter, K. (2008). Evaluating Large Degree Isogenies and Applications to Pairing Based Cryptography. In: Galbraith, S.D., Paterson, K.G. (eds) Pairing-Based Cryptography – Pairing 2008. Pairing 2008. Lecture Notes in Computer Science, vol 5209. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-85538-5_7
Download citation
DOI: https://doi.org/10.1007/978-3-540-85538-5_7
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-85503-3
Online ISBN: 978-3-540-85538-5
eBook Packages: Computer ScienceComputer Science (R0)