Paper 2023/770
Towards compressed permutation oracles
, University of TartuAbstract
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.
- Keywords
- quantum cryptographyrandom oracles
- Contact author(s)
- unruh @ ut ee
- History
- 2023-05-30: approved
- 2023-05-26: received
- See all versions
- Short URL
- https://ia.cr/2023/770
- License
-
CC BY
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}
}
