Orientations and the supersingular endomorphism ring problem
Orientations and the supersingular endomorphism ring problem
复制标题
方向和超奇异自同态环问题
DOI：
10.1007/978-3-031-07082-2_13
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
B. Wesolowski
中科院分区：
文献类型：
--
作者：
B. Wesolowski
.我们研究了同构密码学中的两个重要问题家族以及它们之间的关系：计算超奇异椭圆曲线的自同态环，以及反转类群在定向超奇异曲线上的作用。我们证明，这两个家庭的问题是密切相关的，通过多项式时间减少，假设广义黎曼假设。我们确定了两类基本上等价的问题。第一类对应于计算定向曲线的自同态环的问题。一个大家族的密码系统（如CSIDH）的安全性降低到（有时从）这一类，其中有启发式量子算法运行在亚指数时间。第二类对应于计算可定向曲线的自同态环。基本上所有基于同源性的密码系统的安全性都降低到（有时从）这第二类，对于这第二类，最知名的算法仍然是指数的。我们的一些减少不仅推广，但也加强了以前已知的结果。例如，已知在定义于F p上的曲线的特定情况下，CSIDH的安全性在次指数时间内归结为自同态环问题。我们的减少意味着CSIDH的安全性实际上是等价的自同态环问题，在多项式时间减少（规避证明这种减少不太可能的参数）。
. We study two important families of problems in isogeny-based cryptography and how they relate to each other: computing the endomorphism ring of supersingular elliptic curves, and inverting the action of class groups on oriented supersingular curves. We prove that these two families of problems are closely related through polynomial-time reductions, assuming the generalised Riemann hypothesis. We identify two classes of essentially equivalent problems. The first class corresponds to the problem of computing the endomorphism ring of oriented curves . The security of a large family of cryptosystems (such as CSIDH) reduces to (and sometimes from) this class, for which there are heuristic quantum algorithms running in subexponential time. The second class corresponds to computing the endomorphism ring of orientable curves . The security of essentially all isogeny-based cryptosystems reduces to (and sometimes from) this second class, for which the best known algorithms are still exponential. Some of our reductions not only generalise, but also strengthen previously known results. For instance, it was known that in the particular case of curves defined over F p , the security of CSIDH reduces to the endomorphism ring problem in subexponential time. Our reductions imply that the security of CSIDH is actually equivalent to the endomorphism ring problem, under polynomial time reductions (circumventing arguments that proved such reductions unlikely).
计算超奇异椭圆曲线的自同态环以及与同源图中路径查找的联系
DOI：
10.2140/obs.2020.4.215
发表时间：
2020
期刊：
Open Book Series
影响因子：
--
作者：
Eisenträger, Kirsten;Hallgren, Sean;Leonardi, Chris;Morrison, Travis;Park, Jennifer
通讯作者：
Park, Jennifer