Computational Hardness in Quantum Cryptography
Abstract
An important goal of modern cryptography is to build cryptographic protocols from generic hardness assumptions, which abstract out certain key properties of mathematical problems. This allows us to substitute one mathematical problem for the other without changing any of the theory. While we have developed a solid understanding of the assumptions that enable classical cryptography over the past several years, we lack an understanding of the hardness required to realize cryptography with quantum participants. At the same time, recent exciting research has demonstrated that unique properties of quantum information can sometimes be exploited to base quantum protocols on weaker computational hardness assumptions than their classical counterparts. The proposed research will initiate a systematic study of the generic hardness assumptions that enable quantum cryptography, with the goal of providing firm foundations for quantum protocol design. This will involve (1) understanding simple assumptions that are necessary and sufficient to realize core quantum cryptographic tasks, (2) analyzing the relationship between search and decision problems relevant to quantum cryptography, and (3) establishing new techniques to reason about quantum protocols and adversaries. We will investigate several natural search assumptions about the hardness of finding keys that yield specific quantum states. We will aim to understand whether these are necessary and sufficient to build useful quantum cryptosystems including bit commitments, encryption, digital signatures and secure computation protocols. Techniques developed as part of this research will build foundations for the rapidly emerging area of quantum cryptography. We anticipate that these methods will be broadly applicable even beyond the proposed work, and will help the nation strengthen its cybersecurity infrastructure.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Mar 06, 2024
- Source ID
- FA95502310543
Entities
People
- Dakshita Khurana
Organizations
- Air Force Office of Scientific Research
- United States Air Force
- University of Illinois Urbana–Champaign