论文标题
定向登记有一个内态
Orienteering with one endomorphism
论文作者
论文摘要
在基于肾上腺素的基础密码学中，路径调查问题减少了内态戒指问题。可以将路径调查简化为仅知道一个内态性吗？众所周知，一个小的内态能够实现多项式时间探路和内态戒指计算（Love-Boneh [36]）。内态性给出了超椭圆曲线的明确取向。在本文中，我们使用定向的超级同学图形的火山结构在图上进行上升/降序/水平步骤，并将路径调查算法推导为初始曲线。火山的每个高度都对应于一个唯一的二次阶，称为原始顺序。我们引入了一个新的硬问题，即在曲线上有任意内态的计算原始顺序，并且我们还提供了一种用于求解它的亚指数量子算法。在并发工作（Wesolowski [54]）中，表明内态性环问题在存在一个具有已知原始顺序的一个内态性的情况下减少了矢量化问题，这意味着途径找到算法。从某种意义上说，我们不承担与内态性相关的原始顺序的了解，我们的探路算法更一般。
In supersingular isogeny-based cryptography, the path-finding problem reduces to the endomorphism ring problem. Can path-finding be reduced to knowing just one endomorphism? It is known that a small endomorphism enables polynomial-time path-finding and endomorphism ring computation (Love-Boneh [36]). An endomorphism gives an explicit orientation of a supersingular elliptic curve. In this paper, we use the volcano structure of the oriented supersingular isogeny graph to take ascending/descending/horizontal steps on the graph and deduce path-finding algorithms to an initial curve. Each altitude of the volcano corresponds to a unique quadratic order, called the primitive order. We introduce a new hard problem of computing the primitive order given an arbitrary endomorphism on the curve, and we also provide a sub-exponential quantum algorithm for solving it. In concurrent work (Wesolowski [54]), it was shown that the endomorphism ring problem in the presence of one endomorphism with known primitive order reduces to a vectorization problem, implying path-finding algorithms. Our path-finding algorithms are more general in the sense that we don't assume the knowledge of the primitive order associated with the endomorphism.
