PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum Attacks on Classical Proof Systems - The Hardness of Quantum Rewinding

Andris Ambainis, Ansis Rosmanis, Dominique Unruh

arXiv:1404.6898v2quant-phcs.CR

TL;DR

Quantum security proofs are difficult because their analyses rely on rewinding, whose quantum generalization is limited. This paper constructs oracle-relative separations using the pick-one trick and shows that several classically secure proof systems and commitments can fail against quantum adversaries. The results identify genuine barriers to general relativizing security proofs while remaining scoped to the oracle setting and not ruling out every individual protocol.

  • Problem

    Quantum rewinding techniques cover only restricted classes of proofs, leaving open whether their additional conditions reflect proof limitations or genuine quantum insecurity.

  • Method

    The paper develops oracle-relative separations and the pick-one trick, which enables finding one predicate-satisfying value without enabling the efficient discovery of two.

  • Results

    Relative to an oracle, classically secure sigma-protocols, Fiat–Shamir, Fischlin’s system, and computationally binding commitments can fail to provide their corresponding quantum security guarantees.

  • Takeaways & Limitations

    The results show that the relevant quantum security proofs require new, non-relativizing techniques and that computational binding can provide limited quantum guarantees.

  • Takeaways & Limitations

    The oracle-relative results do not imply that all sigma-protocols are insecure without oracles or that the investigated schemes are insecure in the real world.

Abstract

from arXiv · show

Quantum zero-knowledge proofs and quantum proofs of knowledge are inherently difficult to analyze because their security analysis uses rewinding. Certain cases of quantum rewinding are handled by the results by Watrous (SIAM J Comput, 2009) and Unruh (Eurocrypt 2012), yet in general the problem remains elusive. We show that this is not only due to a lack of proof techniques: relative to an oracle, we show that classically secure proofs and proofs of knowledge are insecure in the quantum setting. More specifically, sigma-protocols, the Fiat-Shamir construction, and Fischlin's proof system are quantum insecure under assumptions that are sufficient for classical security. Additionally, we show that for similar reasons, computationally binding commitments provide almost no security guarantees in a quantum setting. To show these results, we develop the "pick-one trick", a general technique that allows an adversary to find one value satisfying a given predicate, but not two.

1 Introduction

Quantum rewinding is less versatile than classical rewinding, and the paper shows that this reflects genuine oracle-relative insecurity rather than only incomplete proof techniques. The paper develops separations for sigma-protocols, Fiat–Shamir, Fischlin’s system, and commitments, while identifying scope limits of those separations.

  • Motivation: Quantum rewinding cannot generally save quantum security because quantum states cannot be copied, and existing techniques require additional conditions such as strict soundness.Watrous handles many zero-knowledge proofs, while Unruh’s proof-of-knowledge technique does not cover computational security and requires strict soundness.
  • Main separations: Relative to an oracle, classically secure sigma-protocols, Fiat–Shamir, and Fischlin’s system can fail as quantum proofs or proofs of knowledge.The results include computational-setting failures for sigma-protocols and Fiat–Shamir, and a quantum proof-of-knowledge failure for Fischlin’s system.
  • Commitments: Computationally binding commitments can be opened by a quantum adversary to any chosen value, provided it does not open the same commitment to two values simultaneously.This shows that the classical computational-binding definition can be insufficient in the quantum setting relative to an oracle.
  • Technique: The pick-one trick lets an adversary find one value satisfying a predicate but prevents it from efficiently finding two such values.The construction uses a state and an oracle enabling Grover-style search, while additional oracle access prevents obtaining two copies of the relevant state.
  • Interpretation: The oracle separations rule out relativizing security proofs for the investigated schemes and motivate new proof techniques.They do not establish insecurity in the real world without oracles, and they do not exclude security for every individual sigma-protocol.

2 Preliminaries

The preliminaries fix the paper’s security-parameter, oracle, quantum-state, sigma-protocol, and security-definition conventions. They also emphasize that the paper studies strong, polynomial-time quantum attacks against proof and knowledge guarantees.

  • Conventions: Algorithms and their parameters are understood as functions of the security parameter η, with running times required to be polynomially bounded in η.This convention applies even when parameters are described informally as superlogarithmic functions.
  • Oracles: Oracles are unitary transformations that quantum algorithms may query in superposition, and the defined oracles are self-inverse so their inverses are available.Even classical-form oracles can receive superposition queries from quantum algorithms.
  • Sigma-protocols: A sigma-protocol is a three-message proof system consisting of a commitment, a random challenge, and a response checked by a verifier.The protocol is specified together with message lengths, prover algorithms, a verifier, and a relation R.
  • Sigma-protocol properties: Special soundness uses two accepting conversations with the same commitment and different challenges to extract a witness, either perfectly or computationally.The computational variant considers polynomial-time quantum adversaries and requires extraction failure to be negligible.
  • Security definitions: A total break requires a polynomial-time quantum adversary to convince the verifier of a false statement with overwhelming probability.The paper’s attack definitions are strong: the adversary receives no auxiliary state, and extraction must fail with overwhelming probability for a knowledge break.

3 State creation oracles

The section shows how state-creation oracles can be emulated using finite reservoir states and additional reference copies, while preserving the relevant oracle behavior up to inverse-polynomial precision.

  • State creation oracles: An oracle for creating copies of an unknown state is no more powerful than a polynomial-size reservoir containing copies and suitable superpositions with an orthogonal state.This replacement is useful because reservoir states are easier to analyze in the Two Values problem.
  • State creation oracles: Theorem 3 formalizes emulation of a state-creation oracle using another oracle and a finite state reservoir, despite superposition queries and inverse applications.The text emphasizes that this equivalence is not immediate because direct oracle access may appear more powerful than copies alone.
  • State creation oracles: The construction uses auxiliary operations and reference states to implement the desired oracle circuit, with the remaining oracle emulation supplied by the theorem's lemmas.The ideal infinite tensor-product reservoir is motivational; the final proof uses finite tensor products.
  • State creation oracles: A finite reservoir approximates the ideal infinite reservoir, so the associated circuit approximately realizes the state-creation oracle.The finite state has a transition between many copies of the target state and copies of the orthogonal state.
  • State creation oracles: A permutation-symmetry test using m reference copies distinguishes the target state from orthogonal states with error O(1/m), enabling simulation of the reference oracle to inverse-polynomial precision.The test replaces an insufficient swap test for implementing ORef.

4 The pick-one trick

The pick-one trick separates finding one valid value from finding two distinct values in the same hidden subset. This asymmetry underlies the paper’s oracle separations and extraction failures.

  • 4 The pick-one trick: The Two Values problem asks for two distinct elements from a hidden subset using state and membership oracles.Its hardness is the core lower bound behind the pick-one trick.
  • 4 The pick-one trick: The pick-one trick lets an adversary find one subset element satisfying a predicate but prevents finding two distinct elements with non-negligible probability.The paper uses this gap to foil extraction by rewinding.
  • 4 The pick-one trick: A constant-probability search for two distinct values requires at least Ω(sqrt(|X|/k)) queries under the stated oracle resources.When the relevant parameters are superpolynomial, polynomial-time adversaries succeed only with negligible probability.
  • 4 The pick-one trick: A polynomial-time algorithm can search for one x ∈ S_y satisfying a predicate whenever the predicate holds on at least a δ_min fraction of S_y.The search runs in polynomial time in n, 1/δ_min, and |y|.
  • 4 The pick-one trick: The oracle distribution uses logarithmic challenge length, superlogarithmic commitment and response lengths, and randomized oracle answers through an additional input.The extra input gives independent answers for otherwise equal queries, emulating probabilistic behavior.
  • 4 The pick-one trick: The hardness extends to the full oracle distribution: polynomially bounded queries cannot recover the hidden witness or produce two distinct accepting responses.The proof removes auxiliary oracles by reductions to the Two Values lower bound and emulates state-creation access with reservoir states.

5 Attacking commitments

The paper constructs commitments that satisfy strong classical-style properties yet remain quantumly insecure: a quantum adversary can open a commitment to a chosen message without having known it when committing.

  • 5 Attacking commitments: Classical computational binding prevents producing two different valid openings, but the paper argues this definition is insufficient in the quantum setting.Even computational strict binding will be shown insufficient.
  • 5 Attacking commitments: Theorem 12 gives an oracle-relative commitment scheme that is perfectly complete, computationally binding, computationally strict binding, and statistically hiding.These properties hold simultaneously relative to the paper’s oracle.
  • 5 Attacking commitments: Despite those properties, a quantum polynomial-time adversary can open the commitment to an arbitrary message, including one it did not know while committing.The attack succeeds with overwhelming probability for every message length or message m covered by the theorem statement.
  • 5 Attacking commitments: The commitment binds each message bit using a selected bit of a hidden subset element, while verification checks subset membership and the bit relation.The adversary later searches for subset elements whose selected bits match the desired message.
  • 5 Attacking commitments: The construction’s selected-bit commitment form is unnecessary for the basic commitment result but is required for the later attack on Fischlin’s scheme.This connects the commitment design to its reuse in subsequent proof-system attacks.
  • 5 Attacking commitments: Binding follows from the hardness of finding two subset values, whereas hiding follows from the superpolynomial number of possible values for each subset.The attack instead finds one suitable value per committed bit using the pick-one search theorem.

6 Attacking sigma-protocols

Relative to an oracle, sigma-protocols that satisfy classical security properties can fail as quantum proofs of knowledge or arguments. The attacks exploit the ability to produce one accepting response while preventing extraction of a witness or two responses.

  • 6 Attacking sigma-protocols: Strict soundness is necessary for quantum proof-of-knowledge security: without it, a classically secure sigma-protocol admits a total knowledge break.The protocol retains completeness, perfect special soundness, computational strict soundness, and statistical honest-verifier zero-knowledge, yet remains quantum insecure.
  • 6 Attacking sigma-protocols: For logarithmic challenge length, the malicious prover succeeds with overwhelming probability while an extractor with the same oracle access fails to find the witness.The prover uses the pick-one search procedure to respond to the verifier’s challenge, while commitment attacks supply suitable openings.
  • 6 Attacking sigma-protocols: The proof’s quantum insecurity does not imply a total break in the unconditional setting, because an unlimited classical adversary can simulate a quantum adversary.The distinction disappears for computationally limited provers, which is why the computational case establishes a stronger failure.
  • 6.1 The computational case: Computational special soundness does not suffice for quantum argument security: a sigma-protocol can be a classical argument yet admit a total quantum break.The computational construction has completeness, computational special soundness, computational strict soundness, and statistical honest-verifier zero-knowledge.
  • 6.1 The computational case: The computational attack proves a statement outside the language because the constructed relation is empty, yielding a total break rather than only a knowledge break.Pairs of accepting conversations exist, but computational hardness prevents finding them efficiently, so computational special soundness still holds.

7 Attacking Fiat-Shamir

The Fiat-Shamir transformation can turn a classically secure sigma-protocol into a quantum-insecure non-interactive proof system. Relative to an oracle, this failure occurs for both perfect and computational special soundness variants.

  • 7 Attacking Fiat-Shamir: The Fiat-Shamir prover hashes statement and commitments to derive challenges, then returns commitments and corresponding responses for verification.The verifier recomputes the random-oracle challenges and checks every underlying sigma-protocol transcript.
  • 7 Attacking Fiat-Shamir: A Fiat-Shamir system with perfect special soundness can have a total knowledge break despite completeness, computational strict soundness, and statistical honest-verifier zero-knowledge.The underlying sigma-protocol with the same properties is a classical argument of knowledge when rℓch is superlogarithmic.
  • 7 Attacking Fiat-Shamir: The Fiat-Shamir attack is analogous to the sigma-protocol attack because replacing the verifier’s challenge with a random-oracle output does not change the strategy.The construction therefore inherits the relevant quantum attack despite being classically secure under the stated condition.
  • 7.1 The computational case: A computationally special-sound Fiat-Shamir system can suffer a total break under the same oracle-relative framework.This strengthens the insecurity result from failure of quantum knowledge extraction to complete computational insecurity.

8 Attacking Fischlin’s scheme

The section shows that Fischlin’s construction can fail as a quantum argument of knowledge even when the underlying sigma-protocol meets strong classical-security properties. The attack uses the pick-one trick, including against a construction whose classical extraction passively inspects oracle queries.

  • Motivation: The pick-one trick yields a quantum insecurity result for Fischlin’s proof system despite its classical extraction strategy.Classically, extraction inspects the adversary’s oracle-query list; quantumly, that list is not well-defined because query inputs are not measured.
  • Construction: Fischlin’s verifier checks accepting sigma-protocol triples and requires the sum of their hash outputs to be at most S.The proof consists of r triples, with verification of each triple followed by the hash-sum threshold test.
  • Classical extraction: The classical intuition is that sufficiently small hash sums force two accepting responses for the same commitment, enabling extraction from the queried values.The prover must try several accepting challenge-response pairs for each commitment, so classical queries contain two such pairs with overwhelming probability.
  • Statistical case: There is an oracle-relative total knowledge break when the sigma-protocol has logarithmic challenge length, completeness, perfect special soundness, computational strict soundness, statistical honest-verifier zero-knowledge, and commitment entropy.The result is stated for Fischlin’s construction under the listed properties.
  • Computational case: There is also an oracle-relative total break in the computational case, although the same construction remains a classical argument of knowledge.The computational theorem assumes computational special soundness and computational strict soundness, alongside the other listed properties.
  • Open question: The authors conjecture that the two insecurity theorems may continue to hold with strict rather than computational strict soundness, leaving the proof open.The conjecture concerns a variant with superlogarithmic challenge length and random response sets satisfying one response per challenge.

Symbol index

The symbol index lists parameters, algorithms, oracle names, protocol components, and quantum-state notation used throughout the paper. It also identifies Fischlin-specific and sigma-protocol-specific symbols.

  • Fischlin notation: The index defines Fischlin parameters r and b as the number of subproofs and hash-output length, respectively.It also lists COMverify, COMopen*, PFS, and VFis among the construction’s named components.
  • Quantum notation: The notation includes |Ψ⟩ for a Hilbert-space vector, ⟨Ψ| for its conjugate transpose, and OΨ for an oracle providing |Ψ⟩.The index also names |yes⟩ and |no⟩ as superpositions used in Grover search.
  • Protocol notation: The index records protocol symbols such as com for commitment, resp for response, ℓcom for commitment length, and ℓch for challenge length.These symbols are used for sigma-protocol messages and parameters.

Keyword index

The keyword index catalogs the paper’s central concepts, including binding and soundness properties, proof systems, commitments, quantum procedures, and auxiliary probability tools. It also cross-references the pick-one trick and the two-values problem.

  • Security properties: The index covers computational and statistical security notions, including computational binding, strict binding, special soundness, and strict soundness.These entries distinguish properties of commitment schemes and sigma-protocols.
  • Analytical tools: The technical index records statistical distance, trace distance, entropy, hypergeometric sampling, Hoeffding’s inequality, and Jensen’s inequality.These entries correspond to the paper’s probability and quantum-state analyses.
  • Protocol concepts: It identifies Fischlin, sigma-protocols, commitments, and proof systems as core protocol concepts.The index also lists honest-verifier zero-knowledge, knowledge, and total knowledge break.
  • Attack concepts: The index includes the pick-one trick and the two values problem among the paper’s central attack concepts.It also cross-references quantum security and post-quantum cryptography.
  • Quantum and oracle analysis: It lists oracle-query and quantum-state machinery, including preimage search, oracle removal, quantum registers, and state-distance arguments.The indexed lemmas analyze oracle algorithms, query transcripts, and quantum states.

B Proofs for Section 3

The proofs establish oracle-simulation and quantum-state lemmas used to analyze the paper’s separations. They combine state transformations, symmetrization, oracle replacement, and representation-theoretic structure.

  • Oracle constructions: The oracle OΨ swaps |Ψ⟩ with an orthogonal state |⊥⟩ while fixing states orthogonal to both, whereas ORef reflects about |Ψ⟩.These two oracle behaviors are related through constructions using auxiliary registers and unitary transformations.
  • Oracle simulation: A reservoir state is built from tensor products of rotated states |αj⟩, enabling an algorithm to replace reflection-oracle queries with queries to OΨ.The proof introduces cyclic shifts and analyzes the resulting state transformations.
  • Reflection simulation: The reflection ORef is implemented approximately through a unitary UV acting as −1 on the shift-invariant subspace and +1 on its orthogonal complement.The invariant subspace consists of states fixed by the cyclic shift S.
  • Symmetrization: Symmetrization makes the algorithm effectively run on permuted inputs while preserving its average success probability.The construction uses the action of a wreath product on hidden oracle inputs and output representations.
  • Register structure: The proof framework separates query, output, resource, and workspace registers to track oracle interactions and state evolution.The query registers encode Y, X, and oracle-output bits; the output register encodes Y and pairs from X.

C.4 Framework for the proof

The proof analyzes a quantum algorithm through symmetry-respecting density matrices and projections, reducing the relevant case to a single value of Y. Representation-theoretic conditions then bound the algorithm’s success probability and establish the hardness theorem.

  • State decomposition: The analysis tracks the probability mass in complementary subspaces using p_a,q and p_b,q across oracle-query intervals.The state ρ_q is invariant under the relevant symmetry group, and p_b,q is defined as 1 − p_a,q.
  • Reduction to |Y| = 1: The birthday-bound contribution from repeated y-values is at most h(h − 1)/(2M), allowing the analysis to isolate distinct tuples in Y^h.The repeated-value probability is interpreted through the birthday problem.
  • Reduction to |Y| = 1: The proof reduces the general problem to the case |Y| = 1, because the algorithm’s success probability can be analyzed after measuring and fixing a single y.The reduction uses symmetry and discards registers associated with other values of Y without changing the relevant success analysis.
  • Representation-theoretic analysis: Only irreps (N − 1, 1), (N − 2, 2), and (N − 2, 1, 1) occur in both representation decompositions relevant to the proof.The representation U contains four copies of (N − 1, 1), four of (N − 2, 2), and two of (N − 2, 1, 1).
  • Necessary and sufficient conditions: For the (N − 1, 1) component, the query conditions require either small or nearly unit weight in the relevant β-coordinates, with threshold O(max{k/N, 1/k}).The condition is stated as |β_1,s|^2 + |β_1,t|^2 ≤ O(max{k/N, 1/k}) or at least 1 − O(max{k/N, 1/k}).
  • Conclusion: The resulting lemmas establish the hardness of the two values problem, while the amplitude-iteration analysis yields failure probability at most 2^-n.The proof concludes Theorem 5 and separately records the bound for the iterative search procedure.

E.2 Proof of Corollary 8

The proof of Corollary 8 progressively removes oracle access and reduces collision-finding to the hardness of the two values problem. With superlogarithmic parameters, each error term is negligible, so the target probability is negligible.

  • Oracle removal: The proof transforms an adversary through stages that remove access to OS, OP, OR, OE, and OΨ while preserving the relevant collision probability.Each transformation replaces oracle access with sampling, emulation, or a related adversary construction.
  • Oracle removal: A sampled adversary A5 reproduces the distribution of independently generated commitment transcripts by measuring independent copies of |ΣΨ⟩.The resulting transcripts are independently distributed according to DY.
  • Reduction to Theorem 5: The transformed adversary fits the hardness-of-two-values framework with h := n + m + s.This substitution lets Theorem 5 control the final collision probability.
  • Negligibility bounds: Choosing n, m, and s as superpolynomial functions of the commitment and response lengths makes the principal summands negligible.The proof uses n, m, s := ⌊min{2^ℓresp/4, 2^ℓcom/3}⌋ and argues that the first three summands are negligible.
  • Negligibility bounds: The remaining reductions propagate negligibility from P6 through P5, P4, P3, P2, P1, and finally PA.Polynomially bounded query counts and superlogarithmic parameters preserve negligibility at each step.

F.1 Proof for Lemma 14

Lemma 14 establishes the commitment scheme’s completeness, computational binding, strict binding, and statistical hiding using the hard-to-find-two-values property. The attack construction also shows that a quantum adversary can produce valid openings with overwhelming probability.

  • Completeness: The commitment scheme has perfect completeness because oracle-generated pairs lie in the accepting sets used by COMverify.For every generated (y_i, x_i), OV(y_i, x_i) = 1, which implies COMverify accepts.
  • Binding: Computational strict binding follows because two distinct valid openings would yield two distinct x-values satisfying the same predicate, contradicting Corollary 8.The argument reduces a successful binding violation to the hardness of finding two satisfying values.
  • Binding: Computational binding is obtained directly from computational strict binding.The paper states this implication explicitly.
  • Hiding: Statistical hiding follows because the adversary’s distinguishing probability is negligible under the stated superlogarithmic parameter conditions.The proof concludes that the statistical distance is negligible when ℓrand − ℓcom − k is superlogarithmic and k is superpolynomial.
  • Quantum attack: The attack’s opening failure probability is bounded by |m|f, yielding ε_COM ≥ 1 − |m|2^-ℓcom + |m|2e^-k/18, which is overwhelming under the parameter assumptions.The bound uses polynomial message length together with superlogarithmic ℓcom and k.

G.1 Proof of Lemma 18

Lemma 18 proves the sigma-protocol’s classical properties, including completeness, statistical HVZK, entropy, and soundness, while the surrounding construction prepares the quantum attack. The attack later exploits valid accepting behavior that an extractor cannot reproduce.

  • Completeness: The sigma-protocol is complete because a uniformly chosen challenge has an accepting response with overwhelming probability when ℓresp is superlogarithmic.The proof uses the convergence of (1 − 1/n)^n from below to 1/e.
  • Commitment entropy: The commitment used in the protocol has superlogarithmic min-entropy because its commitment component is uniform over {0, 1}^ℓcom.Its min-entropy is at least ℓcom.
  • Soundness: The protocol has perfect special soundness because two accepting conversations with distinct challenges allow OE to recover w0.The extractor simply outputs OE(com, ch, resp, ch′, resp′).
  • Soundness: Computational strict soundness follows from the computational strict binding of the underlying commitment scheme.Two distinct accepting responses would produce two valid distinct openings of the same commitment.
  • Statistical HVZK: The protocol has statistical HVZK because the simulator’s statistical distance is bounded by ε := ε0 + ε1 + ε2 + ε3, which is negligible under the parameter assumptions.The proof invokes negligible commitment distance and superlogarithmic response and randomness lengths.
  • Quantum attack: The quantum adversary succeeds with overwhelming probability, but any polynomial-time extractor with the same oracle access finds w0 only with negligible probability.The extractor failure follows from Corollary 8’s hardness result.

H.1 Proof of Theorem 25

The Fiat–Shamir construction admits total knowledge and computational breaks when instantiated from the paper’s vulnerable sigma-protocols. The attacks reuse the sigma-protocol adversary and yield extractor failure despite classical security results.

  • A total knowledge break exists against Fiat–Shamir instantiated from the sigma-protocol of Definition 17.
  • The quantum adversary repeatedly generates commitments, derives challenges from the random oracle, and invokes the sigma-protocol attack to obtain responses.
  • Extractor failure persists even when the extractor may choose the random oracle before and during the first adversary stage.
  • A total computational break also exists against Fiat–Shamir instantiated from the computational sigma-protocol of Definition 21.
  • The computational attack reuses the adversary from the non-computational Fiat–Shamir attack, whose success probability is overwhelming.

I.1 Proof of Theorem 28

The Fischlin construction inherits quantum total breaks from the paper’s sigma-protocol and commitment attacks. The construction’s special commitment form lets the adversary search for accepting responses while arranging the required openings.

  • A total knowledge break exists against Fischlin’s construction based on the sigma-protocol of Definition 17.
  • The attack uses a fixpoint commitment property so searched challenge-response pairs can themselves serve as commitment openings.
  • The adversary invokes the one-value search procedure repeatedly to obtain accepting challenge-response pairs for each commitment.
  • The probability that all searched pairs satisfy the required success events is at least 1 − 2^-ℓcomr − re^-k(2^-2b−1).
  • Because r is polynomially bounded, b is logarithmic, and ℓcom and k are superpolynomial, the success probability is overwhelming.
  • Extractor failure remains established independently of the second adversary stage, including when the extractor chooses the random oracle during the first stage.
  • The same construction yields a total computational break against Fischlin’s construction based on the computational sigma-protocol.
Loading 1404.6898v2…