Online QuSoft seminar with Ansis Rosmanis. Title: Title : Proving the Hardness of Inverting Permutations via Database
Arguments.
Abstract :
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 the quantum space of the oracle as the database of the knowledge acquired by the algorithm, and used that interpretation to provide security proofs in quantum cryptography.
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).
For zoomlink contact Jop Briet or Subhasree Patro
