PaperlayerView exact revision on arXiv

Source-linked AI summary

Tight adaptive reprogramming in the QROM

Alex B. Grilo, Kathrin Hövelmanns, Andreas Hülsing, Christian Majenz

arXiv:2010.15103v2quant-phcs.CR

TL;DR

Tight adaptive reprogramming remained an open challenge in the QROM, where superposition queries complicate oracle changes and tight proofs are often unavailable. The paper gives a tight bound under specified entropy and classical-trigger conditions, shows a matching attack, and applies the technique to signature constructions.

  • Problem

    Adaptive reprogramming lacked tight QROM bounds, although tightness matters because ROM security does not in general rule out schemes that are insecure in the QROM.

    Source: §1 · p. 2

  • Method

    The paper proves a general adaptive-reprogramming lemma for sufficiently entropic positions where classical queries to a game-provided oracle trigger reprogramming.

    Source: §1 · p. 3

  • Results

    A quantum attack matches the reprogramming bound up to a constant factor, and the tool tightens the hash-and-sign message-compression proof, including the XMSS case.

    Source: §1 · pp. 3, 5

  • Takeaways & Limitations

    The results show that adaptive reprogramming can support tight QROM proofs in the paper’s stated settings and applications.

    Source: §1 · pp. 3, 5

    The paper leaves Fiat–Shamir with aborts outside its treatment, noting limited implications for Dilithium because it is not subset-revealing.

    Source: §1 · p. 5

Abstract

from arXiv · show

The random oracle model (ROM) enjoys widespread popularity, mostly because it tends to allow for tight and conceptually simple proofs where provable security in the standard model is elusive or costly. While being the adequate replacement of the ROM in the post-quantum security setting, the quantum-accessible random oracle model (QROM) has thus far failed to provide these advantages in many settings. In this work, we focus on adaptive reprogrammability, a feature of the ROM enabling tight and simple proofs in many settings. We show that the straightforward quantum-accessible generalization of adaptive reprogramming is feasible by proving a bound on the adversarial advantage in distinguishing whether a random oracle has been reprogrammed or not. We show that our bound is tight by providing a matching attack. We go on to demonstrate that our technique recovers the mentioned advantages of the ROM in three QROM applications: 1) We give a tighter proof of security of the message compression routine as used by XMSS. 2) We show that the standard ROM proof of chosen-message security for Fiat-Shamir signatures can be lifted to the QROM, straightforwardly, achieving a tighter reduction than previously known. 3) We give the first QROM proof of security against fault injection and nonce attacks for the hedged Fiat-Shamir transform.

1 Introduction

The paper addresses whether adaptive reprogramming can be tightly proved in the QROM, where superposition queries complicate classical reprogramming and tight proofs are often lacking. It gives a tight reprogramming tool for common settings and applies it to hash-and-sign, Fiat–Shamir, and hedged Fiat–Shamir constructions.

The QROM gap

  • Adaptive reprogramming was difficult to lift to the QROM because superposition queries can reveal information about inputs that may be reprogrammed later.The paper asks whether this can be proved tightly; its tool assumes sufficiently high entropy at reprogramming positions and classical queries to the game-provided oracle trigger reprogramming.Source: §1 · pp. 2–3

Our contribution

  • The general lemma yields tight bounds for hash-and-sign with randomized hashing and Fiat–Shamir signatures, under the stated entropy conditions.In the two corollaries, the entropy comes from a reduction-sampled random string or from a commitment distribution with sufficient min-entropy and side information.Source: §1 · p. 3

Hash-and-sign

  • For hash-and-sign, the paper proves that a scheme secure under random-message attacks yields adaptive chosen-message security, and tightens the XMSS message-compression proof.The XMSS result permits random strings of half the length to randomize message compression.Source: §1 · p. 3

The Fiat-Shamir transform

  • For Fiat–Shamir signatures, HVZK and UF-CMA0 security imply UF-CMA security in the QROM, with a simple proof congruent with the ROM argument.The proof replaces honest transcripts with simulated ones and patches the oracle after signing queries.Source: §1 · pp. 3–4

Tightness and generality

  • The Fiat–Shamir reduction runs in roughly the adversary’s time, avoiding [KLS18]’s q_H q_S overhead, but its bound requires more commitment entropy.Appending random bits to commitments can increase that entropy; the proof also drops [KLS18]’s requirements for statistical HVZK and uniformly distributed challenges, requiring only computational HVZK.Source: §1 · p. 4

Robustness of the hedged Fiat-Shamir transform

  • The paper lifts the hedged Fiat–Shamir transform’s fault and biased-nonce security to the QROM, obtaining a quantum-resistance result for many fault types against Picnic.The prior ROM result is attributed to [AOTZ20], and Picnic is identified as a NIST candidate.Source: §1 · pp. 4–5

Scope

  • The authors do not further extend the result to Fiat–Shamir with aborts; for Dilithium, the implications are limited because it is not subset-revealing.They state that extending the security statements is straightforward but would complicate the proof.Source: §1 · p. 5

Optimality of our bound

  • A quantum attack matches the reprogramming bound up to a constant factor, using superposition queries and running in time poly(q, n).The attack applies cyclic input permutations before and after potential reprogramming to distinguish the two cases.Source: §1 · p. 5

2 Adaptive reprogramming: the toolbox

The section formalizes quantum adaptive reprogramming as a distinguishing game and gives bounds for basic and more general settings. Its theorem allows adaptively chosen reprogramming distributions with side information, subject to sufficient entropy of the reprogramming positions.

2 Adaptive reprogramming: the toolbox

  • Quantum access to a random oracle is modeled by a unitary that adds the oracle output to the response register, while the reprogramming game gives the distinguisher classical access to Reprogram.In the basic game, Reprogram samples a random x1 and output y for the adversary-supplied x2, then programs x1∥x2 to y.Source: §2 · pp. 5–6
  • Proposition 1 bounds distinguishing between an unchanged random oracle and one reprogrammed at positions partly controlled by the adversary and partly sampled at random.The authors report that the bound is tight up to a constant factor for trivial X1, via a matching distinguisher.Source: §2 · pp. 5–6
  • Theorem 1 covers repeated reprogramming under possibly different, adaptively chosen position distributions and side information, when the reprogramming positions have sufficient entropy.The bound accounts for the highest likelihood of generating a reprogramming position; the result is information-theoretic and applies to query-bounded adversaries.Source: §2 · pp. 6–7
  • Proposition 2 treats repeated reprogramming at adversarially supplied x2 values using a fixed distribution over the random position portion and side information.Its statement defines pmax as the largest probability assigned to any x1; the applications assume this distribution has sufficiently large entropy.Source: §2 · p. 7

3 Basic applications

The section applies adaptive reprogramming to hash-and-sign security reductions, including the XMSS message-hashing construction. It uses reprogramming to simulate signing and obtains a tighter QROM bound for the RFC 8391 setting.

3 Basic applications

  • The applications section presents the basic adaptive-reprogramming bound through hash-and-sign constructions, including the variable-length message-compression setting used by XMSS.The section identifies canonical UF-RMA-to-UF-CMA hash-and-sign and RFC 8391 message hashing as its two motivating examples.Source: §3 · p. 8

3.1 From RMA to CMA security via Hash-and-Sign

  • The QROM hash-and-sign reduction converts UF-RMA security into UF-CMA security by handling collision forgeries with M-eTCR and simulating signing through oracle reprogramming.The reduction uses the UF-RMA game's message-signature pairs and reprograms H at a random zi∥m′i for each signing query.Source: §3.1 · pp. 8, 10
  • The resulting proof gives a tighter QROM reduction for hash-and-sign, avoiding the prior repeated O2H-lemma applications described for this reduction.The theorem states that the UF-RMA reduction runs in about the adversary's time; the bound also accounts for second-preimage and reprogramming terms.Source: §3.1 · p. 8

3.2 Tight security for message hashing of RFC 8391

  • The passage confirms qH can be removed and says Proposition 1 applies directly to the distinguishing bound for games Ga and Gb, producing a bound with second term 32qs · α rather than 32qs · α2.Here α = qH/√|Z|.Source: §3.2 · p. 12

4 Applications to the Fiat-Shamir transform

The section lifts Fiat–Shamir security arguments to the QROM using adaptive reprogramming and multi-transcript HVZK. It applies this approach to standard and hedged Fiat–Shamir, including fault and nonce attacks.

4 Applications to the Fiat-Shamir transform

  • The proof of Theorem 3 uses computational multi-HVZK to compare collections of honest and simulated transcripts, extending the transcript indistinguishability notion to multiple transcripts.The special version uses a challenge-specific simulator.Source: §4 · pp. 12–13

4.1 Revisiting the Fiat-Shamir transform

  • If ID is HVZK and its Fiat–Shamir signature has UF-CMA0 security, Theorem 3 gives UF-CMA security in the QROM with reductions running about as fast as the adversary.The result also holds when challenges hash the public key along with the commitment and message.Source: §4.1 · p. 13
  • Theorem 3’s game sequence replaces honest transcripts with simulated ones and reprograms H afterward so that H(w, m) equals the transcript challenge.The reprogramming positions pair the adversary’s message with the commitment, and the challenge is the programmed value.Source: §4.1 · p. 14

4.2 Revisiting the hedged Fiat-Shamir transform

  • For the hedged construction, the paper extends [AOTZ20] to QROM fault robustness and permits the attacker to control the nonce used to derive signing randomness.The analysis considers the modified Fiat–Shamir transform that includes the public key in challenge hashing.Source: §4.2 · p. 16
  • The fault-injection application omits derivation and serialization faults at indices 8 and 10, while noting that extending the result to include them is straightforward.The hedged construction also excludes faults on the (message, nonce) input because it cannot generally be proven robust against them [AOTZ20].Source: §4.2 · p. 17
  • Under validity awareness, Theorem 4 proves QROM robustness for fault indices {5, 6, 9}; subset-revealing ID schemes additionally allow indices 4 and 7.The reductions run about as fast as the adversary.Source: §4.2 · pp. 17–18
  • Theorem 5 lifts hedged Fiat–Shamir security to the QROM when each (message, nonce) pair is queried at most once, adding fault index 1 to the covered set.The reduction is less tight in advantage than [AOTZ20], but its running time is reduced by a factor of qG.Source: §4.2 · p. 18

5 Adaptive reprogramming: proofs

The proofs model quantum oracle access with a superposition oracle, then analyze a single reprogramming instance before extending the argument to multiple instances and additional input. The single-instance analysis bounds a distinguisher in a two-stage setting where its chosen reprogramming input is sampled from a distribution.

5 Adaptive reprogramming: proofs

  • The proof first handles one reprogramming instance without additional input, then extends to multiple instances by a hybrid argument and to additional input using information-theoretic simulation.The reduction can compute marginal and conditioned distributions, so it need not be efficient.Source: §5 · p. 18

5.1 The superposition oracle

  • A superposition oracle stores each random function output in a register and answers quantum queries with a unitary operation; measuring the oracle registers can be deferred until querying ends.The authors use the simplest version of the technique introduced in [Zha19].Source: §5.1 · pp. 19–20
  • The basic superposition oracle does not efficiently simulate a quantum-accessible random oracle, which is acceptable for query lower bounds without time-complexity assumptions.Source: §5.1 · p. 19

5.2 Reprogramming once

  • The single-instance distinguisher makes q queries, chooses a distribution p, receives x* sampled from p, then tries to distinguish the oracle after possible reprogramming at x*.Its second stage has arbitrary quantum query access to the oracle.Source: §5.2 · p. 20
  • Theorem 6 bounds the distinguisher's success probability using the maximum point mass max_x p(x) of its chosen reprogramming distribution.Source: §5.2 · p. 20
  • The proof reduces oracle distinguishing to distinguishing the joint states before and after reprogramming at x, allowing arbitrary operations on the oracle register.It measures how far the register for x is from the uniform superposition state.Source: §5.2 · p. 21

6 A matching attack

The authors give a quantum-time attack matching their reprogramming bound for a single potentially reprogrammed point. It uses queries both before and after reprogramming and tests the resulting state with projections.

6 A matching attack

  • The attack makes q queries before and q queries after possible reprogramming, using a cyclic permutation to construct a set around the fixed point.The set is S = {x*, σ^-1(x*), ..., σ^-q+1(x*)}.Source: §6 · p. 23
  • Theorem 7 gives a quantum-polynomial-time attack that detects reprogramming at a single point, matching the bound from Theorem 6.Source: §6 · pp. 23–24, Figure 13 · p. 23
  • The proof compares the attacker's states when the oracle is unchanged and when reprogramming occurs, with the reprogrammed point's output difference uniformly random.The stated detection probability is at least a bound whose expression is not given in the supplied passage.Source: §6 · p. 24

A Adaptive reprogramming: Omitted proofs

The omitted proofs extend the single-instance bound to adaptive reprogramming through hybrids and a reduction that simulates side information. The appendix also specifies multi-target collision-resistance notions and games used in the hash-function analysis.

A Adaptive reprogramming: Omitted proofs

  • Lemma 2 handles repeated reprogramming instructions using the total oracle queries before each instruction and the corresponding reprogramming distribution.Its bound is stated in the supplied passage, but the formula is not legible there.Source: A Adaptive reprogramming: Omitted proofs · p. 27
  • Theorem 1 is derived by comparing consecutive hybrid games, each changing whether reprogramming has occurred at a given position.The proof bounds the overall distinguishing gap by summing the gaps between adjacent hybrids.Source: A Adaptive reprogramming: Omitted proofs · pp. 27–28
  • A reduction simulates additional side information by sampling the conditional distribution given the reprogrammed input, which may require an unbounded computation.The reduction preserves the joint distribution and thus perfectly simulates the game.Source: A Adaptive reprogramming: Omitted proofs · pp. 28–29

B.1 Security of Hash Functions

  • The appendix defines multi-target extended target-collision resistance for quantum-accessible random oracles, with a nonce variant allowing the adversary to select an n-bit identifier.The nonce definition uses a classical challenge oracle that returns uniformly random function keys.Source: §B.1 · p. 29
  • The hash-function analysis describes two games that differ in whether the hash value at a randomly keyed, selected message is reprogrammed before the second query phase.Both games allow at most q1 queries before selecting the message and q2 afterward.Source: §B.1 · pp. 29–30

B.2 Identification schemes

These appendices specify the identification and signature schemes used in the applications. They define transcript and security notions, then describe Fiat–Shamir and hash-and-sign constructions.

B.2 Identification schemes

  • An identification scheme comprises key generation, commitment, response, and deterministic verification algorithms, with transcripts formed from a commitment, challenge, and response.The transcript oracles provide either a real interaction or an honest transcript for a fixed challenge.Source: §B.2 · p. 30
  • Validity awareness requires the response algorithm to reject malformed challenges, while statistical HVZK bounds transcript-distribution distance from honest transcripts.Special statistical HVZK makes the comparison for each fixed challenge.Source: §B.2 · pp. 30–31
  • A subset-revealing identification protocol responds by returning the state components selected by DeriveSet from the challenge.The definition requires a polynomial-size challenge space and a polynomial number of state components.Source: §B.2 · p. 31

B.3 Signature schemes

  • A digital signature scheme consists of key generation, signing, and deterministic verification; the appendix defines UF-CMA, UF-CMA0, and UF-RMA security games.Source: §B.3 · p. 31
  • The Fiat–Shamir transform hashes a commitment and message into a challenge, while hash-and-sign compresses a message with a hash before using the underlying signature scheme.The modified Fiat–Shamir transform also includes the public key in the hash input.Source: §B.3 · p. 32

C From UF-CMA0 to UF-F-CMA (Proof of Theorem 4)

The proof reduces faulty-signature security to UF-CMA0 security by simulating faulted signing queries through sequential game hops. Under validity awareness it covers fault indices {5, 6, 9}; assuming subset-revealing identification, it extends coverage to {4, 5, 6, 7, 9}.

C From UF-CMA0 to UF-F-CMA (Proof of Theorem 4)

  • Theorem 4 reduces UF-FF-CMA security for indices {5, 6, 9} to UF-CMA0 security in the QROM, and subset-revealing identification extends the set to {4, 5, 6, 7, 9}.The theorem assumes validity awareness; the extended result additionally assumes subset-revealing identification.Source: C From UF-CMA0 to UF-F-CMA (Proof of… · p. 33
  • The proof replaces fault-signing executions with secret-key-free simulations in the order 9, 5, 6, 7, 4, stopping at index 6 without subset-revealing identification.The sequential proof uses statistical sHVZK; a computational-sHVZK generalization reorders the steps, reprogramming for all fault indices before replacing transcripts.Source: C From UF-CMA0 to UF-F-CMA (Proof of… · pp. 33, 35, 36

C.1 Game G1: Simulating FAULTSIGN for index 9 (Proof of Lemma 3)

  • Index 9 simulation first reprograms H for a-posteriori transcript consistency, then replaces honest transcripts using statistical sHVZK.The stated reprogramming term is (qH + qS + 1) · γ(Commit).Source: §C.1 · p. 36

C.2 Game G2: Simulating FAULTSIGN for index 5 (Proof of Lemma 4)

  • For index 5, reprogramming positions fix the message and public-key shares while the commitment share gives pmax ≤ 2γ(Commit), before transcript replacement.The stated term is (qH + qS + 1) · 2γ(Commit).Source: §C.2 · p. 37

C.3 Game G3: Simulating FAULTSIGN for index 6 (Proof of Lemma 5)

The index 6 simulation handles faults to the challenge hash output by reprogramming the oracle and replacing honest transcripts with simulated ones. Invalid faulted challenges must be rejected.

C.3 Game G3: Simulating FAULTSIGN for index 6 (Proof of Lemma 5)

  • Index 6 simulation reprograms H for a-posteriori consistency, then replaces honest transcripts with simulated ones and rejects invalid faulted challenges.The stated term is (qH + qS + 1) · γ(Commit); validity awareness gives equality between FAULTSIGN and simSignature6.Source: §C.3 · p. 38

C.4 UF-CMA0 adversary for game G3, for F = {5, 6, 9} (Proof of Lemma 6)

Once game G3 simulates faults for indices {5, 6, 9} using simulated transcripts and a correspondingly reprogrammed random oracle, an UF-CMA0 adversary can reproduce that game.

C.4 UF-CMA0 adversary for game G3, for F = {5, 6, 9} (Proof of Lemma 6)

  • The UF-CMA0 reduction perfectly simulates game G3 with the same running time, and a forgery remains valid because no reprogramming occurs on the forged message.In G3, all signing answers come from simulated oracles for fault indices {5, 6, 9}.Source: §C.4 · pp. 38–39, Figure 23 · p. 38

C.5 Faulting the response input (Proof of Lemma 7)

Assuming subset-revealing identification, the proof simulates faulted response inputs at index 7, including faults to the response state.

C.5 Faulting the response input (Proof of Lemma 7)

  • Under subset-revealing identification, faults to c use the index 6 strategy, while faults to sk have no effect on Respond and use the index 9 strategy.The stated term is (qH + qS + 1) · γ(Commit).Source: §C.5 · pp. 39–40
  • For state faults, the simulation applies the fault to response z, allowing honest transcripts to be replaced even when φ targets st.The response is derived from the shares selected by DeriveSet(c).Source: §C.5 · pp. 39–40

C.6 Faulting the commitment output (Proof of Lemma 8)

For fault index 4, the proof simulates signatures when the commitment output is faulted and bounds the resulting game change. It also relates faults targeting w or st to simulations for indices 5 or 7.

C.6 Faulting the commitment output (Proof of Lemma 8)

  • For fault index 4, the proof defines simSignature4 to simulate signatures when the commitment output is faulted.The adversary makes at most qS,4 index-4 signing queries, qS total signing queries, and qH random-oracle queries.Source: §C.6 · p. 40, Figure 25 · p. 40
  • When fault function φ targets w, the simulation strategy is identical to simSignature5, as for fault index 5; when it targets st, it is identical to simSignature7, as for fault index 7.Putting both cases together yields (qH + qS + 1) · 2γ(Commit).Source: §C.6 · p. 40

D From UF-F-CMA to UF-N-F-CMA (Proof of Theorem 5)

Theorem 5 lifts UF-FF-CMA security of the Fiat–Shamir scheme to nonce-based UF-N-FF-CMA security of its R2H transform in the QROM, subject to a restriction on repeated nonce-signing queries. The proof decouples commitment randomness from the secret key and uses query extraction to handle the resulting game change.

D From UF-F-CMA to UF-N-F-CMA (Proof of Theorem 5)

  • UF-FF-CMA security of SIG implies UF-N-FF-CMA security of SIG′ = R2H[SIG, G] in the QROM for F′ = F ∪ {1}, if no (m, n) query to N-FAULTSIGN is repeated.The theorem gives reductions B1 and B2 for adversaries making at most qS signing, qH H, and qG G queries.Source: D From UF-F-CMA to UF-N-F-CMA (Proof… · p. 41
  • B1 runs in about A’s time, while B2 takes roughly Time(A) + |sk| · (Time(Sign) + Time(Vrfy)).The stated overhead for B2 scales with the secret-key length and the costs of signing and verification.Source: D From UF-F-CMA to UF-N-F-CMA (Proof… · p. 41
  • The proof changes the commitment randomness from G(sk, m, n) to fresh randomness, then bounds the game change using Theorem 8 and query extraction.Intermediate games replace G on fault-reachable secret keys with G′ before restoring access to G for the adversary.Source: D From UF-F-CMA to UF-N-F-CMA (Proof… · pp. 42–44
  • Extractor E measures a query to G to obtain a secret-key candidate; B2 checks fault-related candidates and can generate a valid signature if it finds the original key.The candidate list includes keys obtainable by one-bit fault injection, including the identity function.Source: D From UF-F-CMA to UF-N-F-CMA (Proof… · pp. 44–45, Figure 29 · p. 45

E A matching attack - details

The section details a quantum distinguisher for a single reprogrammed point, using queries before and after reprogramming and a final measurement. It then sketches how the attack may extend to multiple reprogrammings, while leaving that case’s formal analysis for future work.

E A matching attack - details

  • The single-point attack is quantum polynomial-time and uses q oracle queries before and q after reprogramming to detect the change.The stated theorem applies for 1 ≤ q below its stated upper threshold; the attack’s probability bound is truncated in the supplied passage.Source: E A matching attack - details · p. 45
  • The distinguisher uses a cyclic permutation to form a q-point set around x*, then measures the final state in the (Π0, Π1) basis.The proof explains how to implement the measurement efficiently by approximating the relevant projection.Source: E A matching attack - details · pp. 45, 47

E.1 Generalization to multiple reprogrammings

  • For multiple reprogrammings, the extension is presented as intuition: in the polynomial case, collisions occur with exponentially small probability, while formal analysis is left for future work.The discussion conditions on no collision before applying the preceding analysis.Source: §E.1 · pp. 47–48
Loading 2010.15103v2…