Paper 2026/2135
Improved Soundness for Compressed Permutation Oracles and Tight Quantum Preimage and Collision Bounds for the Sponge
Abstract
We give a sharper bound on the error introduced by replacing a random permutation oracle with Carolan’s compressed permutation oracle. Building on Rosmanis’s representation-theoretic approach, we represent exact permutation states in the compressed oracle’s database space, allowing a direct comparison of the two query operations. For a uniform permutation on N points, this comparison bounds the soundness error by 4q/√N after q ≤ N/4 queries. As the main application, we obtain tight query complexity for constant success probability in sponge preimage and collision search by substituting this bound into Carolan’s search reductions. The same analysis improves bounds for the one-more problem and cycle finding, and gives tight query complexity for constant success probability in keyless Davies–Meyer collision search
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint.
- Keywords
- Post-quantum cryptographyQuantum random permutation modelCompressed oracleQuantum query complexity
- Contact author(s)
- sunyeopkim @ korea ac kr
- History
- 2026-09-22: revised
- 2026-09-21: received
- See all versions
- Short URL
- https://ia.cr/2026/2135
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2026/2135,
author = {Sunyeop Kim},
title = {Improved Soundness for Compressed Permutation Oracles and Tight Quantum Preimage and Collision Bounds for the Sponge},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/2135},
year = {2026},
url = {https://eprint.iacr.org/2026/2135}
}
