CAREER: Accelerating Algorithms for Computing Isogenies and Endomorphisms of Supersingular Elliptic Curves

这个奖项的重点是寻找大图的某些族的路径，称为等根图。基于等基因图的密码学的安全性建立在等基因图寻路的难度上，而寻路问题即使对于量子计算机来说也是困难的。基于此，基于等基因的密码系统被认为即使在后量子世界也是安全的。该项目将专注于研究同基因图的结构，以发现更快的计算路径和周期的算法，从而更好地理解基于同基因的密码系统的安全性。这些密码系统有一天可以帮助保护现代互联网，因此对其安全性的具体理解，以及对等基因图中寻路难度的具体理解，是必要的。研究部分由教育活动补充，重点是将基于项目的学习纳入数论和密码学的本科数学课程。基于等根的密码系统的安全性基于计算两个给定的超奇异椭圆曲线之间的等根的难度。这样的密码系统因其小的公钥和对量子攻击的抵抗力而具有吸引力。SIKE是NIST过程中唯一基于同基因的KEM，经过十多年的密码分析，最近被完全打破，这突出了依赖一般同基因问题而不是较弱问题的必要性。一般的超奇异等构问题等价于计算给定超奇异椭圆曲线的自同态环问题。本课题的主要研究目标是设计和分析计算超奇异椭圆曲线的自同态环的算法。该项目的第二个主题旨在确定混合速率尚未确定的等质图的膨胀特性。这些同根图的推广可以应用于密码学，因此研究它们的展开性质是很重要的。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

This award focuses on finding paths in certain families of large graphs, called isogeny graphs. Isogeny-based cryptography bases its security on the hardness of path-finding in isogeny graphs, and the path-finding problem is believed to be hard even for quantum computers. Based on this, isogeny-based cryptosystems are believed to be secure even in a post-quantum world. This project will focus on studying the structure of isogeny graphs in order to uncover faster algorithms for computing paths and cycles, leading to a better understanding of the security of isogeny-based cryptosystems. These cryptosystems could one day help secure the modern internet, so a concrete understanding of their security, and hence a concrete understanding of the difficulty of path-finding in isogeny graphs, is imperative. The research component is complemented by educational activities focused on incorporating project-based learning involving programming in undergraduate mathematics courses on number theory and cryptography.Isogeny-based cryptosystems base their security on the difficulty of computing an isogeny between two given supersingular elliptic curves. Such cryptosystems are attractive for their small public keys and their supposed resistance to quantum attacks. SIKE, the lone isogeny-based KEM in the NIST process, was recently completely broken after over a decade of cryptanalysis, highlighting the necessity of relying on the general isogeny problem instead of a weaker one. The general supersingular isogeny problem is equivalent to the problem of computing the endomorphism ring of a given supersingular elliptic curve. The primary research goal for this project is to design and analyze algorithms for computing the endomorphism ring of a supersingular elliptic curve. The second theme of the project aims to determine the expansion properties of isogeny graphs whose mixing rates have yet to be determined. These generalizations of isogeny graphs could have cryptographic applications so it is important to study their expansion properties.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.