SaTC: CORE: Small: New Directions in Post-Quantum Multivariate Cryptography

The development of quantum computing and the power of quantum algorithms to quickly solve prime factoring problems pose new risks for widely deployed cryptographic algorithms. Thus, it is imperative to build cryptographic schemes based on mathematical problems that are believed to be resistant to the capabilities of quantum computing. One of the leading mathematical areas under study for achieving post-quantum security is based on the hardness of solving systems of quadratic equations over a large number of variables, over finite fields. The purpose of this research project is to investigate this area from a foundational perspective, both to expand the cryptographic utility of such systems of equations, and to investigate new quantum algorithms and their impact on the security of such systems of equations. The project also continues efforts with the Prison Math project and the creation of educational videos in the area of cryptography. The primary goals of the study are: (1) to propose and study the simplest variations of solving random quadratic equations over finite fields, especially from the perspective of hardness and utility in cryptography; (2) to develop novel quantum algorithms for solving certain systems of quadratic equations over finite fields, to better understand the boundary between the kinds of problems that are hard for quantum computing and those that are easy for quantum computing; (3) to develop novel public-key cryptosystems whose security is based on solving systems of quadratic equations over finite fields; (4) to explore the possibility of constructing more advanced cryptography, such as functional encryption, using systems of quadratic equations over finite fields; and (5) to explore targets of opportunity in related research questions that arise from our investigation. 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.