PaperlayerView exact revision on arXiv

Source-linked AI summary

Conversable Quantum Fire in the Standard Model

Ofer Casper, Barak Nehoran, Or Sattath

arXiv:2609.36335v1quant-phcs.CR

TL;DR

Prior quantum-fire constructions with proven untelegraphability required an oracle; this work gives a one-shot-signature-based construction in the standard model. It adds keyless untelegraphability and conversability, and uses them with clonability to support classical transfer of flames and min-entropy certification.

  • Problem

    Previously, proven untelegraphability for quantum fire was achieved only relative to an oracle, leaving a standard-model construction unprovided.

    Source: §1 · p. 2

  • Method

    The construction uses one-shot signatures to combine keyless untelegraphability with conversability, allowing flames to be transmitted through classical interaction.

    Source: §1 · p. 3

  • Results

    One-shot signatures imply keyless untelegraphable quantum fire, and the construction is conversable despite its untelegraphability.

    Source: §1 · p. 3

  • Takeaways & Limitations

    Keyless untelegraphability gives the serial-number distribution high min-entropy, while conversability and clonability support classical transfer of the witnesses used for certification.

    Source: §1 · p. 4

    The main transferability construction requires a quantum verifier; the classical-verifier modification requires classically generable verification keys and loses transferability.

    Source: §1 · p. 4

Abstract

from arXiv · show

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.

1 Introduction

The introduction presents a standard-model construction of clonable but untelegraphable quantum fire, including keyless untelegraphability and interactive conversability, and explains how these properties enable publicly certifiable min-entropy with classical communication. It situates this goal among prior randomness-generation approaches, identifies open questions about stronger randomness guarantees and clonability, distinguishes the work from quantum lightning, and notes that it does not establish entropy accumulation.

1 Introduction

  • One-shot signatures imply keyless untelegraphable quantum fire, giving the first provably untelegraphable construction in the standard model.Earlier constructions with proven untelegraphability were oracle-relative [10]; a candidate construction’s untelegraphability remained unproved.Source: §1 · p. 2
  • The logarithmic variant permits depth c log(λ) and polynomially many flames under ordinary unforgeability, while the linear variant permits depth λ/8 and exponentially many under exponential unforgeability.The variants differ in their underlying signature assumption and maximum cloning depth.Source: §1 · p. 2
  • Keyless untelegraphability rules out one-way transmission even when an adversary generates both the flame and serial number, and forces high min-entropy in valid serial numbers.The technical overview derives super-logarithmic min-entropy for efficiently generated valid flames in the logarithmic variant, and linear min-entropy for the linear construction under exponential unforgeability.Source: §1 · p. 3, §1.1 · p. 7
  • Conversability allows a sender to help a receiver obtain a valid flame with the same serial number through interactive classical communication, even though one-way classical telegraphing is impossible.The receiver generates its quantum signing key locally; the sender authenticates that key as a descendant of her flame without sending a quantum state.Source: §1 · p. 3, §1.1 · p. 7
  • Keyless untelegraphability supplies high-entropy serial numbers, while clonability and conversability let witnesses and certifications spread through classical communication, yielding publicly certifiable min-entropy.The scheme supports sequential classical transfers bounded by the fire’s cloning depth; each accepting verifier obtains a quantum witness to act as a prover.Source: §1 · p. 4, §1.1 · p. 7
  • A modified construction supports a classical verifier under an additional assumption of classically generable verification keys, but the verifier cannot transfer certification onward.Without the quantum signing witness, the verifier cannot subsequently act as a prover.Source: §1 · p. 4, §1.1 · p. 8

1.1 Technical Overview

  • The construction implements functional cloning with an authenticated binary tree of one-shot-signature verification keys, where each flame carries a root-to-leaf chain and a signing key for its leaf.Clones need only pass verification under the original serial number; they need not be information-theoretically identical copies.Source: §1 · p. 2, §1.1 · pp. 5–6

1.2 Related Work

  • The work combines standard-model quantum fire with polynomial-time verification for public min-entropy certification; linear min-entropy additionally assumes exponentially unforgeable one-shot signatures, known from an oracle-relative construction.The authors state that such exponential unforgeability is not currently known for a standard-model one-shot signature scheme.Source: §1.2 · p. 10
  • Randomness expansion for a classical verifier uses either spatially separated non-signaling devices or one untrusted quantum device under a computational hardness assumption.The device-independent approach seeks a longer private string that is close to uniform or terminates when devices misbehave; the single-device approach was introduced in.Source: §1.2 · p. 11
  • This work does not prove min-entropy accumulation, instead arguing directly about the resulting protocol and leaving accumulation to future work.Accumulation concerns min-entropy generated by repeating sub-protocols that produce small amounts of entropy.Source: §1.2 · p. 11
  • Quantum lightning yields private certified min-entropy from bolt serial numbers, whereas this work provides publicly certifiable min-entropy transferable over classical channels.Quantum lightning is defined as a collision-free version of public-key quantum money.Source: §1.2 · p. 11

1.3 Open Problems

  • Can public certification of min-entropy be strengthened toward uniform randomness, and can entropy accumulation be achieved?The protocols certify that a string was generated by an algorithm with high min-entropy, but do not certify uniform randomness.Source: §1.3 · pp. 11–12
  • The strongest scheme permits only linearly many sequential Clone operations, an unavoidable restriction for this construction; can standard-model conversable quantum fire support polynomially many?The oracle-based construction in Ref. [10] allows any number of Clone operations.Source: §1.3 · p. 12

2 Definitions, Notation, and Preliminaries

This section establishes notation and preliminaries for one-shot signatures and quantum fire. It introduces the signature algorithms and the quantum-fire operations, including clonability and the stronger keyless untelegraphability notion.

2 Definitions, Notation, and Preliminaries

  • The notation distinguishes quantum algorithms, classical algorithms, quantum states, and classical variables; security parameters are assumed as inputs even when omitted.The paper also defines non-⊥ min-entropy and notes a relation between high min-entropy and sampled Kolmogorov complexity, which it does not further study.Source: §2 · p. 12

2.1 One-Shot Signatures

  • A one-shot signature scheme uses KeyGen, Sign, VerSign, and VerToken, with a quantum signing token and classical signatures and verification.KeyGen outputs a verification key and signing token; Sign produces a classical signature, VerSign checks it, and VerToken checks the token.Source: §2.1 · pp. 12–13
  • VerToken acceptance equals the probability that signing a uniformly random message yields a signature accepted by VerSign.The preliminaries separately state completeness and unforgeability, including exponentially h-unforgeability.Source: §2.1 · p. 13

2.2 Quantum Fire

  • A quantum-fire scheme consists of Spark, Clone, and Verify: Spark produces a serial number and flame, Clone produces two registers, and Verify accepts or rejects an alleged flame.The definitions also introduce a keyless variant, analogous to quantum lightning in having no private key.Source: §2.2 · p. 14
  • Clonability is defined through sequential Clone operations, with one-time clonability corresponding to a single operation.The scheme may also track how many Clone operations remain for a flame.Source: §2.2 · p. 14
  • The paper uses keyless untelegraphability, a stronger notion than the original untelegraphability definition, rather than the original notion itself.The untelegraphability game is defined for non-entangled QPT adversaries.Source: §2.2 · p. 14

C A B

This section defines keyless untelegraphability and conversability, then sets out publicly certifiable min-entropy schemes and their transferability. These properties capture how flames can remain untransmittable one-way while supporting classical-interaction certification and transfer.

C A B

  • Keyless untelegraphability is a stronger security notion than standard untelegraphability, with the adversary allowed to generate both the flame and its serial number.The definition changes the security game; the ordinary notion follows by choosing the serial number honestly.Source: C A B · p. 15
  • Conversability permits a flame to be sent through one-round classical interaction, even though one-way classical communication cannot transmit it.The Converse protocol has the receiver send preparation data, the sender return a deconstructed classical string and verification key, and the receiver reconstruct the flame.Source: C A B · p. 16

2.3 Publicly Certifiable Min-Entropy over Classical Communication

  • A publicly certifiable min-entropy scheme uses GenEntropy, CloneWitness, and CertEntropy, with certification conducted over classical communication between a quantum prover and verifier.Certification returns an acceptance bit, a classical serial number, and a quantum witness; CloneWitness produces two quantum witnesses for a serial number.Source: §2.3 · pp. 16–17
  • High min-entropy means at least c · log(λ) min-entropy for every constant c, while linear min-entropy means at least c · λ for some constant c.Linear min-entropy implies high min-entropy, but not necessarily vice versa.Source: §2.3 · pp. 16–17
  • c-transferability requires sequential certification runs in which each run's output state becomes the prover's witness for the next round.The scheme's clonability and certification protocol are specified separately from this transfer condition.Source: §2.3 · p. 17

3 Conversable Quantum Fire from One-Shot Signatures

This section uses one-shot signatures to construct conversable quantum fire, establishing keyless untelegraphability, conversability, and decomposability under standard-model assumptions, with logarithmic or linear clonability under differing unforgeability assumptions. It also derives min-entropy consequences and examines how removing the chain-length bound affects keyless untelegraphability.

3 Conversable Quantum Fire from One-Shot Signatures

  • Unforgeable one-shot signatures yield logarithmically clonable keyless-untelegraphable, conversable fire; exponentially h-unforgeable signatures for h > 1/8 yield the λ/8-clonable linear variant.Correctness, conversability, and clonability follow from one-shot signature correctness.Source: §3 · pp. 19, 21, 22
  • A chain-length bound is necessary generically: an unforgeability-preserving OSS′ makes Construction 1 with c(λ) = λ telegraphable with probability 1.The counterexample adds verification rules for special keys, enabling adversaries to construct a valid chain without communicating.Source: §3 · pp. 22–23
  • Keyless untelegraphability implies high min-entropy for quantum fire, and conversable fire inherits the same min-entropy notion.The proof uses a low-entropy serial-number distribution to construct adversaries that win the keyless untelegraphability game with non-negligible probability.Source: §3 · pp. 23–24
  • Exponentially 1/3-unforgeable signatures give Construction 1 with c(λ) = λ/8 min-entropy of at least λ/8.More generally, with clonability c(λ) = ℓ·λ and min-entropy e·λ, the stated condition is ℓ + e < h for exponentially h-unforgeable signatures.Source: §3 · pp. 24–25
  • The section introduces decomposable fire: a flame has two classical registers and one quantum register, with PPT algorithms for preparation, reconstruction, and verification.This variant has a classical receiver in the Converse protocol.Source: §3 · p. 25
  • Lemma 1 establishes that min-entropy is preserved when moving from conversable quantum fire to decomposable fire.Its proof equates the non-⊥ output distributions of the two verification procedures.Source: §3 · pp. 25–26
  • For any complete one-shot signature scheme with a classical key-generation algorithm, Construction 1’s fire is decomposable.The decomposition uses classical key generation for CPrepare; CVerify checks the classical data, and CRecon reconstructs while disregarding the quantum state.Source: §3 · p. 26
  • Under subexponentially secure iO, subexponentially secure OWF, and polynomially secure LWE with a subexponential noise-modulus ratio, Construction 1(a) instantiated with the one-shot signature scheme of is a keyless untelegraphable, conversable, decomposable quantum fire scheme.Source: §3 · p. 27

4 Publicly Certifiable Min-Entropy over Classical Communication from Conversable Quantum Fire

The section turns conversable quantum fire into publicly certifiable min-entropy schemes. The construction supports repeated classical transfers, while a classical certifier can preserve min-entropy under decomposability but does not provide transferability.

4 Publicly Certifiable Min-Entropy over Classical Communication from Conversable Quantum Fire

  • A c(λ)-clonable conversable quantum fire with high min-entropy yields a publicly certifiable, c(λ)-transferable min-entropy scheme.Witness clonability follows from fire cloning correctness, while transferability and public certifiability follow from conversability.Source: §4 · p. 28
  • An unforgeable one-shot signature scheme yields a publicly certifiable scheme with at least super-logarithmic min-entropy and c log(λ)-transferability for any fixed constant c.With a 1/3-exponentially unforgeable signature scheme, the result has at least linear min-entropy and λ/8-transferability.Source: §4 · p. 29
  • Classical certification does not yield transferability because the certifier receives no quantum witness, and this variant requires decomposable conversable fire.An unforgeable one-shot signature scheme with classically generable verification keys implies a classically certifiable scheme with high min-entropy.Source: §4 · pp. 29–30
  • Construction 4 replaces quantum certification with a classical certifier for decomposable conversable fire, and the resulting scheme retains the underlying min-entropy.The classical protocol uses preparation, reconstruction, and verification steps; correctness is established when the fire scheme is correct and decomposable.Source: §4 · pp. 29–30

A A Visual Representation of One-Shot Signatures, Conversable Quantum Fire, and the Conversable Quantum Fire Construction from One-Shot Signatures

The appendix provides an informal graphical presentation of Construction 1 and its constituent primitives.

A A Visual Representation of One-Shot Signatures, Conversable Quantum Fire, and the Conversable Quantum Fire Construction from One-Shot Signatures

A.1 Legend

Figure 1 defines a graphical notation for the appendix. Colored squares represent classical strings, with different colors distinguishing different strings.

A.1 Legend

  • Figure 1 establishes the graphical language used in the appendix’s illustrations.Source: §A.1 · p. 33
  • Colored squares represent classical strings, including public keys and serial numbers.Source: Figure 1 · p. 33
  • Different colors denote different classical strings.Source: Figure 1 · p. 33

A.2 Algorithms and Security Games

Figures 2 and 3 depict the syntax of one-shot signatures and quantum fire, while Figures 4 and 5 depict their security definitions.

A.2 Algorithms and Security Games

  • Figures 4 and 5 graphically represent one-shot-signature unforgeability and keyless untelegraphability, respectively.Source: §A.2 · p. 33
  • Figure 2 presents one-shot-signature syntax, with an honestly generated signature and its public key sharing a color.Source: Figure 2 · p. 34
  • Figure 3 presents quantum-fire syntax, with an honestly generated flame and its serial number sharing a color.Source: Figure 3 · p. 34
  • Figure 4 illustrates one-shot unforgeability: an adversary choosing the verification key should not produce two different accepted messages under it.Source: Figure 4 · p. 35

Verify

Figure 5 states the keyless-untelegraphability criterion: no efficient pair of adversaries can make the referee accept with non-negligible probability.

Verify

  • Keyless untelegraphability requires that no efficient pair of adversaries make the referee accept with non-negligible probability.Source: Figure 5 · p. 36

A.3 From one-shot signatures to conversable quantum fire

Figures 6–9 illustrate Spark, Clone, Verify, and Converse in the construction from unforgeable one-shot signatures.

A.3 From one-shot signatures to conversable quantum fire

  • Spark uses the one-shot signature public key as the flame’s serial number.Source: Figure 6 · p. 37
  • Clone produces two flames that retain the original serial number, although their new one-shot signatures differ.Source: Figure 7 · p. 38
  • Verify checks the validity of each cloned flame’s branch and enforces a maximum branch depth.The depth bound is logarithmic for Construction 1(a) and linear for Construction 1(b).Source: Figure 8 · p. 39
  • After Converse, the binary signatures tree resembles the cloning tree, although its leaves are held by different parties.Source: Figure 9 · p. 40
Loading 2609.36335v1…