Paper 2021/282

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

Péter Kutas, Simon-Philipp Merz, Christophe Petit, and Charlotte Weitkämper

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 unbalanced and 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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A major revision of an IACR publication in EUROCRYPT 2021
Keywords
supersingularisogenycryptanalysishidden shift problemSIDH
Contact author(s)
simon-philipp merz 2018 @ rhul ac uk
p kutas @ bham ac uk
christophe petit @ ulb be
CXW916 @ student bham ac uk
History
2021-03-07: received
Short URL
https://ia.cr/2021/282
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/282,
      author = {Péter Kutas and Simon-Philipp Merz and Christophe Petit and Charlotte Weitkämper},
      title = {One-way functions and malleability oracles: Hidden shift attacks on isogeny-based protocols},
      howpublished = {Cryptology {ePrint} Archive, Paper 2021/282},
      year = {2021},
      url = {https://eprint.iacr.org/2021/282}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.