International Association for Cryptologic Research

International Association
for Cryptologic Research


Towards compressed permutation oracles

Dominique Unruh , RWTH Aachen, Germany; University of Tartu, Estonia
Search ePrint
Search Google
Presentation: Slides
Conference: ASIACRYPT 2023
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.
  title={Towards compressed permutation oracles},
  author={Dominique Unruh},