Speaker：Mingjie Chen (University of Birmingham)

Time：2023-12-01, 15:00

Location：Conference Room 104 at Experiment Building at Haiyun Campus

Abstract:

Isogeny-based cryptography is a field that leverages the mathematical properties of supersingular elliptic curves and their isogenies to construct secure cryptographic protocols. It has developed significantly in the last decade due to increasing interest in post-quantum cryptography. The security of all isogeny-based protocols can be reduced to computing the endomorphism ring of a supersingular elliptic curve in different scenarios. 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. This problem underlies the security of pSIDH protocol (ASIACRYPT 2022). 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 talk, we introduce a new quantum polynomial-time algorithm to solve IsERP for isogenies whose degrees are odd and have O(loglog 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(loglog p) many prime factors to powersmooth elements. This is joint work with Muhammad Imran, Gábor Ivanyos, Péter Kutas, Antonin Leroux, Christophe Petit.