International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Péter Kutas , University of Birmingham
Simon-Philipp Merz , Royal Holloway, University of London
Christophe Petit , University of Birmingham and Université libre de Bruxelles
Charlotte Weitkämper , University of Birmingham
Download:
DOI: 10.1007/978-3-030-77870-5_9 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: EUROCRYPT 2021
Abstract: Supersingular isogeny Diffie-Hellman key exchange (SIDH) is a post-quantum 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 commonly believed misconception in this paper. More precisely, we highlight the existence of an abelian group action on the SIDH key space, and we show that for sufficiently \emph{unbalanced} and \emph{overstretched} SIDH parameters, this action can be efficiently computed (heuristically) using the torsion point information revealed in the protocol. This reduces the underlying hardness assumption to a 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 unifies our new attack with earlier subexponential quantum attacks on isogeny-based protocols, and it may be of further interest for cryptanalysis.
Video from EUROCRYPT 2021
BibTeX
@inproceedings{eurocrypt-2021-30920,
  title={One-way functions and malleability oracles: Hidden shift attacks on isogeny-based protocols},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-030-77870-5_9},
  author={Péter Kutas and Simon-Philipp Merz and Christophe Petit and Charlotte Weitkämper},
  year=2021
}