Abstract
SIDH is a post-quantum key exchange algorithm based on the presumed difficulty of finding isogenies between supersingular elliptic curves. However, SIDH and related cryptosystems also reveal additional information: the restriction of a secret isogeny to a subgroup of the curve (torsion-point information). Petit [31] was the first to demonstrate that torsion-point information could noticeably lower the difficulty of finding secret isogenies. In particular, Petit showed that “overstretched” parameterizations of SIDH could be broken in polynomial time. However, this did not impact the security of any cryptosystems proposed in the literature. The contribution of this paper is twofold: First, we strengthen the techniques of [31] by exploiting additional information coming from a dual and a Frobenius isogeny. This extends the impact of torsion-point attacks considerably. In particular, our techniques yield a classical attack that completely breaks the n-party group key exchange of [2], first introduced as GSIDH in [17], for 6 parties or more, and a quantum attack for 3 parties or more that improves on the best known asymptotic complexity. We also provide a Magma implementation of our attack for 6 parties. We give the full range of parameters for which our attacks apply. Second, we construct SIDH variants designed to be weak against our attacks; this includes backdoor choices of starting curve, as well as backdoor choices of base-field prime. We stress that our results do not degrade the security of, or reveal any weakness in, the NIST submission SIKE [20].
Author list in alphabetical order; see https://www.ams.org/profession/leaders/culture/CultureStatement04.pdf. Lorenz Panny was a PhD student at Technische Universiteit Eindhoven while this research was conducted. Péter Kutas and Christophe Petit’s work was supported by EPSRC grant EP/S01361X/1. Katherine E. Stange was supported by NSF-CAREER CNS-1652238. This work was supported in part by the Commission of the European Communities through the Horizon 2020 program under project number 643161 (ECRYPT-NET) and in part by NWO project 651.002.004 (CHIST-ERA USEIT). Date of this document: 2021-06-25. ©IACR 2021. This article is the final version submitted by the author(s) to the IACR and to Springer-Verlag on June 25, 2021. The version published by Springer-Verlag is available at <DOI>.”.
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
Similar content being viewed by others
Notes
- 1.
See Sect. 2.2 for how the objects discussed are represented computationally.
- 2.
- 3.
Note that the naïve meet-in-the-middle approach has prohibitively large memory requirements. Collision finding à la van Oorschot–Wiener thus performs better in practice, although its time complexity is worse in theory [1].
- 4.
[17] also proposes a different group key agreement, SIBD, to which our attack does not apply.
- 5.
Each occurrence of \({\text {polylog}}(p)\) is shorthand for a concrete, fixed polynomial in \(\log p\). (The notation is not meant to imply that all instances of \({\text {polylog}}(p)\) be the same).
- 6.
- 7.
Note that the newest version of SIKE [20] changed the starting curve to a 2-isogenous neighbour of \(j=1728\), but this does not affect the asymptotic complexity of any attack.
- 8.
More generally, these attacks apply for any “special” starting curve in the sense of [26].
- 9.
In the proof, it suffices to take \(p^k > A\) for any k.
- 10.
- 11.
In [10] the theorem was referred to as a classical result, considered to be folklore.
- 12.
Some choices of A and B result in \(D \equiv 2 \pmod 4\) which is an obstruction to this method.
- 13.
We resist the temptation of referring to such instantiations as “door” instead of “backdoor”.
- 14.
For the reader who is wondering exactly how to apply Grover’s algorithm in this context: Let \(\langle P_A, Q_A \rangle = E_0[A^{\gamma }].\) The input for Grover’s algorithm here is an integer \(n < A^{\gamma }\) and all of the input of Algorithm 5. Attempt Steps 2 and 3 for \(\varphi _g\) such that \(\ker (\varphi _g) = \langle P_A + nQ_A\rangle \); the output will be success or failure. Every subroutine of Steps 2 and 3 can be broken down into basic elliptic curve arithmetic for which there are known quantum algorithms of similar complexity to their classical counterparts.
- 15.
References
Adj, G., Cervantes-Vázquez, D., Chi-Domínguez, J.-J., Menezes, A., Rodríguez-Henríquez, F.: On the cost of computing isogenies between supersingular elliptic curves. In: Cid, C., Jacobson Jr, M. (eds.) SAC 2018. LNCS, vol. 11349, pp. 322–343. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-10970-7_15
Azarderakhsh, R., Jalali, A., Jao, D., Soukharev, V.: Practical supersingular isogeny group key agreement. IACR Cryptology ePrint Archive 2019/330 (2019)
Batut, C., Belabas, K., Bernardi, D., Cohen, H., Olivier, M.: User’s Guide to PARI-GP. Université de Bordeaux I. https://pari.math.u-bordeaux.fr/
Biasse, J.-F., Jao, D., Sankar, A.: A quantum algorithm for computing isogenies between supersingular elliptic curves. In: Meier, W., Mukhopadhyay, D. (eds.) INDOCRYPT 2014. LNCS, vol. 8885, pp. 428–442. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-13039-2_25
Boneh, D., Kogan, D., Woo, K.: Oblivious pseudorandom functions from isogenies. In: Moriai, S., Wang, H. (eds.) ASIACRYPT 2020, Part II. LNCS, vol. 12492, pp. 520–550. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-64834-3_18
Bosma, W., Cannon, J., Playoust, C.: The Magma algebra system I: the user language. J. Symbolic Comput. 24(3–4), 235–265 (1997). https://magma.maths.usyd.edu.au/
Bottinelli, P., de Quehen, V., Leonardi, C., Mosunov, A., Pawlega, F., Sheth, M.: The dark SIDH of isogenies. IACR Cryptology ePrint Archive 2019/1333 (2019)
Castryck, W., Lange, T., Martindale, C., Panny, L., Renes, J.: CSIDH: an efficient post-quantum commutative group action. In: Peyrin, T., Galbraith, S. (eds.) ASIACRYPT 2018, Part III. LNCS, vol. 11274, pp. 395–427. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-03332-3_15
Castryck, W., Panny, L., Vercauteren, F.: Rational isogenies from irrational endomorphisms. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020, Part II. LNCS, vol. 12106, pp. 523–548. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45724-2_18
Colò, L., David, K.: Orienting supersingular isogeny graphs. J. Math. Cryptology 14(1), 414–437 (2020)
Costello, C.: B-SIDH: supersingular isogeny Diffie-Hellman using twisted torsion. In: Moriai, S., Wang, H. (eds.) ASIACRYPT 2020, Part II. LNCS, vol. 12492, pp. 440–463. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-64834-3_15
Cremona, J., David, R.: Efficient solution of rational conics. Math. Comput. 72(243), 1417–1441 (2003)
de Quehen, V., et al.: Improved torsion-point attacks on SIDH variants. Full version of this article. IACR Cryptology ePrint Archive 2020/633 (2021). https://ia.cr/2020/633
Delpech de Saint Guilhem, C., Kutas, P., Petit, C., Silva, J.: SÉTA: supersingular encryption from torsion attacks. IACR Cryptology ePrint Archive 2019/1291 (2019)
Delfs, C., Galbraith, S.D.: Computing isogenies between supersingular elliptic curves over \(\mathbb{F}_p\). Des. Codes Crypt. 78(2), 425–440 (2016)
Eisenträger, K., Hallgren, S., Lauter, K., Morrison, T., Petit, C.: Supersingular isogeny graphs and endomorphism rings: reductions and solutions. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018, Part III. LNCS, vol. 10822, pp. 329–368. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78372-7_11
Furukawa, S., Kunihiro, N., Takashima, K.: Multi-party key exchange protocols from supersingular isogenies. In: ISITA, pp. 208–212. IEEE (2018)
Galbraith, S.D., Petit, C., Shani, B., Ti, Y.B.: On the security of supersingular isogeny cryptosystems. In: Cheon, J.H., Takagi, T. (eds.) ASIACRYPT 2016, Part I. LNCS, vol. 10031, pp. 63–91. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53887-6_3
Ivanyos, G., Rónyai, L.: Finding maximal orders in semisimple algebras over \(\mathbb{Q}\). Comput. Complex. 3(3), 245–261 (1993)
Jao, D., et al.: Supersingular isogeny key encapsulation. Updated version of [21] for round 3 of [29] (2020)
Jao, D., et al.: Supersingular isogeny key encapsulation. Submission to [29] (2017). https://sike.org
Jao, D., De Feo, L.: Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies. In: Yang, B.-Y. (ed.) PQCrypto 2011. LNCS, vol. 7071, pp. 19–34. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25405-5_2
Jaques, S., Schanck, J.M.: Quantum cryptanalysis in the RAM model: claw-finding attacks on SIKE. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019, Part I. LNCS, vol. 11692, pp. 32–61. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26948-7_2
Jaques, S., Schrottenloher, A.: Low-gate quantum golden collision finding. In: SAC 2020. Springer (2020)
Kaneko, M.: Supersingular \(j\)-invariants as singular moduli mod \(p\). Osaka J. Math. 26(4), 849–855 (1989)
Kohel, D., Lauter, K., Petit, C., Tignol, J.-P.: On the quaternion \(\ell \)-isogeny path problem. LMS J. Comput. Math. 17A, 418–432 (2014)
Love, J., Boneh, D.: Supersingular curves with small non-integer endomorphisms. In: Galbraith, S. (ed.) ANTS XIV: Proceedings of the Fourteenth Algorithmic Number Theory Symposium (2020)
Martindale, C., Panny, L.: How to not break SIDH. In: CFAIL 2019 (2019)
National Institute of Standards and Technology: Post-quantum cryptography standardization, December 2016. https://csrc.nist.gov/Projects/Post-Quantum-Cryptography/Post-Quantum-Cryptography-Standardization
Onuki, H.: On oriented supersingular elliptic curves. Finite Fields Appl. 69, 101777 (2021)
Petit, C.: Faster algorithms for isogeny problems using torsion point images. In: Takagi, T., Peyrin, T. (eds.) ASIACRYPT 2017, Part II. LNCS, vol. 10625, pp. 330–353. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70697-9_12
Petit, C., Lauter, K.E.: Hard and easy problems for supersingular isogeny graphs. IACR Cryptology ePrint Archive 2017/962 (2017)
Pohlig, S., Hellman, M.: An improved algorithm for computing logarithms over \(\rm GF(p)\) and its cryptographic significance (corresp.). IEEE Trans. Inf. Theory 24(1), 106–110 (1978)
Sahu, R.A., Gini, A., Pal, A.: Supersingular isogeny-based designated verifier blind signature. IACR Cryptology ePrint Archive 2019/1498 (2019)
Siegel, C.L.: Über die Classenzahl quadratischer Zahlkörper. Acta Arithmetica, pp. 83–86 (1935)
Simon, D.: Quadratic equations in dimensions 4, 5 and more. Preprint (2005). https://simond.users.lmno.cnrs.fr/maths/Dim4.pdf
Tako, B.F., Kutas, P., Merz, S.-P.: On the isogeny problem with torsion point information. IACR Cryptology ePrint Archive 2021/153
Tani, S.: An improved claw finding algorithm using quantum walk. In: Kučera, L., Kučera, A. (eds.) MFCS 2007. LNCS, vol. 4708, pp. 536–547. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-74456-6_48
Voight, J.: Identifying the matrix ring: algorithms for quaternion algebras and quadratic forms. In: Alladi, K., Bhargava, M., Savitt, D., Tiep, P. (eds.) Quadratic and Higher Degree Forms, pp. 255–298. Springer, New York (2013). https://doi.org/10.1007/978-1-4614-7488-3_10
Acknowledgements
Thanks to Daniel J. Bernstein for his insight into estimating sizes of solutions to Eq. 3, to John Voight for answering a question of ours concerning Subsect. 5.2, and to Boris Fouotsa for identifying errors in Proposition 34 and its proof. We would also like to thank Filip Pawlega and the anonymous reviewers for their careful reading and helpful feedback.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Copyright information
© 2021 International Association for Cryptologic Research
About this paper
Cite this paper
de Quehen, V. et al. (2021). Improved Torsion-Point Attacks on SIDH Variants. In: Malkin, T., Peikert, C. (eds) Advances in Cryptology – CRYPTO 2021. CRYPTO 2021. Lecture Notes in Computer Science(), vol 12827. Springer, Cham. https://doi.org/10.1007/978-3-030-84252-9_15
Download citation
DOI: https://doi.org/10.1007/978-3-030-84252-9_15
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-84251-2
Online ISBN: 978-3-030-84252-9
eBook Packages: Computer ScienceComputer Science (R0)
