A subexponential-time, polynomial quantum space algorithm for inverting the CM group action
A subexponential-time, polynomial quantum space algorithm for inverting the CM group action
复制标题
用于反转 CM 群作用的次指数时间、多项式量子空间算法
DOI：
--
复制
发表时间：
2020
影响因子：
1.2
通讯作者：
Luis Ruiz
中科院分区：
文献类型：
--
作者：
David Jao;Jason T. LeGrow;Christopher Leonardi;Luis Ruiz
摘要 我们提出了一种量子算法，该算法使用次指数时间但仅使用多项式量子空间来计算同源普通椭圆曲线上的复乘法群作用的群作用逆。该算法的一个应用是它可以用于在基于同源的 CRS 和 CSIDH 密码系统中从公钥中查找私钥。 Childs、Jao 和 Soukharev 先前提出的针对此问题的多项式量子空间算法的主张是错误的；我们的算法（以及 Biasse、Iezzi 和 Jacobson 的同期独立工作）是第一个这样的结果。
Abstract We present a quantum algorithm which computes group action inverses of the complex multiplication group action on isogenous ordinary elliptic curves, using subexponential time, but only polynomial quantum space. One application of this algorithm is that it can be used to find the private key from the public key in the isogeny-based CRS and CSIDH cryptosystems. Prior claims by Childs, Jao, and Soukharev of such a polynomial quantum space algorithm for this problem are false; our algorithm (along with contemporaneous, independent work by Biasse, Iezzi, and Jacobson) is the first such result.