论文标题
量子随机甲骨文模型中的不均匀性和量子建议
Non-uniformity and Quantum Advice in the Quantum Random Oracle Model
论文作者
论文摘要
QROM（量子随机甲骨文模型），由Boneh等人引入。 （Asiacrypt 2011），捕获了所有通用算法。但是，它无法用预处理能力来描述非均匀的量子算法，该算法获得了有限的经典或量子建议。由于非均匀算法在很大程度上被认为是攻击者的正确模型，从Nayebi，Aaronson，Belovs和Trevisan的作品开始（QIC 2015），一系列的作品研究了随机Oracle模型中的非均匀安全性。 Chung，Guo，Liu和Qian（焦点2020）为许多加密应用提供了一个框架，并为许多加密应用建立了不均匀的安全性。 在这项工作中，我们继续对QROM中的量子建议进行研究。我们提供了一个新的想法，该想法将概括为以前的多实体框架，我们认为这更符合量子友好，应该是多实体游戏的量子类似物。为此，我们将界限与量子建议与Chung等人的经典建议的人相匹配，显示量子建议几乎与QROM中许多自然安全游戏的经典建议一样好/坏。 最后，我们表明，对于QROM中一些人为的游戏，量子建议可以比某些参数制度的经典建议呈指数级。据我们所知，它提供了一些证据，证明量子和经典建议相对于非结构化的甲骨文有一般性分离。
QROM (quantum random oracle model), introduced by Boneh et al. (Asiacrypt 2011), captures all generic algorithms. However, it fails to describe non-uniform quantum algorithms with preprocessing power, which receives a piece of bounded classical or quantum advice. As non-uniform algorithms are largely believed to be the right model for attackers, starting from the work by Nayebi, Aaronson, Belovs, and Trevisan (QIC 2015), a line of works investigates non-uniform security in the random oracle model. Chung, Guo, Liu, and Qian (FOCS 2020) provide a framework and establish non-uniform security for many cryptographic applications. In this work, we continue the study on quantum advice in the QROM. We provide a new idea that generalizes the previous multi-instance framework, which we believe is more quantum-friendly and should be the quantum analogue of multi-instance games. To this end, we match the bounds with quantum advice to those with classical advice by Chung et al., showing quantum advice is almost as good/bad as classical advice for many natural security games in the QROM. Finally, we show that for some contrived games in the QROM, quantum advice can be exponentially better than classical advice for some parameter regimes. To our best knowledge, it provides some evidence of a general separation between quantum and classical advice relative to an unstructured oracle.
