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

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

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.