Conversable Quantum Fire in the Standard Model

AI summary

Overview

Research area: Quantum cryptography and quantum information theory, specifically the primitive known as quantum fire, its instantiation from one-shot signatures, and its use for publicly certifiable min-entropy.

Technical level: Advanced. The paper is a theorem-and-proof cryptography paper that assumes familiarity with quantum computing, one-shot signatures, min-entropy, oracle models, and reduction-based security proofs.

Scope: The paper gives the first provably untelegraphable quantum-fire construction in the standard model (assuming one-shot signatures), introduces and achieves the stronger notions of keyless untelegraphability and conversability, and applies these properties to build publicly certifiable, classically transferable min-entropy.

What This Paper Is About

Quantum fire is a quantum state that can be efficiently functionally cloned (spread like fire) but cannot be reconstructed from any classical description sent over a one-way classical channel (it is untelegraphable). Every earlier construction with a proof of untelegraphability relied on an oracle, so the fire was never "domesticated" into the standard model. This paper builds quantum fire from one-shot signatures in the standard model, shows it has two new properties (keyless untelegraphability and conversability), and uses them to obtain a cryptographic application: publicly certifiable min-entropy that can be transferred over classical communication.

Key Contributions

1. First standard-model quantum fire with proven untelegraphability. The construction is based on one-shot signatures (OSS), in contrast with all prior constructions whose untelegraphability proofs were relative to an oracle.

2. Two new security/functionality notions for quantum fire. The authors introduce keyless untelegraphability (no flame can be telegraphed even when both the flame and its serial number are generated by the adversary) and conversability (a flame cannot be sent with one-way classical communication but can be transmitted through classical interaction).

3. Two parameter regimes. A "logarithmic" variant based on standard unforgeable one-shot signatures (instantiable from subexponential iO, subexponentially secure one-way functions, and LWE) supporting polynomially many flames and super-logarithmic min-entropy of the serial-number distribution; and a "linear" variant based on exponentially unforgeable one-shot signatures (instantiable relative to a classical oracle) supporting exponentially many flames and linear min-entropy, with cloning depth up to λ/8.

4. A cryptographic application. A publicly certifiable, classically transferable min-entropy scheme, plus a modified version with a classical verifier (under the added assumption that the OSS has classically generable verification keys), which sacrifices transferability.

Main Findings

• Main Result 1 (Theorem 1.1, Corollary 1): One-shot signatures, for which standard-model constructions exist, imply keyless untelegraphable quantum fire. This is strictly stronger than ordinary untelegraphability.
• Main Result 2 (Theorem 1.2): The quantum fire scheme of Construction 1 is conversable — a valid flame can be sent using only interactive classical communication despite being untelegraphable one-way.
• Main Result 3 (Theorem 1.3, Corollary 3): There is a publicly certifiable, classically transferable min-entropy scheme in which the number of sequential transfers is bounded by the cloning depth of the underlying conversable quantum fire.
• Bounded cloning depth: In the logarithmic variant, Clone may be repeated at most c·log(λ) times along any root-to-leaf path, for a constant c fixed in advance; in the linear variant, at most λ/8 times. The paper states in Proposition 1 that this restriction is unavoidable in their construction (Theorem 3.2 covers the bound).
• Keyless untelegraphability forces entropy (Theorem 3.3): Serial numbers produced by Spark must have high min-entropy. If the min-entropy were only logarithmic, the most probable serial number s* would occur with probability Ω(λ^{-c}), so two independent runs of the adversary would both output s* with probability at least Ω(λ^{-2c}), contradicting keyless untelegraphability. Theorem 3.4 gives the analogous linear-variant statement.
• Proof technique for untelegraphability: A hypothetical telegraphing adversary is converted into an OSS forger that runs the receiver λ^c + 1 times; each run yields a signature chain from the serial number, forming a tree with out-degree at most two and at most λ^c leaves. By the pigeonhole principle two chains end at the same leaf, giving two signing tokens for the same verification key — an OSS forgery.
• Cost of the linear variant: The reduction may need to generate roughly 2^{λ/8} chains, so the resulting forger runs in time Õ(2^{λ/8}), which is ruled out by sufficiently strong exponential unforgeability.
• Conversability protocol: Bob generates (pk_B, sk_B) and sends pk_B; Alice generates (pk_A, sk_A), signs the pair (pk_A, pk_B) with her quantum signing key, appends the signed message to the chain, and sends the serial number and chain to Bob. Bob already holds his quantum key locally, so no quantum state is ever transmitted. The protocol can be repeated sequentially for logarithmically many rounds in the logarithmic variant and up to λ/8 rounds in the linear variant.
• Clones need only be functional: The two flames output by Clone may be far apart in trace distance or computational distinguishability (indeed they can be efficiently distinguished in this construction), but both pass verification with the original serial number.
• Comparison with prior work (Table 1): The table compares known constructions on model (unitary, quantum oracle, classical oracle, standard), public-key versus keyless, assumptions, provable untelegraphability, conversability, unconversability, and keyless untelegraphability. This work is the only standard-model entry, the only one marked as keyless untelegraphable, and the only one marked conversable; the Çakan–Goyal–Shmueli construction is marked unconversable, and the Bostanci–Nehoran–Zhandry candidate is marked as not provably untelegraphable.
• Empirical evaluation: The paper reports no experiments, benchmarks, datasets, or empirical measurements; all claims are theorems and reductions. The paper content provided is truncated partway through Section 2, so later formal statements are not available here.

Methodology in Plain English

The authors start from a one-shot signature scheme, where a quantum signing token can be used to sign one message and it is computationally hard to produce two valid signatures under the same verification key. They identify a serial number with an OSS verification key and the fire state with the quantum signing token. Cloning cannot mean copying the token (that would break the signature scheme); instead, the cloner creates two fresh OSS key pairs, signs the two new verification keys with the old token, and hands one new token plus the authenticated chain to each child. Repeated cloning builds an authenticated binary tree of verification keys rooted at the serial number, and each flame is a root-to-leaf chain together with the quantum token at the leaf. Verification checks every link of the chain and checks that the quantum register is a valid token for one of the two keys in the last link.

To argue that no one-way classical message can replace the flame, they show that a successful telegraphing adversary could be run many times to produce many chains; since the tree is binary and shallow, two chains must collide at a leaf, yielding two tokens for one key, which breaks the signature scheme. For conversability, they let the receiver generate its own key pair first and send only the public key; the sender then signs a pair containing that public key, so the receiver ends up holding a valid token and chain without any quantum transmission. Finally, they turn the entropy forced by keyless untelegraphability plus the ability to hand over a flame by conversation into a certification protocol for min-entropy.

Why This Matters

Impact on research. The no-cloning and no-telegraphing theorems are central no-go results in quantum information. Quantum fire is the object that separates them. Moving that separation from oracle-based constructions into the standard model, and adding the qualitative one-way-versus-two-way classical communication distinction, changes quantum fire from an oracle-model curiosity into a primitive usable inside standard cryptographic reductions. The paper also supplies one of the first constructive applications of quantum fire, and shows that publicly certifiable min-entropy with polynomial-time verification can be obtained in the standard model rather than in the random oracle model or with an exponential-time verifier.

Potential applications (as discussed in the paper):

• Publicly certifiable min-entropy: a prover can convince others that a string was produced by an algorithm whose output distribution has high min-entropy, with polynomial-time verification.
• Transferable public certification: an accepting verifier obtains a quantum witness and can itself act as a prover to certify the same statement onward, with each transfer consuming one level of cloning depth, over a classical channel.
• Key-exfiltration prevention: cited in the paper as an application previously mentioned in the literature for quantum fire.
• Randomness for cryptographic key generation: the paper distinguishes private from public certified randomness and notes privacy matters when the randomness is used for private key generation, a setting adjacent to its public certification result.

Industry relevance. The results bear on verifiable randomness services, cryptographic key generation and key-management architectures where exfiltration resistance matters, and any setting that needs a classical, transferable proof that a value came from a high-entropy source. The paper notes prior blockchain-related use of the underlying signature-chain delegation mechanism in the work of Amos, Georgiou, Kiayias, and Zhandry. All of this remains theoretical: the standard-model instantiation inherits strong assumptions (subexponential iO, subexponentially secure one-way functions, LWE) and the linear-min-entropy regime relies on exponential unforgeability that is currently known only for an oracle-relative construction.

Future Directions

• From min-entropy to uniform randomness. The paper's open-problems section asks whether public certifiability of min-entropy can be strengthened toward publicly certifiable uniform randomness, and as an intermediate question whether some form of entropy accumulation can be achieved (the authors explicitly do not prove an accumulation result).
• Unbounded clonability. The strongest scheme allows at most a linear number of sequential Clone operations, and Proposition 1 shows this restriction is unavoidable in their construction. Whether standard-model conversable quantum fire can permit any polynomial number of sequential clones is left open, noting that the oracle-relative construction of Çakan, Goyal, and Shmueli allows any number.
• Classical-verifier certification with transferability. The modified construction with a classical verifier loses transferability because the verifier never obtains the quantum witness; recovering both properties at once is an evident target.
• Standard-model exponential unforgeability. The linear-min-entropy result is a standard-model reduction from exponentially unforgeable one-shot signatures, but such exponential unforgeability is known for the oracle-relative construction of Shmueli and Zhandry and, to the authors' knowledge, not for any standard-model one-shot signature scheme.

Target Audience

Researchers in quantum cryptography and theoretical computer science working on quantum fire, one-shot signatures, quantum money and quantum lightning, certified randomness, and oracle separations. It is also relevant to cryptographers interested in standard-model constructions and in the interplay between one-way and interactive classical communication. Readers without a background in quantum-secure reductions will find the technical sections difficult, although the introduction and Table 1 give an accessible map of how the constructions compare.

Authors’ abstract

Quantum fire consists of quantum states that can be efficiently functionally cloned but cannot be transmitted using one-way classical communication. Whereas all previous quantum-fire constructions with proven untelegraphability are relative to an oracle, ours, based on one-shot signatures, is in the standard model. Our construction achieves two further notions that we introduce: (a) keyless untelegraphability, a strengthening of untelegraphability; and (b) conversability, meaning that a flame, though not telegraphable via one-way classical communication, can be transmitted via classical interaction. Hence one-way and two-way classical communication differ qualitatively in their power to transmit this quantum fire. We use these two novel properties of quantum fire, along with its clonability, to give one of the first cryptographic applications of quantum fire. Keyless untelegraphability forces the distribution of serial numbers of valid flames to have high min-entropy, while conversability and clonability allow the corresponding flame to be cloned and transferred using only classical communication. We present two variants of our conversable quantum-fire construction. The first, based on one-shot signatures (instantiable from subexponential iO, subexponentially secure one-way functions, and LWE), supports polynomially many flames, and super-logarithmic min-entropy of the serial-number distribution. The second, under the stronger assumption of exponentially unforgeable one-shot signatures (instantiable relative to a classical oracle), supports exponentially many flames, and linear min-entropy.