Paper 2023/770 Original: eprint.iacr.org/2023/770 ↗
Towards compressed permutation oracles
Abstract
Compressed oracles (Zhandry, Crypto 2019) are a powerful technique to reason about quantum random oracles, enabling a sort of lazy sampling in the presence of superposition queries. A long-standing open question is whether a similar technique can also be used to reason about random (efficiently invertible) permutations. In this work, we make a step towards answering this question. We first define the compressed permutation oracle and illustrate its use. While the soundness of this technique (i.e., the indistinguishability from a random permutation) remains a conjecture, we show a curious 2-for-1 theorem: If we use the compressed permutation oracle methodology to show that some construction (e.g., Luby-Rackoff) implements a random permutation (or strong qPRP), then we get the fact that this methodology is actually sound for free.
Metadata
- Available format(s)
PDF- Category
- Foundations
- Publication info
- Preprint.
- History
- 2023-05-26: last updated
- 2023-05-26: published
- Short URL
- https://ia.cr/2023/770
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2023/770,
author = {Dominique Unruh},
title = {Towards compressed permutation oracles},
howpublished = {Cryptology {ePrint} Archive, Paper 2023/770},
year = {2023},
url = {https://eprint.iacr.org/2023/770}
}