Isogeny based cryptography

Isogeny-based cryptography is a kind of elliptic-curve cryptography, whose security relies on (various incarnations of) the problem of finding an explicit isogeny between two given isogenous supersingular elliptic curves over a finite field $\mathbb F_q$. However, given an elliptic curve $E$ in Weierstrass form over a finite field $\mathbb F_q$ and a point $P$ on $E$ of order $n$, one can compute a cyclic separable isogeny of degree $n$ using Velu’s formulas in SageMath (implemented by D. Shumow in 2009).

Currently, quantum computers do not seem to make the isogeny-finding problem substantially easier. This contrasts with the standard discrete-logarithm based elliptic-curve cryptography which is not quantum-safe due to polynomial-time quantum algorithm by P. W. Shor from 1997.

The blog posts by Maria Santos (UCL) provide a nice introduction to isogeny-based cryptography.

Now let’s look at some of the popular examples.

Supersingular isogeny Diffie–Hellman (SIDH)

It was introduced by L. De Feo, D. Jao, and J. Plût in 2011 and uses the full ring of endomorphisms of supersingular elliptic curves, which is an order in a quaternion algebra, and the fact that the supersingular isogeny graph is Ramanujan. This scheme is a reminiscent of the Charles-Goren-Lauter (CGL) cryptographic hash function from 2006, which was broken in 2020. Its current implementation is called Supersingular Isogeny Key Encapsulation (SIKE) and was submitted to the NIST competition on post-quantum cryptography in 2017. An efficient algorithm for computing the endomorphism ring of a supersingular elliptic curve, under certain assumptions, would completely break the SIKE. The SIDH also motivated the introduction of a new isogeny-based signature schemes like Galbraith-Petit-Silva signature and Short Quaternion and Isogeny Signature (SQISign; pronounced “ski-sign”).

Update (Feb 02, 2022): Using SageMath 9.5, one can implement SIDH in only 20 lines of code (announcement).

Update (Jul 30, 2022): SIKE broken by Wouter Castryck and Thomas Decru. The SageMath implementation of this attack recovers the private key in few minutes. See the posts by Steven Galbraith and Lorenz Panny to understand the attack. One can find the current status of attacks here. Here is a summary posted by Luca De Feo:

Update (Mar 26, 2023): SQISign has new resources like SQISign 2.0, SQISignHD, and Learning to SQI.

Update (Apr 25, 2023): A blogpost by Thomas Decru explaing the SIDH attack.

Upadate (Jan 21, 2024): The ALGANT Master’s thesis by Riya Parankimamvila Mamachan about the mathematical aspects of the Castryck-Decru key recovery attack on SIDH.

References

I have included the university location for the write-ups/videos by graduate students. The ones that I found the most useful are star marked (*).

1. M. Pierrakea (ALGANT-Bordeaux 2016-17), Supersingular isogeny key-exchange
2. *D. Urbanik (Waterloo 2016-17), A Friendly Introduction to Supersingular Isogeny Diffie-Hellman (Bonus: video and slides)
3. L. De Feo (2017), Mathematics of Isogeny Based Cryptography (Bonus: slides)
4. S. Galbraith and F. Vercauteren (2017), Computational problems in supersingular elliptic curve isogenies
5. L. Panny (TU Eindhoven 2017), You could have invented Supersingular Isogeny Diffie-Hellman
6. M. Inés, A. Ali, and A. Best (Boston 2018), Supersingular Isogeny Graphs and Quaternion Algebras (Bonus: BUNTES Fall 2018)
7. S. Arpin (Boulder 2019) , A Survey of Literature on Supersingular Isogeny Graphs
8. *C. Costello (2019), Supersingular isogeny key exchange for beginners (Bonus: video, Companion SageMath notebook by Wojciech Nawrocki, and Computation verification by me using SageMath)
9. K. Lauter and J. Sotáková (2021), Supersingular Isogeny Graphs in Cryptography (Bonus: PCMI webpage and KLPT algorithm podcast)
10. P. Longa (2021), Supersingular Isogeny-Based Cryptography: Implementation Aspects and Parameter Selection (Bonus: slides and related video)
11. J-J Chi-Domínguez (2021), A quick journey on what SI[DH/KE] is (Bonus: slides; the notation used for function composition is a bit confusing; here “Kummer line arithmetic” = Montgomery ladder + Vélu’s formulas – see the original SIDH paper.)

Commutative supersingular isogeny Diffie–Hellman (CSIDH; pronounced “sea-side”)

It was introduced by W. Castryck, T. Lange, C. Martindale, L. Panny, and J. Renes in 2018 and uses the subring of $\mathbb F_p$-rational endomorphisms of supersingular elliptic curves, which is an order $O$ in an imaginary quadratic field. Moreover, the ideal-class group $\mathrm{cl}(O)$ is commutative, unlike the full ring of endomorphisms. This is an efficient variant of the Couveignes-Rostovtsev–Stolbunov (CRS) scheme for which the commutativity of ideal-class group leads to a subexponential attack using the quantum algorithms by G. Kuperberg and O. Regev from 2004. The CSIDH also motivated the introduction of a new isogeny-based signature schemes like SeaSign and Commutative supersingular isogeny based Fiat-Shamir signatures (CSI-FiSH; pronounced “sea-fish”).

References

I have included the university location for the write-ups/videos by graduate students.

1. L. De Feo (2019), Isogeny Graphs in Cryptography (Bonus: David Jao on math.SE)
2. J. Sotáková (Amsterdam 2020), Elliptic curves, isogenies, and endomorphism rings (Bonus: video)
3. Y.B. Ti (Auckland 2020), Mathematics of Isogeny-based cryptography
4. T. Lange and L. Panny (2021), (C)SIDH (Bonus: L. Panny’s notes and Martindale-Panny article)
5. J.-F. Biasse (2021), Ideal class group computations for isogeny-based cryptography
6. S. Galbraith (2023), The Ideal Class Group Action on Supersingular Elliptic Curves

Recent developments

There are many new cryptosystems being developed, like OSIDH, Séta (broken), SIAKE, SiGamal, B-SIDH (broken), and CTIDH.

References

1. The webpages for SIKE and CSIDH.
2. S. Galbraith’s blog ellipticnews
3. D. Jao’s seminar at ANTS-XIV: Isogeny-based cryptography: past, present, and future
4. L. De Feo’s presentations:
   • Pirates of the CSIDH (Bonus: preprint)
   • Are Isogenies for Real? (Bonus: discussion session)
   • What’s next for isogeny based cryptography? (Bonus: slides)
5. Isogeny-based Cryptography School: https://isogenyschool2020.co.uk/schedule/
   • W. Castryck, CSIDH on the surface (CSURF), Week 3: Basic protocols (19-23rd July 2021)
   • L. De Feo, Tools for designing protocols based on isogenies (VDF, ORPF,…), Week 5: Advanced protocols (2-6th August 2021)
   • J. Sotáková, Genus theory and attacking CSIDH-like cryptosystems, Week 6: Classical cryptanalysis (9-13th August 2021)
   • C. Costello, Why Hyperelliptic? : Using Kummer arithmetic to optimize genus one isogeny computations, Week 9: Genus two (6-10th September 2021)
   • D.J. Bernstein, √élu: Faster computation of isogenies of large prime degree, Week 10: Efficient computation of isogenies (13-17th September 2021)
6. Cryptography FM podcast (Nadim Kobeissi)
   • L. De Feo and H. Montgomery, Cryptographic Group Actions and Applications, Episode 5 (27 Oct 2020)
   • B. Wesolowski, The supersingular isogeny path and endomorphism ring problems are equivalent), Episode 21 (24 Aug 2021)
7. Security, Cryptography, Whatever podcast (Deirdre Connolly, Thomas Ptacek, and David Adrian)
   • G. Tankersley, PAKEs, oPRFs, algebra,…, Episode 8 (26 Oct 2021)
   • Hertzbleed, Episode 18 (17 Jun 2022)
   • S. Galbraith, Hot Cryptanalytic Summer, Season 2, Episode 2 (11 Aug 2022)
8. Workshop on Elliptic Curve Cryptography (ECC): https://eccworkshop.org/
9. Algorithmic Number Theory Symposium (ANTS): https://antsmath.org
10. Simons Collaboration on Arithmetic Geometry, Number Theory, and Computation: https://simonscollab.icerm.brown.edu/
11. Virtual math seminar on open conjectures in number theory and arithmetic geometry (VaNTAGe): https://sites.google.com/view/vantageseminar
12. ISOCRYPT - Isogeny-based Toolbox for Post-quantum Cryptography: https://www.esat.kuleuven.be/cosic/projects/isocrypt/
13. The Isogeny Club: https://the-isogeny-club.github.io/