Cryptology ePrint Archive: Report 2021/282

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

Péter Kutas and Simon-Philipp Merz and 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.

Category / Keywords: public-key cryptography / supersingular, isogeny, cryptanalysis, hidden shift problem, SIDH

Original Publication (with major differences): IACR-EUROCRYPT-2021

Date: received 4 Mar 2021

Contact author: simon-philipp merz 2018 at rhul ac uk, p kutas@bham ac uk, christophe petit@ulb be, CXW916@student bham ac uk

Available format(s): PDF | BibTeX Citation

Version: 20210307:022232 (All versions of this report)

Short URL: ia.cr/2021/282


[ Cryptology ePrint archive ]