PaperlayerView exact revision on arXiv

Source-linked AI summary

Non-uniformity and Quantum Advice in the Quantum Random Oracle Model

Qipeng Liu

arXiv:2210.06693v1quant-phcs.CR

TL;DR

The paper studies whether bounded quantum preprocessing advice improves non-uniform attacks in the QROM, a capability absent from the standard generic model. It introduces alternating measurement games to analyze such advice without rewinding, matching classical-advice security for many natural games while finding an exponential separation for a contrived no-query game.

  • Problem

    The QROM does not capture non-uniform algorithms whose offline phase produces bounded classical or quantum advice, leaving quantum advice's advantage over classical advice unresolved.

    Source: §1 · pp. 2–3

  • Method

    The paper introduces alternating measurement games as a quantum analogue of multi-instance games and uses them to analyze OWFs, PRGs, and salted cryptographic games without rewinding.

    Source: §2 · pp. 8, 12

  • Results

    Quantum-advice bounds match classical-advice bounds for many natural QROM games, while a contrived game has exponentially better quantum advice when T=0.

    Source: §1 · p. 3, §1.1 · p. 6

  • Takeaways & Limitations

    Quantum advice provides no or little advantage for many natural cryptographic games, but the QROM still permits exponential quantum–classical separations in restricted games.

    Source: §1 · p. 3

    The demonstrated exponential separation applies only when the adversary makes no online queries, T=0.

    Source: §8 · p. 28

Abstract

from arXiv · show

QROM (quantum random oracle model), introduced by Boneh et al. (Asiacrypt 2011), captures all generic algorithms. However, it fails to describe non-uniform quantum algorithms with preprocessing power, which receives a piece of bounded classical or quantum advice. As non-uniform algorithms are largely believed to be the right model for attackers, starting from the work by Nayebi, Aaronson, Belovs, and Trevisan (QIC 2015), a line of works investigates non-uniform security in the random oracle model. Chung, Guo, Liu, and Qian (FOCS 2020) provide a framework and establish non-uniform security for many cryptographic applications. In this work, we continue the study on quantum advice in the QROM. We provide a new idea that generalizes the previous multi-instance framework, which we believe is more quantum-friendly and should be the quantum analogue of multi-instance games. To this end, we match the bounds with quantum advice to those with classical advice by Chung et al., showing quantum advice is almost as good/bad as classical advice for many natural security games in the QROM. Finally, we show that for some contrived games in the QROM, quantum advice can be exponentially better than classical advice for some parameter regimes. To our best knowledge, it provides some evidence of a general separation between quantum and classical advice relative to an unstructured oracle.

1 Introduction

The paper develops quantum-advice techniques for non-uniform security in the QROM, matching classical-advice bounds for many natural games while exhibiting an exponential separation for a contrived game.

1 Introduction

  • Quantum advice addresses a gap in the QROM, which models generic oracle access but not preprocessing that produces bounded classical or quantum advice.Non-uniform attackers use an offline phase to generate advice for an efficient online attack.Source: §1 · p. 2
  • The paper asks whether quantum advice can outperform classical advice in the QROM and answers that it generally does not for common cryptographic games.The stated question is motivated by large prior parameter gaps between classical and quantum advice, especially for OWFs and PRGs.Source: §1 · p. 3

1.1 Our Results

  • The new alternating measurement games generalize multi-instance games without rewinding non-uniform quantum algorithms, enabling tight analyses of quantum advice.The reduction avoids both rewinding and the need for majority vote or tomography.Source: §1.1 · p. 3
  • For OWFs, the result gives security bounds matching classical advice and shows that S=O(√α) quantum advice cannot speed up inversion beyond probability T^2/α.For S=T=2^128, the recommended security parameter is n=384 for 2^-128 security against non-uniform quantum attacks.Source: §1.1 · p. 4, Table 1 · p. 5
  • For PRGs, the paper improves quantum-advice analysis and reduces the exponent on T^2/N from 1/3 to 1/2 relative to the prior result.PRGs are harder to handle because they are decision games and lack public verifiability.Source: §1.1 · pp. 4–5, Table 2 · p. 5
  • For salted games, non-uniform security differs from uniform security by O(ST/K) for search games or O(ST/K)^(1/3) for decision games, for any game type.This extends prior salting results and matches classical-advice bounds; as K grows, the decision-game bound reaches uniform security ν(T).Source: §1.1 · pp. 5–6
  • A contrived QROM game separates advice models: with T=0, classical advice of S=2^(n^c)/n bits has security 2^-Ω(n), while S=O~(n) quantum qubits achieve winning probability 1-negl(n).The separation is established only in the no-online-query regime and is related to one-way communication complexity.Source: §1.1 · pp. 6–7

2 Technical Overview

The paper replaces rewinding-based multi-instance reductions with alternating measurement games, yielding tight quantum-advice bounds and a broader bit-fixing framework. It also identifies a contrived QROM separation where quantum advice is exponentially stronger than classical advice.

Difficulties of Rewinding Quantum Advice

  • The prior quantum-advice reduction used multiple advice copies and rewinding, weakening OWF bounds to O((ST + T^2)/N)^1/3 versus O((ST + T^2)/N) for classical advice.The loss is attributed to rewinding and the need for multiple quantum-advice copies.Source: §2 · p. 9

PRGs

  • For PRG reductions, answers are not publicly verifiable, so majority voting can worsen a 60% success rate to 40% rather than amplify it to 99% [CGLQ20].An online version of shadow tomography yields quantum-advice bounds 1/2 + O((S5T + S4T2)/N)1/19, compared with 1/2 + O((ST + T2)/N)1/3 for classical advice.Source: §2 · pp. 9–10

Alternating Measurement Games

  • For alternating measurement games, a g-round execution has winning probability E_H[p^g], directly converting the advice-dependent success distribution into a multi-round security game.The construction alternates projections and accepts when all measurement outcomes are 0.Source: §2 · pp. 11–12
  • Alternating measurement games avoid rewinding quantum advice and enable tight non-uniform security bounds for OWF games.The reduction also avoids majority vote and tomography, which were needed in the prior approach.Source: §2 · pp. 9, 11, 12

Removing Advice

  • Setting g = S and P = ST removes quantum advice by guessing it, producing a uniform-game advantage bounded by O((ST + T^2)/N)^S.The advice-removal step incurs a 2^-S loss before the bit-fixing bound is applied.Source: §2 · pp. 13–14

General Framework

  • The framework extends to any game whose P-BF-QROM advantage is bounded by ε, with non-uniform security established at O(ε); decision games require a different g choice.For PRGs, g = S is unsuitable because the baseline winning probability is about 1/2.Source: §2 · pp. 8, 14

Separation of Classical and Quantum Advice

  • For a contrived QROM one-way function, quantum advice achieves success arbitrarily close to 1 with T = 0, while classical advice reveals only about O~(S) oracle positions and cannot invert most challenges.This yields evidence of an exponential quantum-versus-classical advice separation in a subexponential-advice regime.Source: §2 · p. 14

3 Preliminaries

The preliminaries define quantum oracle access in the QROM and collect probabilistic inequalities used later to analyze alternating measurement games.

3.1 Quantum Random Oracle Model

  • In the QROM, a fixed random classical function is accessed through a unitary oracle, and query complexity counts the number of oracle-unitary calls.A quantum oracle algorithm interleaves local unitaries with oracle calls before measuring its internal register.Source: §3.1 · p. 15

3.2 Other Useful Lemmas

  • The auxiliary lemmas establish moment and variance relationships, including that the sequence S_k is monotonically non-decreasing.These inequalities support the later analysis of conditional winning probabilities.Source: §3.2 · pp. 15–16

4 (𝑆, 𝑇) Quantum Algorithms and Games in the QROM

This section formalizes non-uniform quantum algorithms and games in the QROM, then introduces the quantum bit-fixing model used to transfer security bounds.

4 (𝑆, 𝑇) Quantum Algorithms and Games in the QROM

  • A non-uniform quantum algorithm consists of oracle-dependent S-qubit advice and a uniform T-query unitary procedure, with uniform algorithms using zero advice.The idealized model does not require the workspace or unitary size to be polynomially bounded.Source: §4 · p. 16
  • A QROM game samples a challenge with random coins, lets an oracle-access quantum adversary output an answer, and verifies that answer using the same coins.The game’s security is the maximum winning probability over bounded-advice, bounded-query adversaries.Source: §4 · p. 17
  • The formal game definition does not directly cover Yao’s box, where the adversary is forbidden from querying the challenge input, although the techniques extend to a related-oracle setting.The authors retain the current definition despite this limitation.Source: §4 · p. 17

4.1 Quantum Bit-Fixing Model

  • The quantum bit-fixing model conditions a random oracle on a P-query quantum sampler outputting 0, then gives the resulting oracle and a shared state to a T-query online adversary.The corresponding classical model restricts both stages to classical queries.Source: §4.1 · p. 18
  • For OWFs, the P-BF-QROM winning probability is ν(P,T) = (P + T^2)/min{N, M}.This bit-fixing bound is later used to control alternating measurement games.Source: §4.1 · p. 18

5 Games, POVMs and Decomposition of Advice

The paper represents a non-uniform quantum algorithm’s winning probability through a game-specific POVM and its eigenbasis, exposing how bounded advice limits useful overlap with high-success directions.

POVM Representation

  • A game’s verification procedure induces a POVM P_H whose expectation on the advice-plus-workspace state equals the algorithm’s winning probability.For function inversion, the projector spans registers containing valid preimages of the challenge.Source: §5 · p. 19

Eigenbasis Decomposition

  • Decomposing the initial state into P_H’s eigenbasis expresses success as a weighted sum of eigenvalues, with amplitudes determined by the advice-dependent state.Each eigenvector defines an algorithm whose success probability equals its associated eigenvalue.Source: §5 · p. 19

6 Non-Uniform Lower Bounds via Alternating Measurements

Section 6 develops alternating measurement games as a quantum-friendly multi-instance framework and uses them to transfer bit-fixing security bounds to non-uniform quantum algorithms with quantum advice.

6 Non-Uniform Lower Bounds via Alternating Measurements

  • Theorem 6.1 bounds non-uniform quantum security by 2·ν(P,T) when P=S(T+T_Verify+T_Samp) and the game has security ν(P,T) in the P-BF-QROM.This is the section’s main reduction from bit-fixing security to quantum-advice security.Source: §6 · p. 20

6.1 Multi-Instance via Alternating Measurements

  • The alternating measurement game G^⊗k repeatedly applies controlled projections and uniformity projections, and is won exactly when every measurement outcome is zero.The construction alternates CP_H on odd rounds with I_Uniform on even rounds.Source: §6.1 · p. 21

6.2 Characterization of Alternating Measurements and Proof of Theorem 6.4

  • Theorem 6.4 relates an algorithm’s winning probability in G to its probability in G^⊗k through the eigenvalues and eigenbasis of the corresponding POVMs.Lemma 6.6 characterizes the leftover state after conditioning on zero outcomes, supporting the theorem’s analysis.Source: §6.1 · p. 21, §6.2 · p. 22

6.3 Advantages of Uniform Algorithms in Alternating Measurement Games

  • For uniform algorithms, conditional success probabilities in successive alternating rounds are monotone, enabling bounds from the P-BF-QROM to control the alternating game.Theorem 6.7 applies when P≥k(T+T_Samp+T_Verify), with the construction using at most (k−1)(T+T_Samp+T_Verify) queries.Source: §6.3 · pp. 23–24

6.4 Proof of Main Theorem

  • The proof removes quantum advice by replacing it with a maximally mixed S-qubit state, losing a factor 2^-S, and combines this with the alternating-game bound.For general games, the resulting bound is at most 2·ν(P,T); decision games require a separate treatment of the 2^-S factor.Source: §6.4 · pp. 25–26

7 Applications

Section 7 applies the main theorem to OWF, PRG, and salted games, obtaining improved quantum-advice bounds and showing that salting defeats preprocessing in the QROM.

7 Applications

  • The framework applies to publicly verifiable OWF games and decision PRG games whenever their P-BF-QROM security can be analyzed.The applications therefore cover both major game types discussed in the section.Source: §7 · p. 26
  • The result improves the previous result on GPRG with quantum advice [CGLQ20] and concerns (S, T) non-uniform quantum adversaries, even with quantum advice.Source: §7 · p. 27

7.1 Salting Defeats Quantum Advice

  • Salting randomizes the challenge instance, reducing the influence of preprocessing advice as the salt space K grows.The salted game samples a uniform salt and uses the corresponding restricted oracle H_s for sampling and verification.Source: §7.1 · p. 27
  • For a salted game with salt space [K], security is at most 4ν(T)+O(S(T+T_Samp+T_Verify)/K), and decision games satisfy the stronger second bound.The decision-game bound is ν(T)+O(S(T+T_Samp+T_Verify)/K)^1/3.Source: §7.1 · p. 27

8 Advantages of Quantum Advice in the QROM

Section 8 constructs a QROM game where quantum advice is exponentially more powerful than classical advice for a restricted parameter regime, using YZ functions and error-correcting codes.

8 Advantages of Quantum Advice in the QROM

  • The exponential advantage is established only for some parameter regimes, with the paper identifying this as an initial step toward broader separations.The stated regime specifically requires T=0.Source: §8 · p. 28
  • G_YZ inverts a uniformly random image of a YZ function, which concatenates random-oracle outputs indexed by the coordinates of an error-correcting-codeword.Sampling uses no oracle queries, while verification makes n queries.Source: §8 · p. 28
  • The quantum strategy makes non-adaptive queries independent of the challenge, stores them as advice, and performs only post-processing after receiving the challenge.The quantum algorithm therefore has no online oracle queries in the non-uniform formulation.Source: §8 · pp. 28–29
  • The constructed game G_YZ has classical-advice security 2^-Ω(n) for S=2^(n^c)/n and T=0, while quantum advice of size Õ(n) achieves success 1−negl(n).The separation specifically uses no online queries, T=0, and a constant 0<c<1.Source: §8 · pp. 28–29
  • The classical lower bound follows from lazy sampling and list recoverability: either the challenge corresponds to one of at most L good codewords, or unsampled coordinates force success probability at most 2^-ζn.The resulting total winning probability is L/2^n+2^-ζn=2^-Ω(n).Source: §8 · p. 29

A Classical Version of Our Main Theorem

Appendix A gives a classical-advice analogue of the main theorem, transferring P-BF-ROM security to non-uniform classical security with a simple multiplicative loss.

A Classical Version of Our Main Theorem

Loading 2210.06693v1…