Public-Key Quantum Fire and Key-Fire From Classical Oracles

Abstract

Quantum fire is a distribution of quantum states that can be efficiently cloned, but cannot be efficiently converted into a classical string. First considered by Nehoran and Zhandry (ITCS'24) and later formalized by Bostanci, Nehoran, Zhandry (STOC'25), quantum fire has strong applications and implications in cryptography, along with important connections to physics and complexity. However, constructing and proving the security of quantum fire so far has been elusive. Nehoran and Zhandry gave a construction relative to an inefficient quantum oracle. Later, Bostanci et al gave a candidate construction based on group actions, however, even in the oracle model they could only conjecture the security of their scheme, and were not able to prove security. In this work, we give a construction of public-key quantum fire relative to a classical oracle and prove its security unconditionally. Going further, we introduce two stronger notions that generalize it: Quantum key-fire where the clonable fire states serve as keys, and interactive (i.e. LOCC) security for quantum (key-)fire. We give a construction of quantum key-fire relative to a classical oracle and unconditionally prove that it satisfies interactive security for any unlearnable functionality. As a result, we also obtain the first classical oracle separations between various notions in physics and cryptography: *** A computational separation between two fundamental principles of quantum mechanics: No-cloning and no-teleportation, which are equivalent in information-theoretically. *** A separation between copy-protection security (Aaronson, CCC'09) and LOCC leakage-resilience security (Cakan, Goyal, Liu-Zhang, Ribeiro, TCC'24). *** A separation between computational no-cloning security and no-learning security, two notions introduced recently by Fefferman, Ghosh, Sinha, Yuen (ITCS'26).