article

Computing isogenies between supersingular elliptic curves over $${\mathbb {F}}_p$$Fp

Authors:

Christina Delfs,

Steven D. GalbraithAuthors Info & Claims

Designs, Codes and Cryptography, Volume 78, Issue 2

Pages 425 - 440

https://doi.org/10.1007/s10623-014-0010-1

Published: 01 February 2016 Publication History

Abstract

Let $$p>3$$p>3 be a prime and let $$E$$E, $$E'$$E be supersingular elliptic curves over $${\mathbb {F}}_p$$Fp. We want to construct an isogeny $$\phi :E\rightarrow E'$$ :E E . The currently fastest algorithm for finding isogenies between supersingular elliptic curves solves this problem in the full supersingular isogeny graph over $${\mathbb {F}}_{p^2}$$Fp2. It takes an expected $$\tilde{\mathcal {O}}(p^{1/2})$$O~(p1/2) bit operations, and also $$\tilde{\mathcal {O}}(p^{1/2})$$O~(p1/2) space, by performing a "meet-in-the-middle" breadth-first search in the isogeny graph. In this paper we consider the structure of the isogeny graph of supersingular elliptic curves over $${\mathbb {F}}_p$$Fp. We give an algorithm to construct isogenies between supersingular curves over $${\mathbb {F}}_p$$Fp that works in $$\tilde{\mathcal {O}}(p^{1/4})$$O~(p1/4) bit operations. We then discuss how this algorithm can be used to obtain an improved algorithm for the general supersingular isogeny problem.

References

[1]

Bach E.: Analytic Methods in the Analysis and Design of Number-Theoretic Algorithms. MIT Press, Cambridge (1984).

[2]

Bröker R.: Constructing Elliptic Curves of Prescribed Order. PhD thesis, Universiteit Leiden (2006).

[3]

Charles D.X., Lauter K.E., Goren E.Z.: Cryptographic hash functions from expander graphs. J. Cryptol. 22(1), 93---113 (2009).

Digital Library

[4]

Cohen H.: A Course in Computational Algebraic Number Theory. Springer, Berlin (1996).

[5]

Cox D.A.: Primes of the Form $$x^2 + n y^2 $$x2+ny2. Wiley, Hoboken (1989).

[6]

Galbraith S.D.: Constructing isogenies between elliptic curves over finite fields. LMS J. Comput. Math. 2, 118---138 (1999).

[7]

Galbraith S.D., Hess F., Smart N.: Extending the GHS Weil descent attack. In: Advances in Cryptology--EUROCRYPT 2002, pp. 29---44. Springer, Berlin (2002).

[8]

Galbraith S.D, Stolbunov A.: Improved algorithm for the isogeny problem for ordinary elliptic curves. Appl. Algebr. Eng. Commun. Comput. 24(2), 107---131 (2013).

[9]

Hafner J.L., McCurley K.S.: A rigorous subexponential algorithm for computation of class groups. J. Am. Math. Soc. 2, 837---850 (1989).

[10]

Jao D., De Feo L.: Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies. In: Post-Quantum Cryptography, volume 7071 of Lecture Notes in Computer Science, pp. 19---34. Springer, Berlin (2011).

[11]

Jao D., Miller S.D., Venkatesan R.: Do all elliptic curves of the same order have the same difficulty of discrete log? In: Advances in Cryptology--ASIACRYPT 2005, pp. 21---40. Springer, Berlin (2005).

Digital Library

[12]

Jao D., Miller S.D., Venkatesan R.: Expander graphs based on GRH with an application to elliptic curve cryptography. J. Number Theory 129(6), 1491---1504 (2009).

[13]

Kohel D.: Endomorphism rings of elliptic curves over finite fields. PhD thesis, University of California at Berkeley (1996).

[14]

Mestre J.-F.: La méthode des graphes. Exemples et applications. In: Proceedings of the International Conference on Class Numbers and Fundamental Units of Algebraic Number Fields (Katata), pp. 217---242 (1986).

[15]

Pohl I.: Bi-directional and heuristic search in path problems. Technical Report 104, Stanford Linear Accelerator Center, Stanford, California (1969).

[16]

Rück H.-G.: A note on elliptic curves over finite fields. Math. Comput. 49(179), 301---304 (1987).

[17]

Silverman J.H.: Advanced Topics in the Arithmetic of Elliptic Curves. Springer, New York (1994).

[18]

Silverman J.H.: The Arithmetic of Elliptic Curves, 2nd edn. Springer, Dordrecht (2009).

[19]

Stolbunov A.: Constructing public-key cryptographic schemes based on class group action on a set of isogenous elliptic curves. Adv. Math. Commun. 4(2), 215---235 (2010).

[20]

Tate J.T.: Global class field theory. In: Cassels J.W.S., Frölich A. (eds.) Algebraic Number Theory, pp. 162---203. Academic Press, Washington, DC (1967).

[21]

Vélu J.: Isogénies entre courbes elliptiques. C. R. Acad. Sci. Paris, Ser. A 273, 238---241 (1971).

[22]

Waterhouse W.C.: Abelian varieties over finite fields. Ann. Sci. Ecole Norm. Sup. 2(4), 521---560 (1969).

Cited By

Arpin SClements JDartois PEriksen JKutas PWesolowski B(2024)Finding orientations of supersingular elliptic curves and quaternion ordersDesigns, Codes and Cryptography10.1007/s10623-024-01435-592:11(3447-3493)Online publication date: 1-Nov-2024
https://dl.acm.org/doi/10.1007/s10623-024-01435-5
Bettaieb SBidoux LDyseryn VEsser AGaborit PKulkarni MPalumbi M(2024)PERK: compact signature scheme based on a new variant of the permuted kernel problemDesigns, Codes and Cryptography10.1007/s10623-024-01381-292:8(2131-2157)Online publication date: 27-Mar-2024
https://dl.acm.org/doi/10.1007/s10623-024-01381-2
Onuki HNakagawa K(2024)Ideal-to-Isogeny Algorithm Using 2-Dimensional Isogenies and Its Application to SQIsignAdvances in Cryptology – ASIACRYPT 202410.1007/978-981-96-0891-1_8(243-271)Online publication date: 10-Dec-2024
https://dl.acm.org/doi/10.1007/978-981-96-0891-1_8
Show More Cited By

Recommendations

Self-pairings on supersingular elliptic curves with embedding degree three

Self-pairings are a special subclass of pairings and have interesting applications in cryptographic schemes and protocols. In this paper, we speed up the computation of the self-pairing by using a simple final exponentiation on supersingular elliptic ...
Implementing the 4-dimensional GLV method on GLS elliptic curves with j-invariant 0

The Gallant---Lambert---Vanstone (GLV) method is a very efficient technique for accelerating point multiplication on elliptic curves with efficiently computable endomorphisms. Galbraith et al. (J Cryptol 24(3):446---469, 2011) showed that point ...
Differential addition on binary elliptic curves
Abstract
This paper presents new and fast differential addition (i.e., the addition of two points with the known difference) and doubling formulas, as the core step in Montgomery scalar multiplication, for various forms of elliptic curves over ...
Highlights
- Differential addition and doubling formulas.
- Efficient arithmetic on elliptic ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Designs, Codes and Cryptography

Designs, Codes and Cryptography Volume 78, Issue 2

February 2016

194 pages

ISSN:0925-1022

Issue’s Table of Contents

Copyright © Copyright © 2016 Springer Science+Business Media New York.

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 February 2016

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

39
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Arpin SClements JDartois PEriksen JKutas PWesolowski B(2024)Finding orientations of supersingular elliptic curves and quaternion ordersDesigns, Codes and Cryptography10.1007/s10623-024-01435-592:11(3447-3493)Online publication date: 1-Nov-2024
https://dl.acm.org/doi/10.1007/s10623-024-01435-5
Bettaieb SBidoux LDyseryn VEsser AGaborit PKulkarni MPalumbi M(2024)PERK: compact signature scheme based on a new variant of the permuted kernel problemDesigns, Codes and Cryptography10.1007/s10623-024-01381-292:8(2131-2157)Online publication date: 27-Mar-2024
https://dl.acm.org/doi/10.1007/s10623-024-01381-2
Onuki HNakagawa K(2024)Ideal-to-Isogeny Algorithm Using 2-Dimensional Isogenies and Its Application to SQIsignAdvances in Cryptology – ASIACRYPT 202410.1007/978-981-96-0891-1_8(243-271)Online publication date: 10-Dec-2024
https://dl.acm.org/doi/10.1007/978-981-96-0891-1_8
Basso ADartois PFeo LLeroux AMaino LPope GRobert DWesolowski B(2024)SQIsign2D–WestAdvances in Cryptology – ASIACRYPT 202410.1007/978-981-96-0891-1_11(339-370)Online publication date: 10-Dec-2024
https://dl.acm.org/doi/10.1007/978-981-96-0891-1_11
Katayama AYasuda M(2024)Computing a Basis of the Set of Isogenies Between Two Supersingular Elliptic CurvesComputer Algebra in Scientific Computing10.1007/978-3-031-69070-9_11(178-192)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-69070-9_11
Benčina BKutas PMerz SPetit CStopar MWeitkämper C(2024)Improved Algorithms for Finding Fixed-Degree Isogenies Between Supersingular Elliptic CurvesAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68388-6_8(183-217)Online publication date: 18-Aug-2024
https://dl.acm.org/doi/10.1007/978-3-031-68388-6_8
Decru T(2024)Radical Isogeny FormulaeAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68388-6_5(107-128)Online publication date: 18-Aug-2024
https://dl.acm.org/doi/10.1007/978-3-031-68388-6_5
Nakagawa KOnuki H(2024)QFESTA: Efficient Algorithms and Parameters for FESTA Using Quaternion AlgebrasAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68388-6_4(75-106)Online publication date: 18-Aug-2024
https://dl.acm.org/doi/10.1007/978-3-031-68388-6_4
De Feo LFouotsa TPanny L(2024)Isogeny Problems with Level StructureAdvances in Cryptology – EUROCRYPT 202410.1007/978-3-031-58754-2_7(181-204)Online publication date: 26-May-2024
https://dl.acm.org/doi/10.1007/978-3-031-58754-2_7
Corte-Real Santos MEriksen JMeyer MReijnders K(2024)AprèsSQI: Extra Fast Verification for SQIsign Using Extension-Field SigningAdvances in Cryptology – EUROCRYPT 202410.1007/978-3-031-58716-0_3(63-93)Online publication date: 26-May-2024
https://dl.acm.org/doi/10.1007/978-3-031-58716-0_3
Show More Cited By

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents