arXiv:2609.28469
Compressed Permutation Oracles Revisited
Joseph Carolan, Christian Majenz
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.
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.