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

：陈明洁（英国伯明翰大学）
：2023-12-01 15:00
：海韵园实验楼104

报告人：陈明洁（英国伯明翰大学）

时  间：2023年12月1日15:00

地  点：海韵园实验楼104

内容摘要:

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.

个人简介：

陈明洁，英国伯明翰大学博士后，2016年本科毕业于武汉大学数学系，2022年博士毕业于加州大学圣地亚哥分校数学系，师从Kiran Kedlaya教授，学习算术几何方向。目前的研究方向为isogeny-based cryptography和computational number theory。研究成果发表于NeurIPS 2023, Asiacrypt 2023等A类国际会议和Acta Arithmatica等国际数学期刊物。

 

联系人：易少云