XiaoMi-AI文件搜索系统
World File Search SystemMahadev
具有可公开验证和可识别中止功能的两全其美的多方量子计算
Alon 等人 (CRYPTO 2021) 引入了一种具有可识别中止 (MPQC-SWIA) 安全性的多方量子计算协议。但是，他们的协议只允许 MPQC 内部各方知道恶意参与者的身份。当两组人意见不一致并需要第三方（如陪审团）来验证谁是恶意方时，这就会变得有问题。鉴于量子态可能只存在于一份副本中，这个问题在量子环境中具有更重要的意义。因此，我们强调具有可公开验证的可识别中止 (PVIA) 协议的必要性，使只有经典计算能力的外部观察者能够在发生中止的情况下就恶意方的身份达成一致。然而，由于不可克隆定理以及 Mahadev (STOC 2018) 和 Chung 等人提出的先前工作，实现具有 PVIA 的 MPQC 带来了重大挑战。 （Eurocrypt 2022）用于量子计算的经典验证的协议存在缺陷。在本文中，我们获得了第一个 MPQC-PVIA 协议，该协议假设后量子无意识传输和经典广播信道。我们构建的核心组件是一种称为可审计量子认证（AQA）的新认证原语，它以压倒性的概率识别恶意发送者。此外，我们提供了第一个具有两全其美（BoBW）安全性的 MPQC 协议，该协议保证在诚实多数的情况下输出交付，并且即使多数不诚实也能在中止时保持安全。我们的两全其美 MPQC 协议在中止时也满足 PVIA。
线性时间内量子计算的经典验证
在量子计算验证问题中，量子服务器想要让客户端相信，对量子电路 C 进行评估的输出就是它所声称的某个结果。这个问题在量子计算的理论和实践中都非常重要 [32, 1, 47]。客户端的计算能力有限，而其理想特性之一是客户端可以完全是经典的，这就引出了量子计算的经典验证 (CVQC) 问题。就服务器端量子计算的时间复杂度而言（通常决定客户端和服务器的总时间复杂度），迄今为止最快的单服务器 CVQC 协议的复杂度为 O(poly(κ)|C|3)，其中|C|是待验证电路的大小，κ是安全参数，由 Mahadev [41] 给出。这导致许多现有协议（包括多方量子计算、零知识和混淆）也出现类似的立方时间爆炸 [8, 50, 9, 16, 18, 2]。考虑到量子计算资源的珍贵性，这种立方复杂度障碍可能会成为将这些问题的协议付诸实践的一大障碍。在本文中，通过开发新技术，我们给出了一种新的 CVQC 协议，其复杂度为 O ( poly ( κ ) | C | )（就客户端和服务器的总时间复杂度而言），比现有协议快得多。我们的协议在量子随机预言模型 [11] 中是安全的，假设存在有噪声陷门无爪函数 [12]，这两个都是量子密码学中广泛使用的假设。在此过程中，我们还为 {| + θ ⟩ = 1 √
通过经典信道进行安全的双方量子计算
摘要。安全的双方计算考虑双方计算其私有输入的联合函数而不透露计算输出以外的任何内容的问题。在这项工作中，我们迈出了理解以下情况的第一步：1）双方（Alice 和 Bob）只能通过经典信道进行通信，2）Bob 的输入是量子的，3）Alice 的输入是经典的。我们的第一个结果表明，在这种情况下，在恶意量子对手的情况下，通常不可能通过黑盒模拟实现双方量子功能。特别是，我们表明，仅依赖经典信道的安全量子计算协议的存在将与量子不可克隆论证相矛盾。我们通过三种不同的方法规避了这种不可能性。第一种方法是考虑一种较弱的安全概念，称为单边模拟安全。这个概念以标准的基于模拟的意义保护一方（量子 Bob）的输入，并保护另一方输入（经典 Alice）的隐私。我们展示了如何实现一个依赖于有错学习假设的满足这一概念的协议。第二种规避不可能结果的方法是假设量子输入具有有效的经典表示，同时提供基于标准模拟的安全性以抵御恶意 Bob。最后，我们将注意力集中在零知识函数类上，并提供一个编译器，该编译器以 QMA 关系 R 的经典量子知识证明 (PoQK) 协议作为输入（经典 PoQK 是可以由经典验证者验证的 PoQK），并输出可以由经典方验证的 R 的零知识 PoQK。我们的结果直接意味着 Mahadev 的量子计算经典验证协议 (FOCS'18) 可以转变为具有经典验证者的量子知识零知识证明。据我们所知，我们是第一个实例化这种原语的人。
