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

职业：加速计算超奇异椭圆曲线同构和自同态的算法

• 批准号: 2340564
• 负责人: Travis Morrison
• 金额: $ 45.86万
• 依托单位: Virginia Polytechnic Institute and State University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2024
• 资助国家: 美国
• 起止时间: 2024-07-01 至 2029-06-30
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2340564&HistoricalAwards=false
• 关键词: CAREER; Accelerating; Algorithms; Computing; Isogenies

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.

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