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 that can be used to provide security proofs in 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)。