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

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 showed how to construct quantum fire relative to an inefficient quantum oracle (which cannot be instantiated even heuristically). Later, Bostanci, Nehoran, Zhandry gave a candidate construction based on group actions, however, even in the classical oracle model they could only conjecture the security of their scheme, and were not able to give a security proof or argue security.

In this work, for the first time, 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 quantum fire, and we give secure constructions for these notions.

• We introduce a notion called quantum key-fire where the clonable fire states serve as keys:

They can be used to evaluate a functionality (such as a signing or decryption key), and for security we require unbounded leakage-resilience, which means that given the fire state, the key cannot be efficiently converted into a classical string.

• We consider the notion of interactive (i.e. LOCC) security for quantum (key-)fire. In this setting, instead of trying to convert the state or key into a classical string; the adversary, given the flame state, attempts to transfer it to another adversary interactively over a classical channel.

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 separation in the computational universe between two fundamental principles of quantum mechanics: No-cloning and no-teleportation, which are equivalent in the informationtheoretic setting.

• A separation between copy-protection security (Aaronson, CCC'09) and unbounded/LOCC leakage-resilience security (C ¸akan, Goyal, Liu-Zhang, Ribeiro, TCC'24).

• A separation between computational no-cloning security and computational no-learning security, two notions introduced recently by Fefferman, Ghosh, Sinha, Yuen (ITCS'26).

In all our constructions, the oracles can be implemented efficiently using one-way functions. Thus, our schemes can be heuristically instantiated in the plain model using one-way functions and indistinguishability obfuscation, which gives us the first constructions in the plain model with concrete evidence for their security.