Classical vs Quantum Random Oracles
Classical vs Quantum Random Oracles
复制标题
DOI：
10.1007/978-3-030-77886-6_20
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Takashi Yamakawa;Mark Zhandry
中科院分区：
文献类型：
--
作者：
Takashi Yamakawa;Mark Zhandry
在本文中，我们研究了随机预言模型（ROM）和量子随机预言模型（QROM）中密码方案的安全性之间的关系。首先，我们引入随机预言机量子访问证明（PoQRO）的概念，这是一种向经典验证者证明量子访问随机预言机能力的协议。我们观察到 Brakerski 等人最近提出的量子性证明。 (TQC ’20) 可以被视为 PoQRO。我们还给出了相对于经典预言机的可公开验证的 PoQRO 的构造。在此基础上，我们构建了在ROM中安全但在QROM中不安全的数字签名和公钥加密方案。特别是，我们获得了在标准密码假设下将 ROM 和 QROM 分开的自然密码方案的第一个例子。另一方面，对于某些类型的密码方案和安全概念，我们给出了从 ROM 中的安全性到 QROM 中的安全性的提升定理。例如，我们的提升定理适用于 Fiat-Shamir 非交互式参数、Fiat-Shamir 签名和全域哈希签名等。我们还讨论了我们的提升定理在量子查询复杂性中的应用。
In this paper, we study relationship between security of cryptographic schemes in the random oracle model (ROM) and quantum random oracle model (QROM). First, we introduce a notion of aproof of quantum access to a random oracle(PoQRO), which is a protocol to prove the capability to quantumly access a random oracle to a classical verifier. We observe that a proof of quantumness recently proposed by Brakerski et al. (TQC ’20) can be seen as a PoQRO. We also give a construction of a publicly verifiable PoQRO relative to a classical oracle. Based on them, we construct digital signature and public key encryption schemes that are secure in the ROM but insecure in the QROM. In particular, we obtain the first examples of natural cryptographic schemes that separate the ROM and QROM under a standard cryptographic assumption.On the other hand, we give lifting theorems from security in the ROM to that in the QROM for certain types of cryptographic schemes and security notions. For example, our lifting theorems are applicable to Fiat-Shamir non-interactive arguments, Fiat-Shamir signatures, and Full-Domain-Hash signatures etc. We also discuss applications of our lifting theorems to quantum query complexity.