Welcome to the resource topic for 2021/282
Title:
One-way functions and malleability oracles: Hidden shift attacks on isogeny-based protocols
Authors: Péter Kutas, Simon-Philipp Merz, Christophe Petit, 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.
ePrint: https://eprint.iacr.org/2021/282
Talk: https://www.youtube.com/watch?v=97AH1KWb7RE
Slides: https://iacr.org/submit/files/slides/2021/eurocrypt/eurocrypt2021/29/slides.pdf
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .