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

点击翻译按钮获取中文摘要

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.