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).

翻译：Zhandry在记录量子查询[Crypto 2019]的开创性工作中,研究了量子查询算法和与随机功能相对应的量子孔器之间的相互作用。Zhandry提出了一个框架,用于将甲骨文量子空间中的不同国家解释为算法所获取知识的数据库,并使用这种解释来提供等离子加密后的安全证据。在本文中,我们对“天线”与随机变换相对应而不是随机函数的情况作了类似的解释。由于随机功能和随机变换在安全证据中都非常重要,我们希望目前的框架能够在量子加密法中找到应用。此外,我们展示了如何利用这一框架来证明试图推翻随机N元素变换的 kquery量算的成功概率多为O(k ⁇ 2/N) 。