PaperlayerView exact revision on arXiv

Source-linked AI summary

Security of the Fiat-Shamir Transformation in the Quantum Random-Oracle Model

Jelle Don, Serge Fehr, Christian Majenz, Christian Schaffner

arXiv:1902.07556v4cs.CRquant-ph

TL;DR

Quantum superposition queries obstruct standard random-oracle techniques for analyzing Fiat-Shamir security. The paper gives a generic reduction to the underlying sigma-protocol and shows preservation of key security properties, with applications to Fiat-Shamir signatures.

  • Problem

    Quantum superposition queries prevent observing or copying adversarial oracle queries without disturbance, complicating Fiat-Shamir security analysis in the quantum random-oracle model.

  • Method

    The paper constructs a generic transformation from a Fiat-Shamir dishonest prover to a similarly successful sigma-protocol dishonest prover using hash reprogramming and simulation.

  • Results

    Soundness and proof-of-knowledge, computational and statistical, are preserved under Fiat-Shamir in the quantum random-oracle model, with probability loss O(q2).

  • Takeaways & Limitations

    The result yields quantum-random-oracle security for suitable Fiat-Shamir signatures and computational proofs of knowledge under quantum computationally unique responses.

  • Takeaways & Limitations

    Applying the techniques to highly optimized signature schemes and deriving concrete security bounds remain future work.

Abstract

from arXiv · show

The famous Fiat-Shamir transformation turns any public-coin three-round interactive proof, i.e., any so-called sigma-protocol, into a non-interactive proof in the random-oracle model. We study this transformation in the setting of a quantum adversary that in particular may query the random oracle in quantum superposition. Our main result is a generic reduction that transforms any quantum dishonest prover attacking the Fiat-Shamir transformation in the quantum random-oracle model into a similarly successful quantum dishonest prover attacking the underlying sigma-protocol (in the standard model). Applied to the standard soundness and proof-of-knowledge definitions, our reduction implies that both these security properties, in both the computational and the statistical variant, are preserved under the Fiat-Shamir transformation even when allowing quantum attacks. Our result improves and completes the partial results that have been known so far, but it also proves wrong certain claims made in the literature. In the context of post-quantum secure signature schemes, our results imply that for any sigma-protocol that is a proof-of-knowledge against quantum dishonest provers (and that satisfies some additional natural properties), the corresponding Fiat-Shamir signature scheme is secure in the quantum random-oracle model. For example, we can conclude that the non-optimized version of Fish, which is the bare Fiat-Shamir variant of the NIST candidate Picnic, is secure in the quantum random-oracle model.

1 Introduction

The paper develops a way to analyze Fiat–Shamir security in the QROM despite quantum superposition queries, proving that key security properties transfer from Σ-protocols to their Fiat–Shamir versions. It also derives consequences for quantum-secure signatures and identifies limitations and prior claims that require stronger conditions.

  • The (quantum) random-oracle model: Quantum superposition queries prevent directly observing or reprogramming the random-oracle queries used by an adversary.This obstruction is why ROM security proofs generally do not automatically extend to the QROM.
  • Main technical result: The technical result extracts an adversary’s likely output input by measuring a randomly selected query and reprograms the oracle there with a fresh random value.The success probability loses at most a factor O(q2), where q is the number of oracle queries.
  • Application to the Fiat-Shamir transformation: A generic reduction transforms any quantum Fiat–Shamir dishonest prover into a similarly successful dishonest prover against the underlying Σ-protocol.The reduction uses the extracted commitment and the verifier’s challenge to reprogram the random oracle.
  • Comparison with prior results: Soundness and proof-of-knowledge, in both computational and statistical variants, are preserved under Fiat–Shamir in the QROM.This extends the positive result beyond statistical soundness and contradicts restricted impossibility claims that forbid measuring oracle queries.
  • Circumventing prior negative results: A stronger notion of quantum computationally unique responses can yield computational proofs of knowledge and therefore secure Fiat–Shamir transformations.The paper cautions that proving this stronger uniqueness property may be substantially harder than proving ordinary computational uniqueness.
  • Application to signatures: Under additional natural assumptions, the results establish QROM security for Fiat–Shamir signatures, including the non-optimized Fish variant of Picnic.Applying the techniques to highly optimized signature schemes and deriving concrete security bounds remains future work.

2 Reprogramming the Quantum Random Oracle

The paper develops a black-box method for reprogramming a quantum random oracle despite superposition queries. A two-stage measure-and-reprogram algorithm preserves predicate success up to an O(q^2) loss, enabling the main technical theorem.

  • Oracle model: The paper analyzes quantum oracle algorithms making q queries to finite-domain functions and predicates on outputs dependent on x and H(x).The oracle acts unitarily on query registers, and the output state may include a quantum register.
  • Oracle reprogramming: The reprogrammed function H ∗Θ_x agrees with H except that it maps x to a fresh value Θ.This lets the analysis replace the hash value at one selected input while preserving all other oracle values.
  • Measure-and-reprogram: The two-stage algorithm S measures one uniformly selected query or final output to obtain x, then reruns the algorithm with one query answered using either H or H ∗Θ_x.All remaining queries use the reprogrammed oracle, and the choice of which oracle answers the measured query is random.
  • Main technical result: For any oracle H and input x, Lemma 1 relates the success of S to the success of the algorithm under the reprogrammed oracle, with an O(q^2) loss.The comparison averages over Θ, the selected query index, and the random oracle-answering choice.
  • Random-oracle simulation: The analysis averages over a 2(q + 1)-wise independent hash family, uses indistinguishability from a fully random function, and notes a negligible additive term when |Y| is superpolynomial.For polynomial |Y|, the stated bound is not optimal, although improved bounds can be derived using similar techniques.
  • Main technical result: Theorem 2 establishes a black-box polynomial-time two-stage quantum algorithm that outputs x first and a predicate-satisfying quantum output after receiving a random Θ.The theorem applies to arbitrary q-query quantum algorithms against a uniformly random oracle and arbitrary predicates.

3 Security of the Fiat-Shamir Transformation

The paper gives a generic quantum reduction from Fiat–Shamir attacks to attacks on the underlying Σ-protocol, with polynomial loss in the oracle-query count. This reduction preserves computational and statistical soundness and proof of knowledge under matching definitions.

  • The generic reduction: Any dishonest Fiat–Shamir prover can be transformed into an underlying Σ-protocol prover with the same success probability up to polynomial loss.The construction is black-box and applies to adaptive quantum Fiat–Shamir adversaries making q random-oracle queries.
  • The generic reduction: The reduction also supports adversaries that produce local classical or quantum outputs satisfying an extended predicate.The local output is incorporated into the response and the verifier predicate.
  • The generic reduction: Security of a Σ-protocol implies security of its Fiat–Shamir transform when the corresponding security definitions match.The implication is stated for security against dishonest provers and applies across the considered definitions.
  • Preservation of soundness: For superpolynomial challenge spaces, static computational or statistical soundness of a Σ-protocol implies adaptive soundness of its Fiat–Shamir transform.Static soundness first implies adaptive soundness for the Σ-protocol itself.
  • Preservation as a proof of knowledge: For superpolynomial challenge spaces, static computational or statistical proof of knowledge of a Σ-protocol implies adaptive proof of knowledge for its Fiat–Shamir transform.The same static-to-adaptive implication is established for proofs of knowledge.

4 Application to Fiat-Shamir signatures

The paper applies its Fiat–Shamir reduction to signatures, showing that proof of knowledge of the underlying protocol yields no-message unforgeability under a hard relation. Additional zero-knowledge, entropy, and response-uniqueness conditions yield chosen-message security.

  • Fiat-Shamir signatures: A Fiat–Shamir proof system can be converted into a public-key signature scheme whose signer proves knowledge of a secret witness.The signature is the non-interactive proof for a statement containing the public key and message.
  • No-message security: Under a hard relation, superpolynomial challenge space, and proof of knowledge, the Fiat–Shamir signature scheme achieves EUF-NMA security.The extractor’s success in producing a witness would contradict hardness of the relation.
  • Chosen-message security: The paper completes prior analyses by deriving precise conditions for strong unforgeability without lossy keys.The result concerns chosen-message security and builds on the reduction to no-message security.
  • Chosen-message security: If the protocol has proof of knowledge, ε-perfect non-abort honest-verifier zero knowledge, α bits of min-entropy, and computationally unique responses, the signature scheme achieves sEUF-CMA security.These conditions are stated together with a hard relation and superpolynomial challenge space.

5 Extractable Σ-protocols from quantum computationally unique responses

The paper introduces quantum computationally unique responses as a collapsingness-based condition and combines them with t-soundness to obtain extractable Σ-protocols.

  • Motivation: Computationally unique responses are insufficient in general to replace perfect unique responses for quantum extractability.The paper motivates a stronger quantum condition based on collapsingness.
  • Quantum computationally unique responses: Quantum computationally unique responses require the verification relation from responses to commitment-challenge pairs to be collapsing.For fixed commitment-challenge pairs, the condition prevents distinguishing whether a successful response superposition was measured.
  • Extractability theorem: A Σ-protocol with constant t-soundness and quantum computationally unique responses is a computational proof of knowledge.This generalizes an earlier theorem that assumed perfect unique responses and special soundness.
  • Extractability theorem: The extractor obtains responses for fresh random challenges by measuring and rewinding the adversary, then computes a witness from t accepting transcripts.The t-soundness condition supplies the witness once all required verification checks succeed.
  • Motivation: The result is expected to apply broadly because deployed Fiat–Shamir signature protocols commonly use computationally unique responses, while artificial separations between collision resistance and collapsingness are limited.The paper connects this observation to the practical use of its generalized extractability theorem.

6 Application to NIST submissions

The section applies the paper’s QROM results to NIST-related Fiat–Shamir schemes, establishing conditions for security while identifying unresolved analyses for optimized constructions.

  • 6.1 Picnic: Picnic uses the Unruh transform for QROM security, whereas Fish applies plain Fiat–Shamir with a reported 1.6x efficiency advantage.Fish is described as the same underlying scheme under plain Fiat–Shamir.
  • 6.1 Picnic: ZKBoo-based Fiat–Shamir signatures are strongly existentially unforgeable in the QROM when the commitment function is a collapsing hash.The proof uses quantum computational unique responses derived from collapsingness and combines this with 3-soundness.
  • 6.1 Picnic: The paper leaves applying its ZKBoo result to optimized ZKB++ and Fish schemes for future work.ZKB++ optimizations complicate analysis, and concrete security bounds for highly optimized schemes remain open.
  • 6.1 Picnic: Picnic2 is not t-sound under the standard condition, but a variation of t-soundness is proven sufficient in Lemma 30.The issue arises because three responses determine a witness only under restricted challenges.
  • 6.2 Lattice-based Fiat–Shamir signature schemes – CRYSTALS-Dilithium and qTesla: For the lattice protocol, computationally unique responses follow from SIS, while the paper additionally assumes the associated function family is collapsing.The response property is equivalent to collision resistance of the restricted linear map, and collapsingness is treated as a natural additional assumption.
  • 6.2 Lattice-based Fiat–Shamir signature schemes – CRYSTALS-Dilithium and qTesla: Under Assumption 27, the lattice protocol has quantum computational unique responses and yields a strongly existentially unforgeable Fiat–Shamir signature scheme in the QROM.The conclusion is stated for Sig[LatticeΣ].

A Proof of Lemma 12 and 15

The proofs reduce adaptive sigma-protocol adversaries to static adversaries by fixing their first-stage outputs and internal state, then invoke the corresponding static security properties.

  • Lemma 12: Lemma 12 fixes an adaptive adversary’s first-stage instance and message, producing a static adversary with the same corresponding internal state.The construction runs the adaptive first stage once and uses the resulting state to define the static adversary.
  • Lemma 12: The proof of Lemma 12 concludes by applying the security bound for the resulting static adversary.The argument allows either quantum polynomial-time or unbounded static adversaries.
  • Lemma 15: Lemma 15 constructs an adaptive black-box knowledge extractor by running the first stage, recording its outputs and state, and invoking the static extractor thereafter.The static adversary simulates the second stage of the original adaptive adversary using the recorded state.
  • Lemma 15: The final bound averages over possible first-stage outputs and uses the static proof-of-knowledge property together with Jensen’s inequality.The proof explicitly identifies these as the sources of its two inequalities.

B Generalization of Lemma 7 from [Unr12]

This appendix generalizes projection-based success bounds to relate interactive-prover acceptance probabilities to extractor success under sequential and partially reused challenges.

  • Sequential random projections: The first generalization relates one random projection to sequential application of t random projections through average square-norm success probabilities.Its purpose is to connect interactive-prover acceptance with extractor acceptance.
  • Sequential random projections: Lemma 29 states a generalized projection inequality for projections P1 through Pn applied to a state vector.The displayed consequence includes the bound F ≥ V 2t−1.
  • Sequential random projections: The appendix extends the earlier t = 2 result to t = 3, with the general case following by the same proof strategy.The proof uses convexity and a prior claim from the proof of Lemma 7.
  • Partially reused challenges: A second generalization analyzes extractors that rewind once with a fresh challenge pair and again with one challenge component reused.This addresses challenges composed of two parts.
  • Partially reused challenges: Lemma 30 formalizes the partially reused-challenge setting using a family of projections indexed by two challenge components.The lemma begins with projections Pij and a state vector.
Loading 1902.07556v4…