arXiv:2609.37467
An Operator-Norm Approach to Security with Quantum Advice
Minki Hhan, Sunghyuk Jo, Qipeng Liu
Abstract
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.
AI Summary
The paper studies security against quantum adversaries receiving $S$ qubits of oracle-dependent advice before a fresh challenge and making $T$ online queries. It considers random functions and random permutations, with forward-only permutation access, and asks how preprocessing affects search and distinguishing games, including salted constructions. Its central reduction bounds quantum-advice advantage by $\sqrt{2}$ times quantum bit-fixing advantage with $P=2S(T_{\mathrm{Samp}}+T+T_{\mathrm{Ver}})$ offline queries. Unlike previous reductions, it applies directly to distinguishing bias rather than success probability. For $T\ge1$, this yields Yao’s-box advantage $O(\sqrt{ST/N})$, matching known attacks up to constants, and PRG advantage $O(\sqrt{ST/N}+T^2/N)$, improving the previous cube-root preprocessing term and square-root query term. For $K$ independent salt-indexed oracles, the generic decision-game bound is $O(\epsilon_{\mathcal G}(T)+\sqrt{Sr/K})$, where $r=2(T_{\mathrm{Samp}}+T+T_{\mathrm{Ver}})$; the salt-dependent term is optimal in general. Construction-specific analysis gives salted PRG advantage $O(\sqrt{ST/(KN)}+T^2/N)$ and permutation-inversion success $O(ST/(KN)+T^2/N)$, with the latter tight up to logarithmic factors. The proofs represent advantage by Hermitian game operators, control high spectral moments using database-size-restricted operator norms, and characterize those norms through postselected bit-fixing experiments. A “diffuseness” condition separates existing-database information from online queries; a polynomial-method reprogramming bound sharpens PRG security. The PRG bound still leaves a gap to known attacks. Salted random-function inversion inherits the classical inversion gap, with matching guarantees only in specified parameter regimes. All guarantees concern idealized oracle models.
The current manuscript is entirely written by the authors based on this understanding, with assistance from ChatGPT-6 Astra in improving its presentation.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.