Paper 2023/779

Hidden Stabilizers, the Isogeny To Endomorphism Ring Problem and the Cryptanalysis of pSIDH

Mingjie Chen, University of Birmingham
Muhammad Imran, Budapest University of Technology and Economics
Gábor Ivanyos, Institute for Computer Science and Control, Hungarian Research Network
Péter Kutas, University of Birmingham, Eötvös Loránd University
Antonin Leroux, DGA-MI, Bruz, France, IRMAR, UMR 6625, Université de Rennes
Christophe Petit, Université Libre de Bruxelles, University of Birmingham
Abstract

The Isogeny to Endomorphism Ring Problem (IsERP) asks to compute the endomorphism ring of the codomain of an isogeny between supersingular curves in characteristic $p$ given only a representation for this isogeny, i.e. some data and an algorithm to evaluate this isogeny on any torsion point. This problem plays a central role in isogeny-based cryptography; it underlies the security of pSIDH protocol (ASIACRYPT 2022) and it is at the heart of the recent attacks that broke the SIDH key exchange. Prior to this work, no efficient algorithm was known to solve IsERP for a generic isogeny degree, the hardest case seemingly when the degree is prime. In this paper, we introduce a new quantum polynomial-time algorithm to solve IsERP for isogenies whose degrees are odd and have $O(\log\log p)$ many prime factors. As main technical tools, our algorithm uses a quantum algorithm for computing hidden Borel subgroups, a group action on supersingular isogenies from EUROCRYPT 2021, various algorithms for the Deuring correspondence and a new algorithm to lift arbitrary quaternion order elements modulo an odd integer $N$ with $O(\log\log p)$ many prime factors to powersmooth elements. As a main consequence for cryptography, we obtain a quantum polynomial-time key recovery attack on pSIDH. The technical tools we use may also be of independent interest.

Note: Updated one author's affiliation.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A minor revision of an IACR publication in ASIACRYPT 2023
Keywords
Isogeny-based CryptographyPost-Quantum CryptographyQuantum Cryptanalysis
Contact author(s)
mic181 @ ucsd edu
muh imran716 @ gmail com
gabor ivanyos @ sztaki hu
p kutas @ bham ac uk
antonin leroux @ polytechnique org
christophe petit @ ulb be
History
2023-09-18: last of 3 revisions
2023-05-28: received
See all versions
Short URL
https://ia.cr/2023/779
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/779,
      author = {Mingjie Chen and Muhammad Imran and Gábor Ivanyos and Péter Kutas and Antonin Leroux and Christophe Petit},
      title = {Hidden Stabilizers, the Isogeny To Endomorphism Ring Problem and the Cryptanalysis of {pSIDH}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/779},
      year = {2023},
      url = {https://eprint.iacr.org/2023/779}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.