PaperlayerView exact revision on arXiv

Source-linked AI summary

An Operator-Norm Approach to Security with Quantum Advice

Minki Hhan, Sunghyuk Jo, Qipeng Liu

arXiv:2609.37467v1quant-phcs.CR

TL;DR

Non-uniform security models adversaries with bounded advice about an oracle before a fresh challenge, but existing salting bounds can be costly. The paper develops an operator-norm approach and a unified reduction, yielding improved decision-game bounds and tight bounds for several constructions.

  • Problem

    Non-uniform security models preprocessing through bounded oracle-dependent advice, while existing generic salting bounds can require very large salt spaces.

    Source: §1 · pp. 3–4

  • Method

    The paper connects quantum auxiliary-input security to bit-fixing security through an operator-norm approach that bounds advantages directly.

    Source: §1.1 · p. 4

  • Results

    The unified reduction improves decision-game bounds, while Yao’s-box bounds are tight up to constants and salted permutation-inversion bounds up to logarithmic factors.

    Source: §1.1 · pp. 4–5

  • Takeaways & Limitations

    The diffuse-game property yields tighter salted bounds by separating existing-database contributions from subsequent-query contributions.

    Source: §1.2 · p. 9

    The technical overview assumes the algorithm starts with a maximally mixed advice state, purified using an additional reference register.

    Source: §1.2 · p. 6

Abstract

from arXiv · show

Non-uniform security allows an adversary to receive bounded advice about an oracle before attempting a fresh challenge. This captures the most realistic attacks and has already been studied extensively in prior work. In this work, we introduce an operator-norm approach for non-uniform security in the quantum random oracle and random permutation models. This new approach yields a unified reduction for both search success probability and distinguishing advantage. Previously, the reduction only worked with success probability even in the decision games, yielding a worse bound. Our framework enables tight bounds for Yao's box, both with and without salting, and improved bounds for pseudorandom generators. We also prove an optimal generic salting theorem for decision games. By defining a property of a game, which separates the contributions of the existing queries in the offline stage and subsequent online queries, we obtain stronger bounds for specific salted constructions. These include salted permutation inversion, tight up to logarithmic factors, and salted random-function inversion, tight up to logarithmic factors and the gap already present in classical function inversion.

1 Introduction

The introduction develops an operator-norm approach to non-uniform security with quantum advice, connects it to bit-fixing security, and presents a unified reduction for search and decision games. It also introduces diffuseness to tighten generic salting bounds, with a different bound for decision games.

1.1 Our Results

  • The new reduction bounds advantages directly in both quantum-advice and bit-fixing models, enabling improved bounds for Yao’s box and PRGs.The paper also improves a PRG bit-fixing bound using the polynomial method.Source: §1.1 · p. 4
  • The generic salting theorem recovers the search bound up to constant factors and improves the decision-game salt-dependent term to sqrt(Sr/K), which is optimal for general decision games.The one-bit Yao game has zero uniform advantage, while its salted version admits an attack matching the square-root term.Source: §1.1 · p. 5
  • The unsalted and salted Yao’s-box bounds are tight up to constant factors, salted permutation inversion is tight up to logarithmic factors, and salted random-function OWF bounds match attacks under stated conditions.For random-function OWFs, the attack match holds up to logarithmic factors when ST^2 ≤ K min{N, M}; the bound also matches Grover search when S ≤ KT.Source: §1.1 · p. 5

1.2 Technical Overview

  • The technical approach represents game advantage with an operator and bounds it through high-order moments, rather than applying the existing high-moment framework to success probability.This direct operator treatment also applies when the decision-game operator is not positive semidefinite.Source: §1.2 · p. 7
  • The paper shows that bit-fixing security equals the database-size-restricted operator norm, because the offline phase can prepare any unit vector in the bounded-database state space.The compressed-oracle database size tracks information learned about the random function and grows by at most one per query.Source: §1.2 · pp. 7–8
  • For salted games, the analysis tracks each salt’s database separately and bounds advantage by separating states with no queries to the challenge salt from states with a nonempty database there.The no-query component is bounded by uniform security, while the nonempty component is controlled by the database-size observable.Source: §1.2 · pp. 8–9
  • In decision games, MEs need not have a positive semidefinite square root, so the triangle-inequality approach does not apply and yields a weaker exponent of 1/2.The overview instead expands ⟨ψ|MEs|ψ⟩ into terms ⟨ψi|MEs|ψj⟩ for i, j ∈ {0, 1} and bounds each term.Source: §1.2 · p. 9
  • The diffuseness condition captures additional structure that can make generic bounds loose, including contributions that average to O(Sr/(KN)) after reduction.The example starts with a database of expected size L contributing O(L/N), which averages over salts to O(P/(KN)).Source: §1.2 · p. 9
  • For a (γ, ∆)-diffuse base game, averaging over salts bounds its salt term by κ(Sr/K∆)γ.The overview says this yields tighter or tight non-uniform bounds for games including OWF, PRG, and Yao’s box.Source: §1.2 · p. 9

2 Preliminaries

The preliminaries establish oracle and database representations for random functions and permutations, then state a reprogramming bound for quantum circuits. These tools track how queries change database size and acceptance probability.

2 Preliminaries

  • A POVM on register A is a family of positive semidefinite operators summing to the identity, with outcome z occurring with probability Tr(ρE_z).Source: §2 · p. 9

2.1 Compressed Oracle and Function Database Hierarchy

  • In the QROM, Fourier-basis database states track oracle information, and each query increases database size by at most one, even with entanglement.The hierarchy consists of nested spaces of states with bounded database size.Source: §2.1 · pp. 9–10

2.2 Permutation Analogue and Permutation Database Hierarchy

  • In the QRPM, databases are partial permutation assignments; their states need not be orthogonal, but each query still increases database size by at most one.The hierarchy uses orthogonal sectors to measure size, and permutation database states may have components at several sizes no greater than their assignment size.Source: §2.2 · pp. 11–12

2.3 Uniform One-Point Reprogramming

  • Uniform one-point reprogramming bounds the acceptance-probability change when a circuit’s oracle is changed at a uniformly random point independent of the circuit.The circuit makes at most T queries, and its initial state, inter-query operations, and final measurement are independent of the reprogrammed point.Source: §2.3 · p. 13

3 Connecting Non-uniform Security with Bit-Fixing Security

This section develops a reduction from quantum auxiliary-input security to bit-fixing security, improving the decision-game bound. It specifies the game and adversary models used for that reduction.

3 Connecting Non-uniform Security with Bit-Fixing Security

  • The section introduces a new reduction from non-uniform security to bit-fixing security that gives a better bound for decision games than prior work.Source: §3 · p. 13

3.1 Game, QROM and QRPM

  • A game samples a random function or permutation, generates a challenge, permits oracle queries, and verifies the adversary’s answer.Each query increases database size by at most one.Source: §3.1 · p. 13

3.2 Bit-Fixing, Quantum Auxiliary-Input, and Advantage

  • Bit-fixing adversaries make up to P offline queries and then up to T online queries; quantum auxiliary-input adversaries receive an S-qubit state and make up to T queries.In the purified bit-fixing model, the online algorithm receives a postselected state, can access register A, and cannot access Z or B.Source: §3.2 · pp. 13–14

G (S, T), AdvBF

The section represents each security game by an operator on the adversary’s input register, then connects restricted operator norms to bit-fixing security and quantum auxiliary-input security.

3.3 Game Operators and Their Purified Representation

  • Each game induces Hermitian operators of operator norm at most 1, with positive operators in search games.The operators capture the game outcome for any input state; their purified versions act on the oracle and adversary registers.Source: §3.3 · p. 15

3.4 QAI Security from Database-Size-Restricted Operator Bounds

  • Theorem 3.4 bounds quantum auxiliary-input advantage using bit-fixing advantage at database size P = 2S(TSample + T + TVerify).The proof uses a moment argument, and the result strengthens earlier decision-game bounds [Liu23].Source: §3.4 · p. 16
  • For a fixed online algorithm, its database-size-restricted operator norm equals the best bit-fixing advantage with at most P offline queries.Taking the supremum over online algorithms gives the section’s bit-fixing characterization.Source: §3.4 · pp. 16, 18
  • The operator characterization follows because offline states are supported on the database hierarchy, and every state with that support can be prepared using at most P queries and postselection.The construction establishes the converse as well as the upper bound.Source: §3.4 · p. 16

4 Improving Non-uniform Security for Salting

The section improves generic salting bounds for quantum advice and introduces a diffuse-game condition that yields stronger bounds when existing database information contributes only weakly.

4 Improving Non-uniform Security for Salting

  • Theorem 4.2 establishes non-uniform salting security with a decision-game bound improving on [Liu23, Theorem 7.5], for random-function or random-permutation F and at most one underlying-oracle query per QueryH call.Source: §4 · p. 19, §4.2 · p. 21

4.1 Salted Database Hierarchy

  • The salted database hierarchy tracks each salt-indexed oracle’s database size, with total size equal to the sum across salts.The hierarchy uses local database-size observables for each oracle register.Source: §4.1 · p. 20

4.2 Salting Defeats Quantum Advice

  • The generic salting argument applies to decision games even though their game operators need not be positive.For decision games, the proof uses the Hermitian-operator bound rather than the positive-square-root argument.Source: §4.2 · pp. 21–22

4.3 (γ, ∆)-Diffuse Games

  • A (γ, ∆)-diffuse game bounds advantage additively by a query-dependent baseline and a term that grows with expected database size.When expected database size is much smaller than ∆, the database contribution is weak; the argument does not require database and subsequent queries to act on orthogonal subspaces.Source: §4.3 · p. 23
  • For salted diffuse games, averaging over the challenge salt reduces the database contribution by replacing P with P/K while leaving the baseline unchanged.The resulting theorem applies to both search and decision games.Source: §4.3 · p. 23

5 Details of Applications

The applications use direct diffuse bounds for PRG and Yao’s box, and derive diffuse bounds for OWF and permutation inversion from bit-fixing results.

5 Details of Applications

  • PRG and Yao’s box receive direct diffuse analyses, whereas OWF and permutation inversion use known bit-fixing bounds to derive theirs.The formulations of these games follow prior work [CGLQ20] [ABC+26].Source: §5 · p. 24

5.1 PRG Game

  • The applications establish QAI bounds for PRG and salted PRG using a direct diffuse bound for the PRG game.The section states separate theorems for the unsalted and salted games.Source: §5.1 · p. 25

5.2 Yao’s Box

  • The applications establish QAI bounds for Yao’s box and its salted variant using a direct diffuse bound.The section states separate theorems for the unsalted and salted games.Source: §5.2 · pp. 26–27

5.3 OWF Game

  • The OWF application derives QAI bounds for both the base and salted games from an OWF diffuse bound.The diffuse bound uses parameters γ = 1 and ∆ = min{N, M}.Source: §5.3 · p. 28

5.4 Permutation inversion game

  • The permutation-inversion application establishes QAI bounds for the base and salted games, deriving the salted result from a diffuse bound.The permutation-inversion game uses γ = 1 and ∆ = N.Source: §5.4 · p. 29

A Missing Proofs

This section presents proofs omitted from earlier sections and fixes an orthonormal basis for the internal register.

A Missing Proofs

  • The appendix section supplies proofs omitted earlier and fixes an orthonormal basis for the internal register.The basis is denoted {|z⟩}Z.Source: A Missing Proofs · p. 31

A.1 Proof for the Uniform one-point reprogramming lemma

The appendix proves the uniform one-point reprogramming lemma using polynomial degree and boundedness, then derives diffuse bounds for decision games and proves Lemma 4.6 by controlling query-database growth.

A.1 Proof for the Uniform one-point reprogramming lemma

  • The reprogramming proof makes acceptance probability a degree-at-most-2T polynomial, enabling a derivative bound via Markov’s polynomial inequality.The acceptance probability is bounded because it averages acceptance probabilities; the derivative at zero isolates singleton terms.Source: §A.1 · pp. 31–32

A.2 Diffuse Bounds for Decision Games

  • A decision game satisfying the stated hypothesis is (1/2, ∆/(1 + ⌈log2 r⌉))-diffuse at query budget T.Here r := max{1, 2(TSample + T + TVerify)}.Source: §A.2 · p. 33

A.3 Proof of Lemma 4.6

  • Lemma 4.6’s proof controls database-size growth by at most r and bounds cross terms using positivity and Cauchy–Schwarz.The proof sets r := max{1, 2(TSample + T + TVerify)}.Source: §A.3 · p. 36

A.4 Proof of Lemma 5.2

The proof compares uniform and image experiments through oracle-conditioned states, then uses one-point reprogramming to bound their difference and cap the resulting operator norm.

A.4 Proof of Lemma 5.2

  • The uniform and image experiments use the same adversary unitary in the final comparison, isolating the change in the oracle-conditioned input states.The proof defines Φunif, Φ⋆, and Φimg by applying the corresponding adversary unitaries to Γunif and Γimg.Source: §A.4 · pp. 37–38
  • Conditioning on H and h fixes the challenge adversary while x varies uniformly, allowing the uniform one-point reprogramming lemma to apply.The resulting parenthesis is bounded by 4T²/N.Source: §A.4 · p. 38
  • Combining Eqs. (38), (42), and (41) with the triangle inequality proves Eq. (21); ∥E_H PRG∥op ≤ 1 for every H implies ∥M E_PRG∥op ≤ 1, giving the cap.On LP, using ⟨ψ|Λ|ψ⟩ ≤ P proves Eq. (22).Source: §A.4 · p. 39

A.5 Proof of Lemma 5.6

The proof adapts a prior argument and bounds both directions of the adversary’s decision, yielding a bound on its absolute advantage.

A.5 Proof of Lemma 5.6

  • Flipping the adversary’s output bit bounds the opposite direction of its winning probability, and combining both bounds controls |Pr[win] − 1/2|.The proof uses the same argument as [CGLQ20, Lemma 6.2].Source: §A.5 · p. 39

A.6 Proof of Lemma 5.10

The proof invokes a bound from Liu23 and applies Lemma 4.6 with parameters chosen for Lemma 5.10.

A.6 Proof of Lemma 5.10

  • For T ≥ 1, the proof absorbs the cited result’s implicit constant into CBF; it handles T = 0 by monotonicity and caps the bound by 1.It uses T² ≤ (T + 1)².Source: §A.6 · p. 40
  • The proof applies Lemma 4.6 to the cited Liu23 bound, using κ := CBF and ∆ := min{N, M}.The cited result is stated as Lemma A.3 and its constant is denoted CBF.Source: §A.6 · p. 40

A.7 Proof of Lemma 5.14

The proof uses a bound from [ABC+26, Lemma 2] to establish Lemma 5.14. It handles the zero-query case by monotonicity and absorbs the cited result’s implicit constant.

A.7 Proof of Lemma 5.14

  • For T ≥ 1, the proof uses [ABC+26, Lemma 2], absorbs its implicit constant into CBF, and bounds T^2 by (T + 1)^2.The T = 0 case follows by monotonicity from T = 1, and the cap by 1 is immediate.Source: §A.7 · p. 40
  • The proof applies the cited estimate to establish Lemma 5.14.The section explicitly identifies its task as proving Lemma 5.14.Source: §A.7 · p. 40
  • The proof derives the bound N + 2CBF(T + 1)^2 using Lemma 4.6 and the preceding inequality.The passage states this expression as the result of applying Lemma 4.6.Source: §A.7 · p. 40

B Database Size Increment per Query

The section bounds database growth under salted queries and the full purified game operator. It also shows that setting K = 1 recovers a bound for the base game.

B Database Size Increment per Query

  • A single family query increases total database size by at most one for random functions and random permutations.For permutations, the argument considers whether the queried input is already in the relevant database domain.Source: B Database Size Increment per Query · pp. 41–42
  • The salted purified game operator increases total database size by at most 2(TSample + T + TVerify).The purified operator uses at most TSample + T + TVerify underlying oracle queries; the same inclusion applies to search and decision games.Source: B Database Size Increment per Query · p. 42
  • When K = 1, the salted hierarchy and query interface reduce to those of the base game, yielding MELP ⊆ LP + 2(TSample + T + TVerify).The section applies the operator-size bound to this special case.Source: B Database Size Increment per Query · p. 42
Loading 2609.37467v1…