Barak Nehoran will present his FPO "Separations of Fundamental Quantum Properties and Their Role in Shaping Cryptography Beyond Classical Limits" on October 9, 2025 at 12:30pm in CS 402.
Examiners: Ran Raz (adviser), Mark Zhandry (adviser), and Alex Lombardi
Readers: Gillat Kol and Sarang Gopalakrishnan
All are welcome to attend. Please see abstract below.
Quantum computers will break much of the cryptography that secures the internet, but they will also enable entirely new cryptographic frameworks with security based on the principles of quantum mechanics. Quantum mechanics prevents certain information processing tasks: unlike classical data, quantum information cannot generally be recognized, cannot be written down on paper (formally called “telegraphed”), and cannot be copied (formally, “cloned”). Some quantum information classicizes, or resembles its classical counterpart, by allowing one or more of these tasks, while other information remains fully quantum and resists all such classicizing tasks. We argue that differences between such classicizing tasks, especially cases when one task is efficient but another is not, are essential for enabling quantum cryptography with no classical analog.
The earliest quantum cryptography explored was quantum money, which is quantum information that can be recognized efficiently but not cloned. Wiesner first defined it in 1968, with a public-key version introduced by Bennett, Brassard, Breidbart, and Wiesner in 1982. Many proposals for public-key quantum money have appeared over the past 43 years, yet proving the security of any of them has remained challenging. We use new tools from the mathematics of group representations and group actions to give the first secure construction of public-key quantum money that does not rely on obfuscation, and the first to also offer collision resistance. We also introduce quantum fire, which describes quantum information that can be cloned efficiently but not telegraphed. Like fire, it can be spread indefinitely from a single source, but only as long as it is kept alive. We provide a secure construction of quantum fire in the black-box setting and give a framework for a potential construction in the plain model. We further show that classicizing tasks can also characterize complexity classes involving efficient quantum verification, offering a new perspective on the fundamental question of the relative power of classical and quantum proofs.