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:2611.00609

Compressed Oracle Duality: A simple framework for knowing what quantum adversaries know

Matthew Ding, Mark Zhandry

quant-phcs.CCcs.CRcs.DSSubmitted Oct 31, 2026• Announced Nov 3, 2026• 0 citations
arXivHTMLPDF

Abstract

Given a quantum adversary that queries a random oracle, how do we characterize the information that they "know"? The Compressed Oracle method of Zhandry (CRYPTO 2019) is one method that records the queries that the adversary makes; this recording serves as a representation of the information that is learned. However, a significant limitation of the Compressed Oracle method is that it may continue to store information that the adversary has "forgotten." This issue is especially pertinent in the space-bounded setting, where the adversary may uncompute information to free up space, while the information may still reside in the compressed oracle. In this work, we present a simple and interpretable framework called "Compressed Oracle Duality," which extends the Compressed Oracle method for space-bounded algorithms. By applying an isometry to the memory of a quantum adversary, we obtain a pair of compressed oracles with identical marginal distributions and classical correlations which correspond to the knowledge the adversary retains. In fact, we show that the outcome of measuring the new compressed oracle database corresponds exactly to applying the pretty-good measurement on the adversary's memory. As an application of our framework for collision search, we give a simplified proof of the recent $T^2S = Ω(N\log N)$ quantum time-space tradeoff for label-symmetric algorithms due to Magniez-Zur (arXiv:2609.10808); we also prove a stronger classical tradeoff of $TS=Ω(N\log N)$ assuming label symmetry. The proofs under our framework do not require representation theory and instead bound the mutual information between the compressed oracle pairs. This highlights both how the label symmetry assumption bypasses known proof barriers as well as the challenges that remain in achieving unconditional quantum time-space tradeoffs.

AI Summary

The paper asks how to characterize information a space-bounded quantum algorithm retains about a random oracle, rather than information recorded in its query history. A compressed-oracle database can remain large even after the algorithm has forgotten individual outputs, obstructing direct space bounds. “Compressed Oracle Duality” canonically re-encodes the algorithm’s memory as a second database: if $A$ is the joint state’s coefficient matrix and $G=A^\dagger A$, the new joint state has coefficient matrix $\sqrt G$. The two measured databases have identical marginals; measuring the dual database implements the pretty-good measurement on the memory. Their classical mutual information is at most $S$ for $S$ qubits. Potentials counting certificates shared by both databases bound query-free extraction success, with quantitative slack. An unconditional shared-point bound gives $O(S/\log N)$ expected shared entries after at most $\sqrt N$ queries. For collision search in a random function with range size $N$, the framework reproves the existing label-symmetric quantum tradeoff $T^2S=\Omega(N\log N)$ without representation theory. The proof bounds matched labels through mutual information and unmatched labels through symmetry and compressed-oracle validity. A separate branching-program comparison with an injective oracle establishes the classical label-symmetric bound $TS=\Omega(N\log N)$. No unrestricted collision tradeoff follows: the proposed per-query joint-potential bound has counterexamples, and label symmetry excludes Pollard’s rho. The general memory characterization assumes no intermediate measurements; only the label-symmetric application is extended to measurements under a conditional symmetry assumption.

No sign of AI-generated textAI use disclosedStrong assumptions
the authors used ChatGPT 6 Astra along with this new framework to develop the simplified proofs.

Central claim may not hold: The abstract presents the retained-knowledge framework without an intermediate-measurement restriction, although the general characterization is established only for unitary algorithms and the paper explicitly leaves knowledge characterization after intermediate measurements open.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
34 pages

Related papers

Quantum Lazy Sampling and Path Recording for Any Group

Ben Foxman, Alex Lombardi, Fermi Ma +2 more

A central challenge in quantum algorithms and cryptography is reasoning about algorithms with oracle access to a random group element (e.g. a random function, permutation, or unitary). Can we efficiently simulate such algorithms? Can we determine what they know after t queries? A classical tool for this is lazy sampling: the oracle does not commit to the full group element upfront, but rather samples partial information about it on the fly. We study a quantum analog of lazy sampling: compressed oracles (or recording oracles). These are quantum data structures that allow on-the-fly simulation for quantum queries, originally introduced by Zhandry (CRYPTO '19) for random functions, and generalized to unitaries by Ma-Huang (STOC '25) and permutations by Carolan (STOC '26), and used to great effect in security proofs and lower bounds due to their interpretability. We define and analyze a general-purpose and interpretable path-recording oracle, derived from first principles, that perfectly simulates random elements of any closed subgroup of $U(N)$. Our oracle stores, in superposition, t input-output pairs, with updates described in terms of the commutant of the group's tensor power representation. This transparently records the information the algorithm has learned. Our oracle builds on recent work of Grinko-Yoshida (QIP '26), who gave a different general-purpose compressed oracle without clear interpretability. One interesting application of our path-recording is allowing direct comparisons between compressed oracles of different groups, giving a new technique for proving pseudorandomness results. For example, comparing $S_N$ and $U(N)$ yields what is arguably the simplest construction to date of pseudorandom unitaries: the product PC of a pseudorandom permutation and a random Clifford, improving on the prior PFC construction (Metger-Poremba-Sinha-Yuen, FOCS '24; Ma-Huang, STOC '25).

quant-pharXiv:2606.30281•Jun 30, 2026•12 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

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 Time-Space Lower Bounds for Collision Finding and Element Distinctness under Label Symmetry

Frédéric Magniez, Sebastian Zur

How much memory is needed to retain the quantum speedup for collision finding? For a uniformly random function $f:[N]\to [N]$, the BHT algorithm finds a collision using $O(N^{1/3})$ queries and a quantumly accessible classical table containing $O(N^{1/3})$ input-output pairs, whereas a logarithmic-space Grover search uses $O(\sqrt N)$ queries. Determining the optimal query-space tradeoff between these extremes remains a major open problem. We resolve this equation within the class of label-symmetric algorithms, which treat the function $f$'s output labels as interchangeable. We prove that such algorithm that makes $T$ queries, uses $S$ qubits, and finds a collision in a uniformly random function $f:[M]\to [N]$ with constant probability satisfies $$T=Ω(N^{1/3}) \qquad\text{and}\qquad T^2S=Ω(N\log N).$$ For the setting where $M=N$, these bounds are matched by a space-efficient implementation of the BHT algorithm. As a consequence of our tradeoff, any label-symmetric algorithm for the search version of Element Distinctness on $f: [n] \to [n^2]$ must satisfy $$T=Ω(n^{2/3}) \qquad\text{and}\qquad T^2S=Ω(n^2\log n),$$ matching Ambainis's quantum walk. Thus, both tradeoffs are optimal within the class of label-symmetric algorithms. To prove these results, we develop a space-sensitive version of the compressed oracle technique. The compressed oracle records the information learned by the algorithm in an evolving superposition of databases. Using label symmetry and representation theory, we show that an algorithm using $S$ qubits can effectively retain information about only $O(S/\log N)$ collision-free database entries. Substituting this estimate into the compressed oracle technique yields the stated tradeoffs.

quant-pharXiv:2609.10808•Sep 11, 2026•1 citation

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

Compressed Permutation Oracles

Joseph Carolan

The analysis of quantum algorithms which query random, invertible permutations has been a long-standing challenge in cryptography. Many techniques which apply to random oracles fail, or are not known to generalize to this setting. As a result, foundational cryptographic constructions involving permutations often lack quantum security proofs. With the aim of closing this gap, we develop and prove soundness of a compressed permutation oracle. Our construction shares many of the attractive features of Zhandry's original compressed function oracle: the purification is a small list of input-output pairs which meaningfully reflect an algorithm's knowledge of the oracle.

arXiv:2509.18586•ACM Symposium on Theory of Computing (STOC)•Jun 9, 2026•13 citations
Given a quantum adversary that queries a random oracle, how do we characterize the information that they "know"? The Compressed Oracle method of Zhandry (CRYPTO 2019) is one method that records the queries that the adversary makes; this recording serves as a representation of the information that is learned. However, a significant limitation of the Compressed Oracle method is that it may continue to store information that the adversary has "forgotten." This issue is especially pertinent in the space-bounded setting, where the adversary may uncompute information to free up space, while the information may still reside in the compressed oracle.
In this work, we present a simple and interpretable framework called "Compressed Oracle Duality," which extends the Compressed Oracle method for space-bounded algorithms. By applying an isometry to the memory of a quantum adversary, we obtain a pair of compressed oracles with identical marginal distributions and classical correlations which correspond to the knowledge the adversary retains. In fact, we show that the outcome of measuring the new compressed oracle database corresponds exactly to applying the pretty-good measurement on the adversary's memory.
As an application of our framework for collision search, we give a simplified proof of the recent T2S=Ω(Nlog⁡N)T^2S = Ω(N\log N)T2S=Ω(NlogN) quantum time-space tradeoff for label-symmetric algorithms due to Magniez-Zur (arXiv:2609.10808); we also prove a stronger classical tradeoff of TS=Ω(Nlog⁡N)TS=Ω(N\log N)TS=Ω(NlogN) assuming label symmetry. The proofs under our framework do not require representation theory and instead bound the mutual information between the compressed oracle pairs. This highlights both how the label symmetry assumption bypasses known proof barriers as well as the challenges that remain in achieving unconditional quantum time-space tradeoffs.
The paper asks how to characterize information a space-bounded quantum algorithm retains about a random oracle, rather than information recorded in its query history. A compressed-oracle database can remain large even after the algorithm has forgotten individual outputs, obstructing direct space bounds.
“Compressed Oracle Duality” canonically re-encodes the algorithm’s memory as a second database: if AAA is the joint state’s coefficient matrix and G=A†AG=A^\dagger AG=A†A, the new joint state has coefficient matrix G\sqrt GG​. The two measured databases have identical marginals; measuring the dual database implements the pretty-good measurement on the memory. Their classical mutual information is at most SSS for SSS qubits. Potentials counting certificates shared by both databases bound query-free extraction success, with quantitative slack. An unconditional shared-point bound gives O(S/log⁡N)O(S/\log N)O(S/logN) expected shared entries after at most N\sqrt NN​ queries.
For collision search in a random function with range size NNN, the framework reproves the existing label-symmetric quantum tradeoff T2S=Ω(Nlog⁡N)T^2S=\Omega(N\log N)T2S=Ω(NlogN) without representation theory. The proof bounds matched labels through mutual information and unmatched labels through symmetry and compressed-oracle validity. A separate branching-program comparison with an injective oracle establishes the classical label-symmetric bound TS=Ω(Nlog⁡N)TS=\Omega(N\log N)TS=Ω(NlogN).
No unrestricted collision tradeoff follows: the proposed per-query joint-potential bound has counterexamples, and label symmetry excludes Pollard’s rho. The general memory characterization assumes no intermediate measurements; only the label-symmetric application is extended to measurements under a conditional symmetry assumption.
A central challenge in quantum algorithms and cryptography is reasoning about algorithms with oracle access to a random group element (e.g. a random function, permutation, or unitary). Can we efficiently simulate such algorithms? Can we determine what they know after t queries? A classical tool for this is lazy sampling: the oracle does not commit to the full group element upfront, but rather samples partial information about it on the fly. We study a quantum analog of lazy sampling: compressed oracles (or recording oracles). These are quantum data structures that allow on-the-fly simulation for quantum queries, originally introduced by Zhandry (CRYPTO '19) for random functions, and generalized to unitaries by Ma-Huang (STOC '25) and permutations by Carolan (STOC '26), and used to great effect in security proofs and lower bounds due to their interpretability. We define and analyze a general-purpose and interpretable path-recording oracle, derived from first principles, that perfectly simulates random elements of any closed subgroup of U(N)U(N)U(N). Our oracle stores, in superposition, t input-output pairs, with updates described in terms of the commutant of the group's tensor power representation. This transparently records the information the algorithm has learned. Our oracle builds on recent work of Grinko-Yoshida (QIP '26), who gave a different general-purpose compressed oracle without clear interpretability. One interesting application of our path-recording is allowing direct comparisons between compressed oracles of different groups, giving a new technique for proving pseudorandomness results. For example, comparing SNS_NSN​ and U(N)U(N)U(N) yields what is arguably the simplest construction to date of pseudorandom unitaries: the product PC of a pseudorandom permutation and a random Clifford, improving on the prior PFC construction (Metger-Poremba-Sinha-Yuen, FOCS '24; Ma-Huang, STOC '25).
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 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.
How much memory is needed to retain the quantum speedup for collision finding? For a uniformly random function f:[N]→[N]f:[N]\to [N]f:[N]→[N], the BHT algorithm finds a collision using O(N1/3)O(N^{1/3})O(N1/3) queries and a quantumly accessible classical table containing O(N1/3)O(N^{1/3})O(N1/3) input-output pairs, whereas a logarithmic-space Grover search uses O(N)O(\sqrt N)O(N​) queries. Determining the optimal query-space tradeoff between these extremes remains a major open problem. We resolve this equation within the class of label-symmetric algorithms, which treat the function fff's output labels as interchangeable. We prove that such algorithm that makes TTT queries, uses SSS qubits, and finds a collision in a uniformly random function f:[M]→[N]f:[M]\to [N]f:[M]→[N] with constant probability satisfies T=Ω(N1/3)andT2S=Ω(Nlog⁡N).T=Ω(N^{1/3}) \qquad\text{and}\qquad T^2S=Ω(N\log N).T=Ω(N1/3)andT2S=Ω(NlogN). For the setting where M=NM=NM=N, these bounds are matched by a space-efficient implementation of the BHT algorithm. As a consequence of our tradeoff, any label-symmetric algorithm for the search version of Element Distinctness on f:[n]→[n2]f: [n] \to [n^2]f:[n]→[n2] must satisfy T=Ω(n2/3)andT2S=Ω(n2log⁡n),T=Ω(n^{2/3}) \qquad\text{and}\qquad T^2S=Ω(n^2\log n),T=Ω(n2/3)andT2S=Ω(n2logn), matching Ambainis's quantum walk. Thus, both tradeoffs are optimal within the class of label-symmetric algorithms. To prove these results, we develop a space-sensitive version of the compressed oracle technique. The compressed oracle records the information learned by the algorithm in an evolving superposition of databases. Using label symmetry and representation theory, we show that an algorithm using SSS qubits can effectively retain information about only O(S/log⁡N)O(S/\log N)O(S/logN) collision-free database entries. Substituting this estimate into the compressed oracle technique yields the stated tradeoffs.
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.
The analysis of quantum algorithms which query random, invertible permutations has been a long-standing challenge in cryptography. Many techniques which apply to random oracles fail, or are not known to generalize to this setting. As a result, foundational cryptographic constructions involving permutations often lack quantum security proofs. With the aim of closing this gap, we develop and prove soundness of a compressed permutation oracle. Our construction shares many of the attractive features of Zhandry's original compressed function oracle: the purification is a small list of input-output pairs which meaningfully reflect an algorithm's knowledge of the oracle.