Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2609.37467

An Operator-Norm Approach to Security with Quantum Advice

Minki Hhan, Sunghyuk Jo, Qipeng Liu

quant-phcs.CRSubmitted Sep 28, 2026• Announced Sep 29, 2026• 0 citations
arXivHTMLPDF

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.

No sign of AI-generated textAI use disclosed
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.

Related papers

Lower Bounds for Preprocessing Attacks on Quantum Cryptography

Fangqi Dong, Alex Lombardi

We prove near-optimal lower bounds for preprocessing attacks on quantum cryptography in the random oracle model. Specifically, we show that a $T$-query adversary with $S$ qubits of non-uniform advice can recover a random key $k$ from the $n$-qubit binary phase state $|ψ_k\rangle \propto \sum_{x} R(k,x) |x\rangle$ with probability at most $O(\frac{T^2 + \sqrt{ST}}{N})$ for $N=2^n$. In contrast, the best known bound for post-quantum one-way functions is $O(\frac{T^2 + ST}{N})$, with a trivial attack at $S = N$. This demonstrates a new advantage of quantum cryptography over classical cryptography: $n$ qubits of communication suffice for security against preprocessing attacks with space up to $N^2$ rather than $N$. Our methodology is simple: express the optimal preprocessing attack as the operator norm of a random matrix, and bound this value in expectation over the random oracle via the trace-moment method. These trace moments have a natural interpretation using compressed oracles [Zhandry, Crypto 2019], which we then analyze. This can be viewed as a simplification and generalization of the approach of Liu [Eurocrypt 2023] for proving the security of post-quantum cryptography against preprocessing attacks. We also prove the following results: (1) We tighten Liu's analysis of post-quantum PRGs in QROM, achieving a distinguishing advantage bound of $O(\frac{T^2}N + \sqrt{\frac{ST}N})$. (2) For unitary synthesis, we extend the one-query lower bound of Lombardi-Ma-Wright [STOC 2024] to hold against adversaries that can make one arbitrary function query along with polynomially many (adaptive) queries to the random oracle, either before or after the function query. This also interprets the original LMW24 result in terms of compressed oracles. (3) Finally, we prove a tight $O(\frac{\sqrt{S}}N)$ bound for the pseudorandomness of random binary phase states against space $S$ distinguishers.

quant-pharXiv:2610.02101•Oct 2, 2026•1 citation

Tight Quantum Time-Space Tradeoffs for Function Inversion

Kai-Min Chung, Siyao Guo, Qipeng Liu +1 more

In function inversion, we are given a function f:[N]→[N], and want to prepare some advice of size S, such that we can efficiently invert any image in time T. This is a well studied problem with profound connections to cryptography, data structures, communication complexity, and circuit lower bounds. Investigation of this problem in the quantum setting was initiated by Nayebi, Aaronson, Belovs, and Trevisan (2015), who proved a lower bound of ST2=Ω̃(N) for random permutations against classical advice, leaving open an intriguing possibility that Grover's search can be sped up to time Õ(√{N/S}). Recent works by Hhan, Xagawa, and Yamakawa (2019), and Chung, Liao, and Qian (2019) extended the argument for random functions and quantum advice, but the lower bound remains ST2=Ω̃(N). In this work, we prove that even with quantum advice, ST+ T2=Ω̃(N), is required for an algorithm to invert random functions. This demonstrates that Grover's search is optimal for S=Õ(√N), ruling out any substantial speed-up for Grover's search even with quantum advice. Further improvements to our bounds would imply new classical circuit lower bounds, as shown by Corrigan-Gibbs and Kogan (2019). To prove this result, we develop a general framework for establishing quantum time-space lower bounds. We further demonstrate the power of our framework by proving the following results. (a) Yao's box problem: We prove a tight quantum time-space lower bound for classical advice. For quantum advice, we prove a first time-space lower bound using shadow tomography. These results resolve two open problems posted by Nayebi et al (2015). (b) Salted cryptography: We show that “salting generically provably defeats preprocessing,” a result shown by Coretti, Dodis, Guo, and Steinberger (2018), also holds in the quantum setting. In particular, we prove quantum time-space lower bounds for a wide class of salted cryptographic primitives in the quantum random oracle model. This yields the first quantum time-space lower bound for salted collision-finding, which in turn implies that PWPPO⊈ FBQPO/qpoly relative to a random oracle O.

arXiv:2006.05650•Annual Symposium on Foundations of Computer Science•Nov 1, 2020•50 citations

Towards Simple and Useful One-Time Programs in the Quantum Random Oracle Model

Lev Stambler

We construct simulation-secure one-time memories (OTM) in the random oracle model, and present a plausible argument for their security against quantum adversaries with bounded and adaptive depth. Our contributions include: (1) A simple scheme where we use only single-qubit Wiesner states and conjunction obfuscation (constructible from LPN): no complex entanglement or quantum cryptography is required. (2) A new POVM bound where e prove that any measurement achieving $(1 - ε)$ success on one basis has conjugate-basis guessing probability at most $\frac{1}{2m} + O(ε^\frac{1}{4})$. (3) Simultation-secure OTMs in the quantum random oracle model where an adversary can only query the random oracle classically. (4) Adaptive depth security where, via an informal application of a lifting theorem from Arora et al., we conjecture security against adversaries with polynomial quantum circuit depth between random oracle queries. Security against adaptive, depth-bounded, quantum adversaries captures many realistic attacks on OTMs built from single-qubit states; our work thus paves the way for practical and truly secure one-time programs. Moreover, depth bounded adaptive adversarial models may allow for encoding one-time memories into error corrected memory states, opening the door to implementations of one-time programs which persist for long periods of time.

quant-pharXiv:2601.13258•Jan 20, 2026•0 citations

Indistinguishability Lifting for Keyed Oracles, Compressed Ideal Cipher, and More Applications

Ritam Bhaumik, Yu-Hsuan Huang

Cryptographic security proofs often involve an adversary interacting with a larger, keyed oracle that consists of (potentially exponentially) many independent instances of a smaller, base oracle. However, showing quantum indistinguishability between two such keyed oracles can be tricky, since a single query made by an adversary may involve a superposition that covers all instances of the base oracles simultaneously. In this paper, we establish a generic indistinguishability lifting theorem of the following form: if the two base oracles are indistinguishable under quantum queries, then their corresponding keyed oracles are too, up to an O(q^2) multiplicative loss in distinguishing advantage, where q is the number of queries made by the adversary. Our lifting theorem applies to both statistical and computational settings, and to oracles that are stateful as well. It is also optimal in that it matches the obvious Grover search attack for a certain (contrived) choice of oracles. As an immediate application, we extend Carolan's compressed permutation oracle to an efficiently implementable compressed ideal cipher, and use it to prove preimage resistance of the Davies-Meyer compression function in the quantum ideal cipher model. Thanks to our lifting theorem, the soundness of our compressed ideal cipher reduces to that of Carolan's oracle, and any further improvement on the latter would automatically carry over to the former. As our second application, we give a modular construction that doubles the message length of any quantum-secure strong pseudorandom permutation. Along the way, we show that an existing two-round tweakable Feistel construction is indistinguishable from a random permutation under quantum bidirectional queries. This is done via a dedicated polynomial-method argument, which may be of independent interest.

cs.CRCross-listedarXiv:2610.04674•Oct 6, 2026•0 citations

Tight Bounds for Inverting Permutations via Compressed Oracle Arguments

Ansis Rosmanis

In his seminal work on recording quantum queries [Crypto 2019], Zhandry studied interactions between quantum query algorithms and the quantum oracle corresponding to random functions. Zhandry presented a framework for interpreting various states in the quantum space of the oracle as databases of the knowledge acquired by the algorithm and used that interpretation to provide security proofs in post-quantum cryptography. In this paper, we introduce a similar interpretation for the case when the oracle corresponds to random permutations instead of random functions. Because both random functions and random permutations are highly significant in security proofs, we hope that the present framework will find applications in quantum cryptography. Additionally, we show how this framework can be used to prove that the success probability for a k-query quantum algorithm that attempts to invert a random N-element permutation is at most O(k^2/N).

arXiv:2103.08975•Mar 16, 2021•21 citations

A Quantum "Lifting Theorem" for Constructions of Pseudorandom Generators from Random Oracles

Jonathan I. Katz, Sela, Ben

We study the (quantum) security of pseudorandom generators (PRGs) constructed from random oracles. We prove a "lifting theorem" showing, roughly, that if such a PRG is unconditionally secure against classical adversaries making polynomially many queries to the random oracle, then it is also (unconditionally) secure against quantum adversaries in the same sense. As a result of independent interest, we also show that any pseudo-deterministic quantum-oracle algorithm (i.e., a quantum algorithm that with high probability returns the same value on repeated executions) can be simulated by a computationally unbounded but query bounded classical-oracle algorithm with only a polynomial blowup in the number of queries. This implies as a corollary that our lifting theorem holds even for PRGs that themselves make quantum queries to the random oracle.

arXiv:2401.14319•Jan 25, 2024•1 citation
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.
The paper studies security against quantum adversaries receiving SSS qubits of oracle-dependent advice before a fresh challenge and making TTT 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 2\sqrt{2}2​ times quantum bit-fixing advantage with P=2S(TSamp+T+TVer)P=2S(T_{\mathrm{Samp}}+T+T_{\mathrm{Ver}})P=2S(TSamp​+T+TVer​) offline queries. Unlike previous reductions, it applies directly to distinguishing bias rather than success probability. For T≥1T\ge1T≥1, this yields Yao’s-box advantage O(ST/N)O(\sqrt{ST/N})O(ST/N​), matching known attacks up to constants, and PRG advantage O(ST/N+T2/N)O(\sqrt{ST/N}+T^2/N)O(ST/N​+T2/N), improving the previous cube-root preprocessing term and square-root query term.
For KKK independent salt-indexed oracles, the generic decision-game bound is O(ϵG(T)+Sr/K)O(\epsilon_{\mathcal G}(T)+\sqrt{Sr/K})O(ϵG​(T)+Sr/K​), where r=2(TSamp+T+TVer)r=2(T_{\mathrm{Samp}}+T+T_{\mathrm{Ver}})r=2(TSamp​+T+TVer​); the salt-dependent term is optimal in general. Construction-specific analysis gives salted PRG advantage O(ST/(KN)+T2/N)O(\sqrt{ST/(KN)}+T^2/N)O(ST/(KN)​+T2/N) and permutation-inversion success O(ST/(KN)+T2/N)O(ST/(KN)+T^2/N)O(ST/(KN)+T2/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.
We prove near-optimal lower bounds for preprocessing attacks on quantum cryptography in the random oracle model. Specifically, we show that a TTT-query adversary with SSS qubits of non-uniform advice can recover a random key kkk from the nnn-qubit binary phase state ∣ψk⟩∝∑xR(k,x)∣x⟩|ψ_k\rangle \propto \sum_{x} R(k,x) |x\rangle∣ψk​⟩∝∑x​R(k,x)∣x⟩ with probability at most O(T2+STN)O(\frac{T^2 + \sqrt{ST}}{N})O(NT2+ST​​) for N=2nN=2^nN=2n. In contrast, the best known bound for post-quantum one-way functions is O(T2+STN)O(\frac{T^2 + ST}{N})O(NT2+ST​), with a trivial attack at S=NS = NS=N. This demonstrates a new advantage of quantum cryptography over classical cryptography: nnn qubits of communication suffice for security against preprocessing attacks with space up to N2N^2N2 rather than NNN. Our methodology is simple: express the optimal preprocessing attack as the operator norm of a random matrix, and bound this value in expectation over the random oracle via the trace-moment method. These trace moments have a natural interpretation using compressed oracles [Zhandry, Crypto 2019], which we then analyze. This can be viewed as a simplification and generalization of the approach of Liu [Eurocrypt 2023] for proving the security of post-quantum cryptography against preprocessing attacks. We also prove the following results: (1) We tighten Liu's analysis of post-quantum PRGs in QROM, achieving a distinguishing advantage bound of O(T2N+STN)O(\frac{T^2}N + \sqrt{\frac{ST}N})O(NT2​+NST​​). (2) For unitary synthesis, we extend the one-query lower bound of Lombardi-Ma-Wright [STOC 2024] to hold against adversaries that can make one arbitrary function query along with polynomially many (adaptive) queries to the random oracle, either before or after the function query. This also interprets the original LMW24 result in terms of compressed oracles. (3) Finally, we prove a tight O(SN)O(\frac{\sqrt{S}}N)O(NS​​) bound for the pseudorandomness of random binary phase states against space SSS distinguishers.
In function inversion, we are given a function f:[N]→[N], and want to prepare some advice of size S, such that we can efficiently invert any image in time T. This is a well studied problem with profound connections to cryptography, data structures, communication complexity, and circuit lower bounds. Investigation of this problem in the quantum setting was initiated by Nayebi, Aaronson, Belovs, and Trevisan (2015), who proved a lower bound of ST2=Ω̃(N) for random permutations against classical advice, leaving open an intriguing possibility that Grover's search can be sped up to time Õ(√{N/S}). Recent works by Hhan, Xagawa, and Yamakawa (2019), and Chung, Liao, and Qian (2019) extended the argument for random functions and quantum advice, but the lower bound remains ST2=Ω̃(N). In this work, we prove that even with quantum advice, ST+ T2=Ω̃(N), is required for an algorithm to invert random functions. This demonstrates that Grover's search is optimal for S=Õ(√N), ruling out any substantial speed-up for Grover's search even with quantum advice. Further improvements to our bounds would imply new classical circuit lower bounds, as shown by Corrigan-Gibbs and Kogan (2019). To prove this result, we develop a general framework for establishing quantum time-space lower bounds. We further demonstrate the power of our framework by proving the following results. (a) Yao's box problem: We prove a tight quantum time-space lower bound for classical advice. For quantum advice, we prove a first time-space lower bound using shadow tomography. These results resolve two open problems posted by Nayebi et al (2015). (b) Salted cryptography: We show that “salting generically provably defeats preprocessing,” a result shown by Coretti, Dodis, Guo, and Steinberger (2018), also holds in the quantum setting. In particular, we prove quantum time-space lower bounds for a wide class of salted cryptographic primitives in the quantum random oracle model. This yields the first quantum time-space lower bound for salted collision-finding, which in turn implies that PWPPO⊈ FBQPO/qpoly relative to a random oracle O.
We construct simulation-secure one-time memories (OTM) in the random oracle model, and present a plausible argument for their security against quantum adversaries with bounded and adaptive depth. Our contributions include: (1) A simple scheme where we use only single-qubit Wiesner states and conjunction obfuscation (constructible from LPN): no complex entanglement or quantum cryptography is required. (2) A new POVM bound where e prove that any measurement achieving (1−ε)(1 - ε)(1−ε) success on one basis has conjugate-basis guessing probability at most 12m+O(ε14)\frac{1}{2m} + O(ε^\frac{1}{4})2m1​+O(ε41​). (3) Simultation-secure OTMs in the quantum random oracle model where an adversary can only query the random oracle classically. (4) Adaptive depth security where, via an informal application of a lifting theorem from Arora et al., we conjecture security against adversaries with polynomial quantum circuit depth between random oracle queries. Security against adaptive, depth-bounded, quantum adversaries captures many realistic attacks on OTMs built from single-qubit states; our work thus paves the way for practical and truly secure one-time programs. Moreover, depth bounded adaptive adversarial models may allow for encoding one-time memories into error corrected memory states, opening the door to implementations of one-time programs which persist for long periods of time.
Cryptographic security proofs often involve an adversary interacting with a larger, keyed oracle that consists of (potentially exponentially) many independent instances of a smaller, base oracle. However, showing quantum indistinguishability between two such keyed oracles can be tricky, since a single query made by an adversary may involve a superposition that covers all instances of the base oracles simultaneously. In this paper, we establish a generic indistinguishability lifting theorem of the following form: if the two base oracles are indistinguishable under quantum queries, then their corresponding keyed oracles are too, up to an O(q^2) multiplicative loss in distinguishing advantage, where q is the number of queries made by the adversary. Our lifting theorem applies to both statistical and computational settings, and to oracles that are stateful as well. It is also optimal in that it matches the obvious Grover search attack for a certain (contrived) choice of oracles. As an immediate application, we extend Carolan's compressed permutation oracle to an efficiently implementable compressed ideal cipher, and use it to prove preimage resistance of the Davies-Meyer compression function in the quantum ideal cipher model. Thanks to our lifting theorem, the soundness of our compressed ideal cipher reduces to that of Carolan's oracle, and any further improvement on the latter would automatically carry over to the former. As our second application, we give a modular construction that doubles the message length of any quantum-secure strong pseudorandom permutation. Along the way, we show that an existing two-round tweakable Feistel construction is indistinguishable from a random permutation under quantum bidirectional queries. This is done via a dedicated polynomial-method argument, which may be of independent interest.
In his seminal work on recording quantum queries [Crypto 2019], Zhandry studied interactions between quantum query algorithms and the quantum oracle corresponding to random functions. Zhandry presented a framework for interpreting various states in the quantum space of the oracle as databases of the knowledge acquired by the algorithm and used that interpretation to provide security proofs in post-quantum cryptography. In this paper, we introduce a similar interpretation for the case when the oracle corresponds to random permutations instead of random functions. Because both random functions and random permutations are highly significant in security proofs, we hope that the present framework will find applications in quantum cryptography. Additionally, we show how this framework can be used to prove that the success probability for a k-query quantum algorithm that attempts to invert a random N-element permutation is at most O(k^2/N).
We study the (quantum) security of pseudorandom generators (PRGs) constructed from random oracles. We prove a "lifting theorem" showing, roughly, that if such a PRG is unconditionally secure against classical adversaries making polynomially many queries to the random oracle, then it is also (unconditionally) secure against quantum adversaries in the same sense. As a result of independent interest, we also show that any pseudo-deterministic quantum-oracle algorithm (i.e., a quantum algorithm that with high probability returns the same value on repeated executions) can be simulated by a computationally unbounded but query bounded classical-oracle algorithm with only a polynomial blowup in the number of queries. This implies as a corollary that our lifting theorem holds even for PRGs that themselves make quantum queries to the random oracle.