One-way functions and malleability oracles: hidden shift attacks on isogeny-based protocols

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Authors

Colleges, School and Institutes

External organisations

  • Université Libre de Bruxelles
  • Royal Holloway University of London

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.

Details

Original languageEnglish
Title of host publicationAdvances in Cryptology – EUROCRYPT 2021
Subtitle of host publication40th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, October 17–21, 2021, Proceedings, Part I
EditorsAnne Canteaut, François-Xavier Standaert
Publication statusPublished - 16 Jun 2021
Event40th Annual International Conference on the Theory and Applications of Cryptographic Techniques - Zagreb, Croatia
Duration: 17 Oct 202121 Oct 2021
https://eurocrypt.iacr.org/2021/

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume12696
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference40th Annual International Conference on the Theory and Applications of Cryptographic Techniques
Abbreviated titleEUROCRYPT 2021
CountryCroatia
CityZagreb
Period17/10/2121/10/21
Internet address