Collaborative Research: CISE-ANR: FET: Small: Complexity theory aspects of quantum cryptography

Quantum computing offers the ability to unlock cryptographic advancements that are beyond the reach of existing security technologies. This includes not only strengthening the mathematical foundations of existing cryptographic schemes but also enabling entirely new cryptographic concepts. This project seeks to chart a clearer understanding of the complexity-theoretic foundations that underlie quantum cryptographic systems. The resulting insights will help in precisely characterizing the mathematical assumptions needed for quantum cryptographic primitives. The project also aims to develop new protocols and techniques for secure interaction with quantum information, including ways to verify and protect quantum information. Such protocols could potentially lead to applications of quantum computers and quantum networks in the future. In addition to contributing to foundational science, the project will support educational activities, outreach, and international collaboration. The project undertakes a broad theoretical study of the complexity assumptions and structural underpinnings of quantum cryptography. It aims to clarify the hierarchy of quantum cryptographic primitives and determine which assumptions are necessary or sufficient for constructing various protocols. The research will explore idealized models such as the quantum random oracle model, the common Haar state model, and the Haar random oracle model, in order to probe feasibility and impossibility results. The investigators will also analyze complexity-theoretic reductions and separations between different cryptographic primitives, and employ recently developed unitary complexity theory to better understand their security. A further goal is to design new quantum cryptographic protocols, including interactive and zero-knowledge protocols for preparing quantum states, and to explore notions such as proofs of quantum knowledge. By pursuing these directions, the project seeks to build a coherent, complexity-theoretic framework for 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.