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.28469

Compressed Permutation Oracles Revisited

Joseph Carolan, Christian Majenz

quant-phSubmitted Sep 23, 2026• Announced Sep 24, 2026• 6 citations
arXivHTMLPDF

Abstract

The compressed permutation oracle has been used to analyze the quantum security of a number of cryptographic constructions which resisted prior techniques. However, these analyses were fundamentally limited by the poor soundness of the method: the technique was proven sound only up to $O(N^{1/12})$ queries to permutations on $N$ elements. We revisit this analysis, improving the soundness bound to a tight $Ω(N^{1/2})$. In addition to being tighter, our proof is conceptually simpler and more direct, and gives the same bound in the ideal cipher model. The main technical idea is to construct the compression isometry from a simple POVM on the naive purification, a technique which may find wider applications. As immediate applications, our results yield tight, concrete collision and pre-image lower bounds for the sponge hash construction underlying SHA3 and the Davies--Meyer compression function used in SHA1 and SHA2. More broadly, the improved soundness theorem provides a general-purpose tool for analyzing quantum security in settings where random permutations or ideal ciphers serve as the underlying primitive.

AI Summary

The paper addresses the soundness of compressed permutation oracles for quantum algorithms with forward and inverse access to random permutations. Previous guarantees applied only up to the $N^{1/12}$ query scale for permutations on $N$ elements, limiting security bounds obtained from compressed-database arguments. It analyzes the existing oracle and proves distinguishing advantage $O(q/\sqrt N)$, giving soundness for $q=o(\sqrt N)$. The explicit bound is $120q/\sqrt{N-q+1}+q(q+1)/(N-2q+1)$ when $3q-1\le N$. The same guarantee holds for ideal ciphers with superposition queries over keys, without dependence on the number of keys. The proof constructs a compression isometry from uniform superpositions of permutations completing partial databases. It separates these completion states into orthogonal query-information levels and normalizes their frame operators, equivalently implementing a pretty-good-measurement POVM coherently. Symmetric-group representation theory determines the normalization spectrum; incidence-map estimates and comparisons between adjacent levels bound one-query error, which is accumulated through a hybrid argument. Applications give sponge preimage and collision success bounds $O(T^2/2^d+T^3/2^c)$ and $O(T^3/2^d+T^3/2^c)$, respectively, and Davies–Meyer bounds $O(T^2/2^n)$ and $O(T^3/2^n)$, with explicit constants. Here $T$ includes transcript-generation and verification overhead. The sponge analysis covers a single squeezing block, including all four SHA-3 parameter sets. These are random-permutation and ideal-cipher results, not security proofs for fixed Keccak or actual SHA implementations; Davies–Meyer is analyzed with XOR feed-forward rather than SHA-1/SHA-2’s wordwise addition.

Likely largely AI-generatedAI use disclosedOverclaims
The technical overview and introduction were prepared by an interlaced combination of text from Astra and the authors.

Error found: The paper calls its square-root soundness scale tight but proves only that constant distinguishing advantage requires Ω(√N) queries, without establishing a matching O(√N)-query distinguisher.

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

Related papers

Compressed Permutation Oracles Revisited — E8 Intelligence Research

Andrew Stewart Caldin

The compressed permutation oracle has been used to analyze the quantum security of a number of cryptographic constructions which resisted prior techniques. However, these analyses were fundamentally limited by the poor soundness of the method: the technique was proven sound only up to $O(N^{1/12})$ queries to permutations on $N$ elements. We revisit this analysis, improving the soundness bound to a tight $Ω(N^{1/2})$. In addition to being tighter, our proof is conceptually simpler and more direct, and gives the same bound in the ideal cipher model. The main technical idea is to construct the compression isometry from a simple POVM on the naive purification, a technique which may find wider applications. As immediate applications, our results yield tight, concrete collision and pre-image lower bounds for the sponge hash construction underlying SHA3 and the Davies--Meyer compression function used in SHA1 and SHA2. More broadly, the improved soundness theorem provides a general-purpose Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com

•Nov 11, 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

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

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

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

Permutation Superposition Oracles for Quantum Query Lower Bounds

Christian Majenz, Giulio Malavolta, Michael Walter

We propose a generalization of Zhandry's compressed oracle method to random permutations, where an algorithm can query both the permutation and its inverse. We show how to use the resulting oracle simulation to bound the success probability of an algorithm for any predicate on input-output pairs, a key feature of Zhandry's technique that had hitherto resisted attempts at generalization to random permutations. One key technical ingredient is to use strictly monotone factorizations to represent the permutation in the oracle's database. As an application of our framework, we show that the one-round sponge construction is unconditionally preimage resistant in the random permutation model. This proves a conjecture by Unruh.

arXiv:2407.09655•ACM Symposium on Theory of Computing (STOC)•Jun 15, 2025•16 citations
The compressed permutation oracle has been used to analyze the quantum security of a number of cryptographic constructions which resisted prior techniques. However, these analyses were fundamentally limited by the poor soundness of the method: the technique was proven sound only up to O(N1/12)O(N^{1/12})O(N1/12) queries to permutations on NNN elements. We revisit this analysis, improving the soundness bound to a tight Ω(N1/2)Ω(N^{1/2})Ω(N1/2). In addition to being tighter, our proof is conceptually simpler and more direct, and gives the same bound in the ideal cipher model. The main technical idea is to construct the compression isometry from a simple POVM on the naive purification, a technique which may find wider applications.
As immediate applications, our results yield tight, concrete collision and pre-image lower bounds for the sponge hash construction underlying SHA3 and the Davies--Meyer compression function used in SHA1 and SHA2. More broadly, the improved soundness theorem provides a general-purpose tool for analyzing quantum security in settings where random permutations or ideal ciphers serve as the underlying primitive.
The paper addresses the soundness of compressed permutation oracles for quantum algorithms with forward and inverse access to random permutations. Previous guarantees applied only up to the N1/12N^{1/12}N1/12 query scale for permutations on NNN elements, limiting security bounds obtained from compressed-database arguments.
It analyzes the existing oracle and proves distinguishing advantage O(q/N)O(q/\sqrt N)O(q/N​), giving soundness for q=o(N)q=o(\sqrt N)q=o(N​). The explicit bound is 120q/N−q+1+q(q+1)/(N−2q+1)120q/\sqrt{N-q+1}+q(q+1)/(N-2q+1)120q/N−q+1​+q(q+1)/(N−2q+1) when 3q−1≤N3q-1\le N3q−1≤N. The same guarantee holds for ideal ciphers with superposition queries over keys, without dependence on the number of keys.
The proof constructs a compression isometry from uniform superpositions of permutations completing partial databases. It separates these completion states into orthogonal query-information levels and normalizes their frame operators, equivalently implementing a pretty-good-measurement POVM coherently. Symmetric-group representation theory determines the normalization spectrum; incidence-map estimates and comparisons between adjacent levels bound one-query error, which is accumulated through a hybrid argument.
Applications give sponge preimage and collision success bounds O(T2/2d+T3/2c)O(T^2/2^d+T^3/2^c)O(T2/2d+T3/2c) and O(T3/2d+T3/2c)O(T^3/2^d+T^3/2^c)O(T3/2d+T3/2c), respectively, and Davies–Meyer bounds O(T2/2n)O(T^2/2^n)O(T2/2n) and O(T3/2n)O(T^3/2^n)O(T3/2n), with explicit constants. Here TTT includes transcript-generation and verification overhead. The sponge analysis covers a single squeezing block, including all four SHA-3 parameter sets. These are random-permutation and ideal-cipher results, not security proofs for fixed Keccak or actual SHA implementations; Davies–Meyer is analyzed with XOR feed-forward rather than SHA-1/SHA-2’s wordwise addition.
The compressed permutation oracle has been used to analyze the quantum security of a number of cryptographic constructions which resisted prior techniques. However, these analyses were fundamentally limited by the poor soundness of the method: the technique was proven sound only up to O(N1/12)O(N^{1/12})O(N1/12) queries to permutations on NNN elements. We revisit this analysis, improving the soundness bound to a tight Ω(N1/2)Ω(N^{1/2})Ω(N1/2). In addition to being tighter, our proof is conceptually simpler and more direct, and gives the same bound in the ideal cipher model. The main technical idea is to construct the compression isometry from a simple POVM on the naive purification, a technique which may find wider applications. As immediate applications, our results yield tight, concrete collision and pre-image lower bounds for the sponge hash construction underlying SHA3 and the Davies--Meyer compression function used in SHA1 and SHA2. More broadly, the improved soundness theorem provides a general-purpose Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com
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.
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.
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).
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.
We propose a generalization of Zhandry's compressed oracle method to random permutations, where an algorithm can query both the permutation and its inverse. We show how to use the resulting oracle simulation to bound the success probability of an algorithm for any predicate on input-output pairs, a key feature of Zhandry's technique that had hitherto resisted attempts at generalization to random permutations. One key technical ingredient is to use strictly monotone factorizations to represent the permutation in the oracle's database. As an application of our framework, we show that the one-round sponge construction is unconditionally preimage resistant in the random permutation model. This proves a conjecture by Unruh.