CAREER: Cryptography from New Assumptions: Encrypted Computation and More

For many years, cryptography has enabled a secure communication infrastructure by relying on the difficulty or "hardness" of solving special mathematical problems. These computational problems, which are hard on average, form the foundational building block of modern cryptography. Yet, despite decades of research studying and leveraging these problems, only a few sources of hardness are commonly used in cryptography. This project is dedicated to a holistic study of new sources of hardness, including: (a) a fundamental exploration of the hardness of new cryptographic assumptions, (b) the design of new techniques to leverage these hard problems for achieving new feasibility results and more efficient cryptographic mechanisms—such as efficient encrypted computation, including multi-party computation and homomorphic encryption — and (c) addressing the severe shortage of assumptions underpinning post-quantum cryptography. The project aims to systematically study the theory and applications of code-based and multivariate cryptography, as well as new assumptions based on point lattices. Additionally, the project aims to advance the use of natural computational problems that arise in the domain of statistical inference for cryptography and the underlying mechanisms (such as low-degree tests and sum-of-squares lower bounds) to rigorously analyze any new assumptions. The investigator devotes time to the Prison Math Project that aims to improve employment prospects and reduce recidivism of individuals upon release from correctional facilities. Additional educational efforts of the investigator should also serve to further bridge the fields of cryptography, complexity theory and statistics. 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.