Abstract
The supersingular isogeny Die-Hellman (SIDH) is a postquantum key exchange protocol based on the presumed hardness of computing an isogeny between two supersingular elliptic curves given some additional torsion point information. Unlike other isogeny-based protocols, SIDH has been widely believed to be immune to subexponential quantum attacks because of the non-commutative structure of the endomorphism rings of supersingular curves.
We contradict this folkloric belief in this paper. More precisely, we highlight the existence of an abelian group action on the SIDH key space, and we show that for suciently unbalanced and overstretched SIDH parameters, this action can be eciently computed using the torsion point information revealed in the protocol. This reduces the underlying hardness assumption to an hidden shift problem instance which can be solved in quantum subexponential time.
We formulate our attack in a new framework allowing the inversion of one-way functions in quantum subexponential time provided a malleability oracle with respect to some commutative group action. This framework unies our new attack with earlier subexponential quantum attacks on isogeny-based protocols, and it may be of further interest for cryptanalysis.
We contradict this folkloric belief in this paper. More precisely, we highlight the existence of an abelian group action on the SIDH key space, and we show that for suciently unbalanced and overstretched SIDH parameters, this action can be eciently computed using the torsion point information revealed in the protocol. This reduces the underlying hardness assumption to an hidden shift problem instance which can be solved in quantum subexponential time.
We formulate our attack in a new framework allowing the inversion of one-way functions in quantum subexponential time provided a malleability oracle with respect to some commutative group action. This framework unies our new attack with earlier subexponential quantum attacks on isogeny-based protocols, and it may be of further interest for cryptanalysis.
| Original language | English |
|---|---|
| Title of host publication | Advances in Cryptology – EUROCRYPT 2021 |
| Subtitle of host publication | 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, October 17–21, 2021, Proceedings, Part I |
| Editors | Anne Canteaut, François-Xavier Standaert |
| Publisher | Springer |
| Pages | 242-271 |
| Number of pages | 30 |
| ISBN (Print) | 9783030778699, 9783030778705 |
| DOIs | |
| Publication status | Published - 16 Jun 2021 |
| Event | 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques - Zagreb, Croatia Duration: 17 Oct 2021 → 21 Oct 2021 https://eurocrypt.iacr.org/2021/ |
Publication series
| Name | Lecture Notes in Computer Science |
|---|---|
| Publisher | Springer |
| Volume | 12696 |
| ISSN (Print) | 0302-9743 |
| ISSN (Electronic) | 1611-3349 |
Conference
| Conference | 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques |
|---|---|
| Abbreviated title | EUROCRYPT 2021 |
| Country/Territory | Croatia |
| City | Zagreb |
| Period | 17/10/21 → 21/10/21 |
| Internet address |
Bibliographical note
Funding Information:Acknowledgement. We thank Lorenz Panny for helpful comments on a previous version of this paper and the anonymous reviewers of Eurocrypt2021 for their work and useful feedback. The work of Péter Kutas and Christophe Petit was supported by EPSRC grant EP/S01361X/1. Simon-Philipp Merz was supported by EPSRC grant EP/P009301/1.
Publisher Copyright:
© 2021, International Association for Cryptologic Research.
ASJC Scopus subject areas
- Theoretical Computer Science
- Computer Science(all)