Tight Bounds for Inverting Permutations via Compressed Oracle Arguments
This work provides a tool for security proofs in quantum cryptography, specifically for applications involving random permutations, but it is incremental as it extends an existing framework to a new context.
The paper tackles the problem of analyzing quantum query algorithms interacting with random permutations, introducing a framework similar to Zhandry's for random functions, and proves that the success probability for inverting a random permutation with k queries is at most O(k^2/N).
In his seminal work on recording quantum queries [Crypto 2019], Zhandry studied interactions between quantum query algorithms and the quantum oracle corresponding to random functions. Zhandry presented a framework for interpreting various states in the quantum space of the oracle as databases of the knowledge acquired by the algorithm and used that interpretation to provide security proofs in post-quantum cryptography. In this paper, we introduce a similar interpretation for the case when the oracle corresponds to random permutations instead of random functions. Because both random functions and random permutations are highly significant in security proofs, we hope that the present framework will find applications in quantum cryptography. Additionally, we show how this framework can be used to prove that the success probability for a k-query quantum algorithm that attempts to invert a random N-element permutation is at most O(k^2/N).