Paper 2025/1734
Compressed Permutation Oracles
, University of Maryland, College ParkAbstract
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. We then apply this framework to show that the Feistel construction with seven rounds is a strong quantum PRP, resolving an open question of (Zhandry, 2012). We further re-prove essentially all known quantum query lower bounds in the random permutation model, notably the collision and preimage resistance of both Sponge and Davies-Meyer, hardness of double-sided zero search and sparse predicate search, and give new lower bounds for cycle finding and the one-more problem.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint.
- Keywords
- QuantumPermutationsFeistel
- Contact author(s)
- jcarolan @ umd edu
- History
- 2025-09-24: approved
- 2025-09-23: received
- See all versions
- Short URL
- https://ia.cr/2025/1734
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2025/1734,
author = {Joseph Carolan},
title = {Compressed Permutation Oracles},
howpublished = {Cryptology {ePrint} Archive, Paper 2025/1734},
year = {2025},
url = {https://eprint.iacr.org/2025/1734}
}
