PaperlayerView exact revision on arXiv

Source-linked AI summary

Blind Unforgeability implies Plus-One Unforgeability

Mehil Agarwal, Calliope S. Reimann, Fang Song

arXiv:2610.00517v1quant-phcs.CR

TL;DR

The paper addresses the unresolved relationship between quantum BU and PO in a setting where superposition access complicates the classical notion of freshness. It constructs a reduction from PO to BU, proving that BU implies PO and is strictly stronger.

  • Problem

    Quantum superposition access makes the classical criterion of predicting a tag at an unqueried point inapplicable, and the relationship between BU and PO remained unresolved.

    Source: §1 · p. 2

  • Method

    The reduction reshapes a PO attacker's coherent query-history contributions and constructs a singleton-puncture adversary.

    Source: §4.1 · p. 15, §4.4 · p. 24

  • Results

    Blind-unforgeability implies plus-one unforgeability for any quantum-accessible keyed function family.

    Source: §1 · p. 3

  • Takeaways & Limitations

    BU is strictly stronger than PO in the quantum setting.

    Source: §1 · p. 3

    The quantitative reduction loses a polynomial factor in query complexity, and the optimal loss remains open.

    Source: §1.2 · p. 6

Abstract

from arXiv · show

We prove that quantum blind-unforgeability implies quantum plus-one unforgeability, settling an open question in the literature. Since plus-one unforgeability is known not to imply blind-unforgeability, our result establishes that blind-unforgeability is \emph{strictly stronger} than plus-one unforgeability in the quantum setting. The implication is proven using a new \emph{smoothing} technique that coherently rescales the query histories of a quantum-query algorithm in a black-box manner. This enables us to transform any successful plus-one attacker into a blind-unforgeability attacker with only inverse-polynomial loss. Our proof represents a conceptual shift from merely extracting a useful query history as in earlier attempts, which we show inevitably fails in general, to first coherently reshaping how query histories interfere.

1 Introduction

The paper resolves the relationship between quantum blind-unforgeability (BU) and plus-one unforgeability (PO): BU implies PO, and the paper characterizes BU as strictly stronger. Its reduction first reshapes coherent query-history interference, because successful histories can cancel and defeat direct extraction of an omitted point.

1 Introduction

  • Quantum superposition access makes classical freshness at an unqueried point inapplicable, leaving the relationship between counting-based PO and withholding-based BU unresolved.PO asks for q + 1 distinct valid pairs after q queries; BU tests for a valid forgery at a point whose value was withheld.Source: §1 · p. 2
  • BU implies PO for any quantum-accessible keyed function family, establishing BU as strictly stronger than PO.The reduction turns a q-query PO attacker into a BU attacker with at most 3q + 1 queries and only polynomial loss in a noticeable advantage.Source: §1 · p. 3

1.1 Technical overview

  • Directly extracting an omitted reported point can fail: successful histories may cancel at every point, despite PO success approaching one.The all-or-nothing example shows that existing zero-touch histories need not provide a usable leave-one-out witness.Source: §1.1 · pp. 3–4
  • Poisson smoothing coherently reweights query histories with random phases, detuning cancellations without measuring or recording those histories.Averaging assigns different weights to histories according to how many reported points they omit, making zero-touch contribution visible along the interpolation.Source: §1.1 · pp. 4–5
  • After smoothing, a root-of-unity touch-count twirl separates zero-touch histories from positive-touch components during punctured execution.A fixed puncture can alter histories that query it, so their amplitudes could otherwise interfere destructively with the desired zero-touch sector.Source: §1.1 · p. 6
  • The paper relates singleton-puncture completion density to BU by treating it as the derivative of BU success at blinding rate β = 0.Polynomial degree bounds imply that noticeable density yields BU advantage Ω(δ/q3), with an O(q2) loss from density to BU success.Source: §1.1 · p. 6

1.2 Discussions

  • The quantitative reduction loses a polynomial factor in query complexity, and the paper leaves the optimal loss open.The discussion asks which losses are inherent.Source: §1.2 · p. 6
  • The proof offers an alternative to recording or reprogramming queries: random phases modify relative history weights while preserving coherent interference.The discussion identifies this approach as complementary to recording, compressed-oracle, and reprogramming techniques.Source: §1.2 · p. 7

2 Preliminaries

The preliminaries set notation for Bernoulli blinding and basic inequalities, then describe quantum-query histories as a coherent analytic decomposition. They define omitted reported inputs and filters for isolating valid outputs that include a point never queried.

2.1 Notations and Useful Facts

  • The notation defines Bernoulli blinding as independently including each domain point with probability β.The preliminaries also specify poly(λ) as an unspecified polynomial in the security parameter.Source: §2.1 · p. 7

2.2 Quantum Oracles and Query Algorithms

  • A query history is an analytic decomposition of a quantum algorithm, not a recorded transcript; its history amplitudes remain coherent and may interfere.The history is a sequence of query addresses, and the reduction does not measure or record those addresses.Source: §2.2 · p. 8
  • For a successful history reporting q + 1 distinct inputs after q queries, at least one reported input is omitted from its queries.The omitted-output set consists of the reported inputs never touched by that history.Source: §2.2 · p. 9
  • The singleton zero-touch mass isolates histories that never query a chosen reported point and outputs that are valid under the key and include that point.The definition uses a zero-touch filter and a projection onto valid output-forgery pairs containing the candidate point.Source: §2.2 · p. 10

3 BU Equals Singleton-Puncture Density Unforgeability

The section characterizes blind-unforgeability through singleton-puncture density and proves the two notions equivalent. It gives reductions in both directions, using polynomial bounds to turn a noticeable density into a BU attack.

3.1 Formulating Singleton-Puncture Density Unforgeability

  • For every efficiently computable keyed family, BU security is equivalent to singleton-puncture density security.The section defines ∂BU security by requiring the density to be negligible for every quantum polynomial-time algorithm.Source: §3.1 · p. 10
  • Singleton-puncture density is the derivative of BU success at β = 0; its unnormalized form remains useful even on exponential domains.Normalizing by the probability of a uniform singleton can make noticeable density exponentially small, so the unnormalized density is the relevant intermediate quantity.Source: §3.1 · p. 11

3.2 ∂BU implies BU

  • Given a BU attacker at rate β, C_A,β further blinds a singleton-punctured oracle and achieves density at least G_A(β)/β with at most 2q queries.The additional blinding set includes each other input independently with probability β.Source: §3.2 · pp. 11–12

3.3 BU implies ∂BU

  • The bound GA(β) ≥ ρF(A)/[2(2q+1)^2] incurs only an O(q^2) loss; when ρF(A) is noticeable, A yields a valid BU adversary with noticeable winning probability.The second bound gives an explicit, though weaker, blinding rate.Source: §3.3 · pp. 12–13

4 ∂BU implies PO

This section proves that blind-unforgeability (including singleton-punctured density unforgeability) implies plus-one unforgeability by transforming successful plus-one adversaries using phase smoothing and singleton-density extraction. It also presents a finite-precision implementation of smoothing and bounds the transformation’s loss and oracle queries.

4.1 PO Adversary Smoothing

  • Randomized phase smoothing reshapes query histories so successful zero-touch histories can be used to convert a PO adversary into a ∂BU attacker.The construction samples t uniformly from [0, 1] and phases z, applies address-dependent phases before oracle calls, and compensates on the output; the resulting t-adjusted superposition gives priority to histories with fewer forgeries.Source: §4.1 · pp. 14–15

4.2 Singleton Density Extraction

  • Singleton extraction filters histories that never query the puncture, then tests the q + 1 claimed messages and returns the pair at the punctured input.The extraction uses at most 3q + 1 oracle queries, and its success probability is at least that of the PO adversary.Source: §4.2 · pp. 18–20

4.3 Finite-Precision Efficient Implementation

  • The continuous smoothing phases admit a polynomial-sized finite-precision implementation whose total error is negligible when q is polynomial in the security parameter.The implementation truncates t to [0, 1 − τ] and chooses discretization errors ε_t = O(τ^3) and ε_u = O(τ^2).Source: §4.3 · pp. 20, 21, 23

4.4 Putting it Together

  • A q-query PO adversary succeeding with probability δ yields an efficient singleton-puncture adversary using at most 3q + 1 queries and achieving ρF(C) ≥ δ/[4(q + 1)] − negl(λ).The implication uses Poisson smoothing followed by singleton zero-touch extraction.Source: §4.4 · p. 24
  • A q-query plus-one adversary winning with probability δ yields an efficient BU adversary using at most 3q + 1 queries and winning with probability at least δ/(8(q + 1)(6q + 3)^2) − negl(λ).The section concludes that BU security therefore implies PO security.Source: §4.4 · p. 24

5 Ruling Out Raw Singleton Extractions

The section shows that successful plus-one attacks can have no usable raw singleton zero-touch component because different query histories cancel. Poisson smoothing reweights omission layers, detuning that cancellation before singleton extraction.

5 Ruling Out Raw Singleton Extractions

  • A plus-one attacker can succeed with probability approaching one while its singleton zero-touch mass is identically zero.Thus raw extraction from the attacker's unmodified interference pattern need not yield a usable witness.Source: §5 · p. 25
  • For each reported point, two branches contribute equal and opposite singleton zero-touch amplitudes, giving exact cancellation.The example's omitted sets are the full output set and a singleton, respectively.Source: §5 · p. 26
  • The construction shows that histories can cancel under coherent regrouping despite every successful history omitting at least one reported point.This motivates reshaping the interference pattern before extracting a zero-touch witness.Source: §5 · p. 26
  • Poisson smoothing reweights a successful history omitting r reported points by t^(2r−1), changing the relative weights of omission layers.At t = 1 the original computation is recovered; for 0 < t < 1, the example's formerly cancelling amplitude is nonzero.Source: §5 · pp. 26–27

A Algebraic Property of BU success and ρF

The section expresses blind-unforgeability success under Bernoulli blinding as a polynomial in the blinding rate. Its value at zero is zero, and its derivative there is determined by singleton blind sets, yielding the singleton-puncture density.

A Algebraic Property of BU success and ρF

Loading 2610.00517v1…