Compressed Permutation Oracles Revisited
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(N1/12) queries to permutations on N elements. We revisit this analysis, improving the soundness bound to a tight Ω(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.
Related
- Indistinguishability Lifting for Keyed Oracles, Compressed Ideal Cipher, and More Applications
- How to make quantum cheese: efficient geometry oracles for exponentially many pseudorandom microstructures
- Spectral theory of energy-selective quantum search with Ising Hamiltonian phase oracles
- Modeling and Resource Optimization for Quantum Oracles
- QEncodeBench: Can Large Language Models Encode Classical Problems into Verified Quantum Oracles?
BibTeX
@misc{carolan2026compressed,
title = {{Compressed Permutation Oracles Revisited}},
author = {Joseph Carolan and Christian Majenz},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.28469},
eprint = {2609.28469},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.28469},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Compressed Permutation Oracles Revisited
AU - Joseph Carolan
AU - Christian Majenz
PY - 2026
DA - 2026/09/23
PB - arXiv
DO - 10.48550/arxiv.2609.28469
UR - https://arxiv.org/abs/2609.28469
AB - 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.
ER -