A Note on the Instantiability of the Quantum Random Oracle
A Note on the Instantiability of the Quantum Random Oracle
复制标题
DOI：
10.1007/978-3-030-44223-1_27
复制
发表时间：
2020-04
期刊：
影响因子：
--
通讯作者：
Edward Eaton;F. Song
中科院分区：
文献类型：
--
作者：
Edward Eaton;F. Song
在十五年前一篇极具影响力的论文中 [10]，Canetti、Goldreich 和 Halevi 展示了随机预言模型 (ROM) 和标准模型之间的根本区别。他们构建了一个签名方案，该方案可以在 ROM 中被证明是安全的，但在使用任何哈希函数实例化时是不安全的（因此在标准模型中是不安全的）。 2011 年，Boneh 等人。定义了量子随机预言模型（QROM）的概念，其中可以在量子叠加中对随机预言进行查询。由于 QROM 概括了 ROM，因此 QROM 中的安全性证明比 ROM 中的安全性证明更强。这使得 QROM 中的安全性可能意味着标准模型中的安全性存在可能性。在这项工作中，我们证明事实并非如此，并且 QROM 中的安全性并不意味着标准模型的安全性。我们通过证明显示标准模型和 ROM 之间分离的原始方案在 QROM 中也是安全的来做到这一点。我们考虑了两种建立这种分离的方案，一种具有长度限制的消息，一种没有，并且表明这两种方案在 QROM 中都是安全的。我们的结果进一步了解了 ROM 与 QROM 或标准模型中的证明情况，并指出 QROM 和 ROM 比标准模型安全性更接近彼此。
In a highly influential paper from fifteen years ago [10], Canetti, Goldreich, and Halevi showed a fundamental separation between the Random Oracle Model (ROM) and the standard model. They constructed a signature scheme which can be proven secure in the ROM, but is insecure when instantiated with any hash function (and thus insecure in the standard model). In 2011, Boneh et al. defined the notion of theQuantumRandom Oracle Model (QROM), where queries to the random oracle may be made in quantum superposition. Because the QROM generalizes the ROM, a proof of security in the QROM is stronger than one in the ROM. This leaves open the possibility that security in the QROM could imply security in the standard model. In this work, we show that this is not the case, and that security in the QROM cannot imply standard-model security. We do this by showing that the original schemes that show a separation between the standard model and the ROM are also secure in the QROM. We consider two schemes that establish such a separation, one with length-restricted messages, and one without, and show both to be secure in the QROM. Our results give further understanding to the landscape of proofs in the ROM versus the QROM or standard model, and point towards the QROM and ROM being much closer to each other than either is to standard model security.