SaTC: CORE: Small: Classical and quantum algorithms for number-theoretic problems arising in cryptography

SaTC：核心：小：密码学中出现的数论问题的经典和量子算法

• 批准号: 2001470
• 负责人: Kirsten Eisentraeger
• 金额: $ 50万
• 依托单位: Pennsylvania State Univ University Park
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2020
• 资助国家: 美国
• 起止时间: 2020-05-01 至 2025-04-30
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2001470&HistoricalAwards=false
• 关键词: SaTC; CORE; Small; Classical; quantum

This project is concerned with questions in several areas of cryptography. Since currently used cryptosystems can be broken by a quantum computer it is important to develop alternatives to these systems that are resistant to quantum computers. This project will address the classical and post-quantum security of some systems based on supersingular isogenies and of some lattice-based systems that have been proposed as replacements for currently used systems. There seems to be some urgency to achieve this: there has been continued progress in building quantum computers, and it takes several years to design, build, and deploy a new quantum secure infrastructure. Another part of the project deals with making cryptosystems more efficient. These are important practical questions. In addition this project will provide research training opportunities for graduate students. For the educational component, the PI and co-PI will teach middle school girls and students at local high schools about cryptography and its mathematical background. The PI's involvement in groups of women mathematicians will provide support and mentoring for underrepresented groups.The first part of the project is concerned with the classical and post-quantum security of the key-exchange and signature schemes that are based on isogenies of elliptic curves. Several different schemes have been proposed, and one goal is to analyze and compare the underlying hardness assumptions of the different schemes. The project will also address the possibility of generalizing these schemes from supersingular elliptic curves to supersingular abelian varieties of dimension 2. The second part is concerned with making systems that are currently being used more efficient. This will involve finding more efficient algorithms for constructing curves. The last part studies the security of some lattice-based systems. The lattice-based cryptosystem called ``Soliloquy'' was recently broken by a quantum computer. It is important to determine if other lattice-based systems, such as systems based on Ring-LWE, can be broken by quantum computers as well. The Ring-LWE problem is significant because a number of cryptographic constructions, including fully homomorphic encryption, can be based on it.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.

这个项目涉及密码学的几个领域。由于目前使用的密码系统可以被量子计算机破解，因此开发这些系统的替代品非常重要。该项目将解决一些基于超奇异同构的系统和一些基于晶格的系统的经典和后量子安全性，这些系统已被提议作为当前使用的系统的替代品。实现这一目标似乎有一些紧迫性：在构建量子计算机方面一直在不断取得进展，设计、构建和部署新的量子安全基础设施需要几年时间。 该项目的另一部分涉及使密码系统更有效。这些都是重要的实际问题。此外，该项目还将为研究生提供研究培训机会。在教育方面，PI和co-PI将教授中学女生和当地高中的学生密码学及其数学背景。该项目的第一部分是关于基于椭圆曲线同构的密钥交换和签名方案的经典和后量子安全性。已经提出了几种不同的方案，一个目标是分析和比较不同方案的基本硬度假设。 该项目还将解决这些计划从超奇异椭圆曲线推广到超奇异阿贝尔品种的2维的可能性。 第二部分涉及使目前使用的系统更有效率。 这将涉及到寻找更有效的算法来构建曲线。最后一部分研究了一些基于格的系统的安全性。这个名为“独白”的基于格子的密码系统最近被量子计算机破解了。重要的是要确定其他基于晶格的系统，例如基于Ring-LWE的系统，是否也可以被量子计算机打破。 Ring-LWE问题是重要的，因为许多加密构造，包括全同态加密，可以基于它。这个奖项反映了NSF的法定使命，并已被认为是值得通过使用基金会的智力价值和更广泛的影响审查标准进行评估的支持。

项目成果

Computing endomorphism rings of supersingular elliptic curves and connections to path-finding in isogeny graphs

计算超奇异椭圆曲线的自同态环以及与同源图中路径查找的联系

• DOI: 10.2140/obs.2020.4.215
• 发表时间: 2020
• 期刊: Open Book Series
• 作者: Eisenträger, Kirsten;Hallgren, Sean;Leonardi, Chris;Morrison, Travis;Park, Jennifer
• 通讯作者: Park, Jennifer

A TOPOLOGICAL APPROACH TO UNDEFINABILITY IN ALGEBRAIC EXTENSIONS OF Q

解决Q代数扩张中不可定义性的拓扑方法

• DOI: 10.1017/bsl.2023.37
• 发表时间: 2023
• 期刊: The Bulletin of Symbolic Logic
• 作者: EISENTRÄGER, KIRSTEN;MILLER, RUSSELL;SPRINGER, CALEB;WESTRICK, LINDA
• 通讯作者: WESTRICK, LINDA