Source-linked AI summary
Quantum Lightning Never Strikes the Same State Twice
Mark Zhandry
TL;DR
Public-key quantum money is difficult to derive from classical hardness because a reduction that can create one note may be able to create a second without the adversary. The paper combines no-cloning with computational assumptions and develops constructions and security results for quantum money and lightning.
Problem
A reduction proving public-key quantum money secure from a classical assumption may generate two valid notes itself, apparently breaking that assumption without the adversary’s help.
Source: §1 · p. 3Method
The paper combines no-cloning with computational assumptions and develops quantum-lightning constructions and security arguments, including a two-phase proof for money using obfuscated subspaces.
Source: §1 · p. 2, §1.1.2 · p. 7, §1.2 · p. 10Results
The paper gives first public-key quantum-money constructions, win-win security results, and a secure quantum-lightning scheme under Assumption 5.1; Aaronson–Christiano’s signature meets Boneh-Zhandry, not strong Garg-Yuen-Zhandry.
Source: §1.2 · p. 11, §4 · p. 20, §5.2 · p. 37Takeaways & Limitations
Public-key quantum money can be verified locally without mint involvement, while preventing others from creating new notes.
Source: §1 · p. 2The commitment-based lightning result depends on non-interactive commitments; the interactive setting cannot be proved secure because the adversary controls the transcript.
Source: §1.1.2 · p. 7
Abstract
from arXiv · showhide
Public key quantum money can be seen as a version of the quantum no-cloning theorem that holds even when the quantum states can be verified by the adversary. In this work, investigate quantum lightning, a formalization of "collision-free quantum money" defined by Lutomirski et al. [ICS'10], where no-cloning holds even when the adversary herself generates the quantum state to be cloned. We then study quantum money and quantum lightning, showing the following results: - We demonstrate the usefulness of quantum lightning by showing several potential applications, such as generating random strings with a proof of entropy, to completely decentralized cryptocurrency without a block-chain, where transactions is instant and local. - We give win-win results for quantum money/lightning, showing that either signatures/hash functions/commitment schemes meet very strong recently proposed notions of security, or they yield quantum money or lightning. - We construct quantum lightning under the assumed multi-collision resistance of random degree-2 systems of polynomials. - We show that instantiating the quantum money scheme of Aaronson and Christiano [STOC'12] with indistinguishability obfuscation that is secure against quantum computers yields a secure quantum money scheme
1 Introduction
This section examines computationally secure no-cloning through quantum lightning and related quantum-money constructions, including applications and connections to cryptographic primitives. It outlines a conjecture-based construction from degree-2 polynomial hash functions and an obfuscation-based approach, with associated proof strategies and security discussion.
1 Introduction
- A classical-assumption reduction for public key quantum money faces a barrier: if it can generate one valid note, it seems able to generate a second itself.The introduction motivates studying computationally bounded adversaries and the stronger no-cloning goal of preventing duplication even when the adversary controls generation.Source: §1 · pp. 2–4
1.1 This Work: Strong Variants of No-Cloning
- The paper studies strong variants of quantum no-cloning and their relationships to cryptographic applications.The motivating settings include public-key quantum money, verifiable random strings, and computationally bounded adversaries.Source: §1 · p. 2, §1.1 · p. 4
1.1.1 Quantum Lightning Never Strikes the Same State Twice
- Quantum lightning makes banknote generation public while preventing even an adversarial generator from producing two valid bolts with the same serial number.Its security applies even when an efficient adversary chooses how bolts are generated, including by departing from the prescribed procedure.Source: §1.1.1 · p. 4
- Quantum lightning supports verifiable min-entropy strings and decentralized currency whose coins are bolts verified locally without coordination.A bolt’s serial number serves as the random string and proof of min-entropy; currency coins use serial numbers whose hashes begin with a specified number of zeros.Source: §1.1.1 · p. 5
1.1.2 Connections to Post-quantum Security
- For quantum-secure collision-resistant hashes, either the hash is collapsing or it yields quantum lightning without additional computational assumptions.The construction requires parallel repetition to amplify a non-negligible distinguishing advantage, and verification must carefully exclude invalid bolts.Source: §1.1.2 · pp. 6–7
- Quantum-secure computationally binding commitments or Boneh-Zhandry-secure one-time signatures either meet stronger security notions or yield public key quantum money.Non-interactive commitments yield quantum lightning, while interactive commitments yield quantum money; the lightning result relies on non-interactivity.Source: §1.1.2 · p. 7
1.1.3 Constructing Quantum Lightning
- The authors seek standard-model hash functions for quantum lightning, but report finding only one candidate and leave additional candidates as an open problem.Unruh’s counterexample is relative to a quantum oracle and does not provide a candidate construction for the standard model.Source: §1.1.3 · p. 8
- Degree-2 polynomial hash functions are not collision resistant: linearization finds many collisions and can generate repeated copies of the same preimage superposition, defeating the initial scheme.For m ≈ rn, the attack constructs a dimension-r affine space of colliding inputs, or r + 1 colliding inputs without affine relations.Source: §1.1.3 · p. 9
- The authors give the first quantum lightning construction based on a plausible conjecture about a classical problem, using bolts made from repeated copies of a hash preimage superposition.The conjecture rules out 2(r + 1) colliding inputs with no affine relations; producing two verified bolts with the same serial number would yield that many such inputs with overwhelming probability. The scheme can also be modified to obtain a collision-resistant non-collapsing hash function, though not one of degree 2.Source: §1.1.3 · p. 9
1.2 Quantum Money From Obfuscation
- For Aaronson and Christiano’s quantum money scheme [AC12], the proof replaces obfuscated subspaces with larger random subspaces, then uses quantitative no-cloning to rule out forgery.The replacement is shown undetectable using subspace-hiding obfuscation, which is implied by iO; conditioned on the larger subspaces, the hidden banknote subspace is chosen from many possibilities, making cloning negligible.Source: §1.2 · pp. 10–11
- Aaronson and Christiano’s scheme satisfies the Boneh-Zhandry signature definition but not the strong Garg-Yuen-Zhandry notion, separating the two security notions.The authors view the scheme as an instance of their win-win results.Source: §1.2 · p. 11
- The paper’s obfuscation approach may need only subspace-hiding obfuscation, and the authors identify lattice-based constructions as a possible route despite strong quantum attacks on current obfuscators.They also simplify analysis of Aaronson and Christiano’s black-box scheme using unstructured-search lower bounds and their quantitative no-cloning theorem.Source: §1.2 · p. 11, §1.3 · p. 12
1.3 Related Works
- Unlike randomness expansion, quantum lightning uses one computationally bounded device and requires the experimenter to perform quantum operations; public-key quantum money must withstand verification-oracle attacks.The related-work discussion notes that quantum lightning can provide verifiable entropy, since quantum-generated randomness can be shown to another individual to have been random.Source: §1.3 · p. 11
2 Preliminaries
The preliminaries establish notation and a quantum-computation model, then define public-key quantum money through generation, verification, correctness, and resistance to duplication.
2.1 Notations
- The security parameter is λ, represented in unary, and negligible functions are those eventually smaller than every inverse polynomial.Source: §2.1 · p. 12
2.2 Quantum Computation
- Quantum states are vectors over a finite basis; computation uses unit-cost gates and partial measurements, with polynomially many operations considered efficient.The section also introduces product and entangled states, unitary evolution, and measurement in the computational basis.Source: §2.2 · pp. 12–13
2.3 Public Key Quantum Money
- A public-key quantum money scheme generates banknotes and verifies them with serial numbers; verification must accept generated notes, preserve them, and produce essentially deterministic serial numbers.Security requires that a quantum polynomial-time adversary given a note cannot produce two accepted notes with its same serial number except with negligible probability.Source: §2.3 · pp. 14–15
3 Quantum Lightning
Quantum lightning formalizes bolts that can be generated and verified but not duplicated with the same fingerprint. The section relates this security notion to min-entropy and describes applications to verifiable randomness and cryptocurrency, alongside their limits.
3.1 Definitions
- A lightning scheme generates bolts and verifies them while extracting fingerprints; uniqueness requires that an adversarial storm cannot produce two accepted bolts with the same fingerprint.The definition parallels collision resistance: the adversary constructs two bolts, rather than receiving a note first and forging its duplicate.Source: §3.1 · pp. 15–17
- Uniqueness implies min-entropy: if an adversarial generator produced serial numbers with low min-entropy, repeated sampling would yield a repeated serial number and violate uniqueness.Source: §3.1 · p. 18
3.2 Applications
- Quantum lightning can produce random strings with proofs of min-entropy, but the stated guarantee is only super-logarithmic.Setup can be run once and then used to generate arbitrarily many strings with proofs; sub-exponential hardness can raise the guarantee to polynomial min-entropy, potentially still below the string length.Source: §3.2 · pp. 18–19
- Higher min-entropy remains open; a randomness-extractor seed would be part of the verifier description and known to the adversary, who could tailor serial-number distributions against it.Source: §3.2 · p. 19
- For blockchain-less cryptocurrency, a coin is a bolt whose serial-number hash has a prescribed number of leading zeros, making generation require repeated bolt sampling.Source: §3.2 · p. 19
- Without distinguishing old coins from new, improved technology can accelerate coin creation and cause exponentially increasing supply and inflation; raising the zero threshold would invalidate old coins.The paper leaves fixing this limitation as an open problem.Source: §3.2 · p. 19
4 Win-win Results
This section presents win-win results for collision-resistant hash functions, one-time signatures, and commitment schemes: they either satisfy stronger security notions or yield quantum money or quantum lightning.
4 Win-win Results
- A scheme meeting weaker security notions either meets stronger definitions or can be used to construct quantum money or quantum lightning.The section interprets this as a positive outcome for either case, given the difficulty of constructing public-key quantum money.Source: §4 · p. 20
4.1 Infinity-Often Security
- Infinitely-often security bounds an adversary’s advantage by a negligible function for infinitely many security parameters, rather than necessarily all parameters.The win-win results therefore allow one of the two properties to be only infinitely-often secure.Source: §4.1 · pp. 20–21
4.2 Collision Resistant Hashing
- For collision-resistant H, either H is collapsing or yields infinitely-often-secure quantum lightning; either H is infinitely-often collapsing or yields secure quantum lightning.These are the two alternatives of Theorem 4.3.Source: §4.2 · p. 22
- For candidate bolts sharing a serial number, measuring them yields a hash collision; otherwise, both are accepted with probability at most 3/4.The construction uses a randomly chosen verification test; the bound applies to the stated pair of bolts.Source: §4.2 · p. 24
- Parallelized collision-resistant hashing makes the probability that two fully accepting bolt sequences share a serial number negligible, yielding valid quantum lightning.For individual bolts, the same-serial-number acceptance probability is bounded by 3/4; repeating in parallel makes the sequence-level probability negligible.Source: §4.2 · pp. 24–25
4.3 One-time Signatures
- A one-time weakly or strongly BZ-secure signature scheme is either correspondingly GYZ-secure or yields infinitely-often secure public-key quantum money; alternatively, it is infinitely-often GYZ-secure or yields secure public-key quantum money.The theorem gives both alternatives for the weak and strong cases, respectively.Source: §4.3 · p. 26
4.4 Commitment Schemes
- A publicly verifiable computationally binding commitment scheme is either collapse-binding or yields infinitely-often secure public-key quantum money; alternatively, it is infinitely-often collapse-binding or yields secure public-key quantum money.The theorem states both alternatives for the same commitment scheme.Source: §4.4 · p. 30
- Under computational binding, two banknotes with the same serial number imply verification failure with overwhelming probability; λ parallel repetitions suppress acceptance exponentially and yield full quantum money.The underlying construction is not a full quantum money scheme before parallel repetition.Source: §4.4 · pp. 30–31
4.5 Non-interactive Commitments
- A computationally binding non-interactive commitment is either collapse-binding or yields infinitely-often secure quantum lightning; alternatively, it is infinitely-often collapse-binding or yields secure quantum lightning.Interactive commitments do not give bolts because an adversarial bolt generator can influence the receiver; with non-interactive commitments, the receiver plays no role, and two bolts with the same serial number would open the commitment to two values, breaking computational binding.Source: §4.5 · p. 31
5 Constructing Quantum Lightning
The section builds quantum lightning from an assumed hardness property of random quadratic maps: finding sufficiently many non-affine collisions is infeasible. The construction turns those maps into verifiable bolts and also derives a collapse-non-binding hash function on an unrestricted domain.
5.1 Hardness Assumption
- A random-difference attack finds a collision by solving n linear equations in m unknowns, with rank n at constant probability for random matrices and difference.Generalizing the attack yields k + 1 non-affine colliding inputs when m ≥ kn, with overwhelming probability when m ≥ kn + ω(log λ).Source: §5.1 · p. 32
- The scheme is secure if random quadratic maps satisfy 2(k + 1)-NAMCR, meaning it is infeasible to find 2(k + 1) non-affine colliding inputs.The assumption uses k = poly(n) and m < (k + 1/2)n; a stronger (k + 2)-NAMCR assumption is possible but unnecessary for the construction.Source: §5.1 · p. 33
5.2 Quantum Lightning
- The construction generates a superposition of colliding inputs, measures their shared hash value y, and outputs the resulting state as a bolt.It chooses random upper-triangular matrices as the public key and maps each affine-space point x to x, x − ∆1, …, x − ∆k.Source: §5.2 · pp. 33–34
- Verification accepts bolts only when all k + 1 registers pass mini-verification and produce the same serial number y.The mini-verification projects onto the span of the construction’s hash-indexed states and measures the hash value; acceptance leaves the corresponding state unchanged.Source: §5.2 · pp. 34, 35, 37
- If two bolts verify with the same serial number, measuring them yields 2(k + 1) non-affine collisions, contradicting the hardness assumption; thus the scheme is secure under Assumption 5.1.The proof states that the measured pre-images are non-affine with overwhelming probability.Source: §5.2 · p. 37
5.3 Collapse-non-binding Hash Functions
- Restricting the input to sorted non-affine multi-collisions gives a collapse-non-binding hash function, which the section extends to an unrestricted domain.The unrestricted inputs encode the differences and coordinates within the collision affine space; handling varying space dimensions is omitted.Source: §5.3 · pp. 37–38
6 Quantum Money from Obfuscation
This section derives secure quantum money from indistinguishability obfuscation and injective one-way functions, and analyzes bounds on converting and cloning quantum states, including uniform superpositions over random subspaces. It also presents a signature scheme separating two security notions and a simpler black-box security proof with a matching bound for constant success probability.
6 Quantum Money from Obfuscation
- Injective one-way functions and iO yield secure quantum money by applying iO to Aaronson and Christiano’s abstract scheme.The construction follows by deriving a subspace-hiding obfuscator from an appropriately padded iO.Source: §6 · p. 38, §6.1 · p. 39, §6.3 · p. 43
6.1 Obfuscation
- Theorem 6.3 shows that appropriately padded iO is a secure subspace-hiding obfuscator when injective one-way functions exist and |F|^(n-d1) is exponential.The result supplies the obfuscator used to instantiate the quantum money scheme.Source: §6.1 · p. 39
6.2 New No-Conversion and No-Cloning Theorems
- For any CPTP converter, expected squared fidelity is at most d times the largest eigenvalue of C_{S1,S2,D}, which combines input/output overlaps and sampling probabilities.The bound applies to converting a sampled input state into its corresponding target state.Source: §6.2 · p. 41
- The no-conversion theorem bounds cloning through the states’ Gram matrix cubed; for k copies, the relevant matrix is A◦(k+1), yielding state-set-specific success bounds.Cloning is treated as conversion to multiple copies of the input state.Source: §6.2 · p. 41
- For uniformly random n/2-dimensional subspaces over F, copying the uniform superposition has squared fidelity at most 2 × |F|^-n/2.The state is the uniform superposition over the chosen subspace.Source: §6.2 · p. 42
6.3 Quantum Money from Obfuscation
- If shO hides dimensions d0=n/2 and d1 with |F|^(n-d1) and |F|^(d1-n/2) exponentially large, the banknote construction is secure.The banknote uses a subspace-hiding obfuscator for the random subspace and its dual.Source: §6.3 · p. 43
- Under the theorem’s assumptions, the obfuscation-based money construction has negligible cloning success: the bound 2|F|^(-n′/2) is exponentially small.The reduction relates the cloning probability to the adversary’s success in H4, then bounds that success using a random subset of dimension n′/2 in a space of dimension n′.Source: §6.3 · p. 44
6.4 A Signature Scheme
- The derived signature scheme preserves Boneh-Zhandry security when its underlying scheme has it, yet violates Garg-Yuen-Zhandry security, separating the two definitions.A superposition signing attack yields a state verifiable with the obfuscated programs, distinguishing it from a measured message/tag pair.Source: §6.4 · p. 45
6.5 A simplified Proof in the Black Box Setting
- The simplified black-box proof uses Grover’s lower bound and quantitative no-cloning, matching Aaronson and Christiano’s bound for constant ϵ but giving a slightly worse bound for small ϵ.It bounds copying probability by O(q²|F|^(-(n+1-d1)) + |F|^(-(d1-n/2))).Source: §6.5 · p. 45