CAREER: Foundations of Post-Quantum and Quantum Cryptography

Quantum computing poses both a fundamental threat to existing classical cryptography and an exciting opportunity to develop new forms of cryptography. This project aims to provide a theoretical foundation for constructing and analyzing cryptographic primitives and protocols in these two contexts, known as post-quantum cryptography and quantum cryptography. The project centers on two main questions. First, are there post-quantum (i.e., quantum-safe) instantiations of our most important cryptographic primitives and protocols, and can their security be justified under simple, well-understood assumptions? Second, to what extent does quantum computing enable quantitatively and qualitatively better security for basic cryptographic tasks? Answering these questions would increase confidence in the security of our internet infrastructure as breakthroughs in quantum computation continue. The project also includes plans to develop new courses and public course materials integrating quantum computation into computer science education, mentor undergraduate and graduate students, and organize local workshops and colloquia on cryptography and quantum computing. The project includes the following specific goals. First, it aims to establish the post-quantum security of poorly understood primitives such as hash functions and succinct non-interactive arguments based on well-studied computational hardness assumptions. Second, it aims to develop techniques for establishing quantitatively strong, concrete post-quantum security of cryptographic primitives without any reliance on heuristics. Third, it aims to understand the feasibility and complexity-theoretic requirements of “quantum nanocrypt,” a collection of cryptographic tasks that may be secure even if an attacker has the power to perform any classical computation instantaneously. Finally, it aims to establish tight quantitative resource tradeoffs for breaking this “inherently quantum” cryptography. 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. NSF Award ID: 2541300 | Program: 01002627DB NSF RESEARCH & RELATED ACTIVIT,01002930DB NSF RESEARCH & RELATED ACTIVIT,01003031DB NSF RESEARCH & RELATED ACTIVIT | Principal Investigator: Alex Lombardi | Institution: Princeton University, PRINCETON, NJ | Award Amount: $364,398 View on NSF Award Search: https://www.nsf.gov/awardsearch/show-award/?AWD_ID=2541300 View on Research.gov: https://www.research.gov/awardapi-service/v1/awards/2541300.html