Verifiable Quantum Advantage without Structure
Verifiable Quantum Advantage without Structure
复制标题
无需结构即可验证的量子优势
DOI：
--
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Mark Zhandry
中科院分区：
文献类型：
--
作者：
Takashi Yamakawa;Mark Zhandry
除非另有说明，我们证明了以下无条件地保持，相对于概率为1的随机预言：·存在BQP机器可解的NP搜索问题，但BPP机器不可解。存在单向的，甚至是抗碰撞的函数，可以对抗经典的对手，但很容易在量子上被反转。类似的分离适用于数字签名和CPA安全公钥加密（后者需要假设经典的CPA安全加密方案）。有趣的是，这种分离并不一定适用于其他加密对象（如PRG）。·有无条件的公开可验证的量子性证明，交互次数最少：对于统一的对手，证明是非交互的，而对于非统一的对手，证明是两个消息公共硬币。我们的结果似乎并不与Aaronson-Ambanis猜想相矛盾。假设这个猜想，存在公开可验证的可证明的随机性，再次与最小的交互轮次。通过用具体的加密哈希函数（如SHA 2）替换随机预言，我们获得了上述结果的合理Minicrypt实例。以前的类似结果都需要实质性的结构，无论是高度结构化的神谕和/或代数假设在密码狂热和超越。
We show the following hold, unconditionally unless otherwise stated, relative to a random oracle with probability 1: •There are NP search problems solvable by BQP machines but not BPP machines.•There exist functions that are one-way, and even collision resistant, against classical adversaries but are easily inverted quantumly. Similar separations hold for digital signatures and CPA-secure public key encryption (the latter requiring the assumption of a classically CPA-secure encryption scheme). Interestingly, the separation does not necessarily extend to the case of other cryptographic objects such as PRGs.•There are unconditional publicly verifiable proofs of quantumness with the minimal rounds of interaction: for uniform adversaries, the proofs are non-interactive, whereas for non-uniform adversaries the proofs are two message public coin.•Our results do not appear to contradict the Aaronson-Ambanis conjecture. Assuming this conjecture, there exist publicly verifiable certifiable randomness, again with the minimal rounds of interaction.By replacing the random oracle with a concrete cryptographic hash function such as SHA2, we obtain plausible Minicrypt instantiations of the above results. Previous analogous results all required substantial structure, either in terms of highly structured oracles and/or algebraic assumptions in Cryptomania and beyond.
登录
查看更多内容
随机预言模型中的量子深度
DOI：
10.1145/3564246.3585153
发表时间：
2023
期刊：
ACM Symposium on Theory of Computing
影响因子：
--
作者：
Arora, Atul Singh;Coladangelo, Andrea;Coudron, Matthew;Gheorghiu, Alexandru;Singh, Uttam;Waldner, Hendrik
通讯作者：
Waldner, Hendrik
DOI：
10.1007/978-3-030-77886-6_20
发表时间：
2020
期刊：
--
影响因子：
--
作者：
Takashi Yamakawa;Mark Zhandry
通讯作者：
Takashi Yamakawa;Mark Zhandry
DOI：
10.1145/3357713.3384304
发表时间：
2020-06
期刊：
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
Ryan B. Amos;M. Georgiou;A. Kiayias;Mark Zhandry
通讯作者：
Ryan B. Amos;M. Georgiou;A. Kiayias;Mark Zhandry
论量子随机预言密钥协议的不可能性
DOI：
--
发表时间：
2022
期刊：
Springer
影响因子：
--
作者：
Austrin, Per;Chung, Hao;Chung, Kai-Min;Fu, Shiuan;Lin, Yao-Ting;Mahmoody, Mohammad
通讯作者：
Mahmoody, Mohammad