QHROM

量子默克尔树

提交信息是密码学的核心任务，其中一方（通常称为证明者）存储一段信息（例如，一个比特串）并承诺不更改它。另一方（通常称为验证者）可以访问此信息，后者可以稍后了解该信息并验证它没有被篡改。Merkle 树 [1] 是一种众所周知的简洁构造，其中验证者可以通过从诚实的证明者那里收到一个简短的证明来了解信息的任何部分。尽管 Merkle 树在古典密码学中具有重要意义，但却没有与 Merkle 树相关的量子类似物。直接使用量子随机预言模型（QROM）[2] 进行概括似乎并不安全。在这项工作中，我们提出了量子 Merkle 树。它基于我们所说的量子 Haar 随机预言模型（QHROM）。在 QHROM 中，证明者和验证者都可以访问 Haar 随机量子预言机 G 及其逆。利用量子 Merkle 树，我们为 Gap-k-Local-Hamiltonian 问题提出了一个简洁的量子论证。假设量子 PCP 猜想是正确的，这个简洁的论证可以扩展到所有 QMA 。这项工作提出了许多有趣的开放研究问题。