机构名称：
¥ 1.0
摘要。我们为量子计算 (BQP) 构建了一个经典可验证的简洁交互式论证，其通信复杂性和验证器运行时间在 BQP 计算的运行时间内是多对数的（在安全参数中是多项式的）。我们的协议是安全的，假设不可区分混淆 (iO) 和错误学习 (LWE) 的后量子安全性。这是第一个简洁的论证，适用于普通模型中的量子计算；先前的工作（Chia-Chung-Yamakawa，TCC '20）既需要较长的公共参考字符串，又需要非黑盒使用以随机预言机建模的哈希函数。在技术层面，我们重新审视了构建经典可验证量子计算的框架（Mahadev，FOCS '18）。我们为 Mahadev 的协议提供了一个独立的模块化安全性证明，我们认为这是有独立意义的。我们的证明很容易推广到验证者的第一条消息（包含许多公钥）被压缩的场景。接下来，我们将压缩公钥的概念形式化；我们将该对象视为受限/可编程 PRF 的泛化，并基于不可区分混淆对其进行实例化。最后，我们使用（足够可组合的）NP 简洁知识论证将上述协议编译成完全简洁的论证。使用我们的框架，我们获得了几个额外的结果，包括 - QMA 的简洁论证（给定见证的多个副本）， - 量子随机预言模型中 BQP（或 QMA）的简洁非交互式论证，以及 - 假设后量子 LWE（无 iO）的 BQP（或 QMA）的简洁批处理论证。
量子计算的简洁经典验证
主要关键词
相关文件推荐
