使用亚线性预处理的安全多方计算
Published:
详细计算能否使用到多用户的PPML中
背景 安全多方计算 (MPC) 协议使一组具有私有输入的各方能够计算其输入的联合函数，同时仅显示输出。 优化 MPC 协议的渐近和具体效率一直是大量工作的主题。 在考虑针对恶意对手的安全性时，这个问题尤其具有挑战性，他们可以积极地腐蚀各方。 设计此类协议的一个成功方法是采用预处理。 在输入已知之前，各方运行离线协议以生成相关的秘密随机性，该随机性由轻量级且通常为“非加密”（或“信息论”）在线协议使用。 1该模型也称为 离线/在线模型，在不能保证诚实的多数时特别有吸引力，因为它允许将协议的繁重的“加密”部分推到离线阶段，从而最大限度地降低在线协议的成本。 源自 Beaver 的工作，他展示了如何使用“乘法三元组”进行不诚实多数的安全算术计算，许多安全计算协议广泛使用相关随机性。
大部分工作都在预处理模型中设计了协议，具有针对恶意对手的安全性。 一种强大的循环技术使用同态 MAC 来验证在线协议产生的值； 由此产生的相关性是“经过验证的”乘法三元组的一种形式。 事实上，所谓的“SPDZ”工作线是该领域的领先方法，催生了一系列优化、实施和改进。 另一种最近的方法包括基于次线性分布式零知识的编译器 。 根据设计，在所有这些协议中，大部分工作都在预处理阶段。 特别是，现有协议中此阶段的典型通信复杂性比被评估电路的规模高出几个数量级。
最近构建的伪随机相关发生器 (PCG) 展示了改善某些预处理程序的通信需求的巨大潜力。 PCG 为各方提供了一种方法，可以在不进行通信的情况下，将短的相关种子局部扩展为某些相关性的长伪随机实例。 事实上，最近基于噪声学习奇偶性（LPN）或其 Ring-LPN 变体的 PCG 结构能够具体有效地安全生成许多乘法三元组，具有次线性通信和良好的具体效率，包括种子的安全生成]。 这直接为具有半诚实安全性的 MPC 提供了实用的次线性通信预处理。
然而，这些技术通常不适用于经过身份验证的乘法三元组的更复杂的相关性，这是将这种方法扩展到具有恶意安全性的协议所必需的。 用于经过验证的三元组的具体有效 PCG 仅存在于大字段上的 2 方相关的有限设置中。2 使用 PCG 生成的“BDOZ” 风格的成对经过验证的三元组对于算术电路可能是可行的 和少量的聚会，但会导致在线交流的聚会人数呈二次方增长。 在布尔电路的 2 方评估的情况下，用于 OT 的 PCG 可用于生成 F2 上的乘法三元组，从而实现半诚实的在线协议，每门 2 位，而对于恶意安全，需要传达 2 个元素 每个门一个大的有限域。 总而言之，目前的 PCG 机器不能有效地用于生成支持在线协议的经过验证的三元组，该在线协议与参与方的数量成线性比例，或者甚至是布尔电路的 2 方协议。 因此，在这些设置中具有预处理的 MPC 的所有实用协议都要求预处理的通信复杂性远大于电路尺寸。
本文为不诚实多数设置中的安全多方计算 (MPC) 提供了新的可行性和具体的效率结果。 我们的一般方法可以实例化，以提供第一个实用的次线性通信方法来生成“SPDZ 式”相关性，在实现恶意安全的意义上，在线阶段既非加密又在电路尺寸上具有线性通信 和派对的数量。 我们的方法不需要像 SPDZ 中那样经过身份验证的乘法三元组，而是仅使用半诚实（未经身份验证的）三元组以及基于 Boyle 等人最近协议变体的额外预处理材料。因此，我们的协议继承了后一种协议简洁的相关随机性特征——也就是说，额外的预处理材料（除了乘法三元组之外）在电路尺寸上只是次线性的。 从具体效率的角度来看，我们的方法对于 2 方情况下的布尔电路也很有吸引力，因为没有具体有效的 PCG 来生成二进制认证三元组，而用于 OT 的 PCG 可以生成二进制非认证三元组。 更具体地说，我们的协议支持在任何有限域或环 Z2k 上的算术电路预处理模型中的安全计算。 我们说在线阶段是“信息论的”（或“非密码学的”），因为相关的随机分布 D 在计算上与某些分布 D’ 无法区分，对于后者，使用 D’ 执行在线阶段会得出真实信息 理论上的安全。 离线预处理阶段具有与电路大小的平方根成比例的通信。
请注意，在线阶段的信息论性质使得实现亚线性离线通信的任务非常重要，而不是简单地忽略离线阶段（零离线通信）并在在线阶段执行完整安全计算的简单解决方案方法。 我们还从现有的同态加密方案和现有的伪随机相关生成器中提出了主要定理的具体有效实例（基于强大但合理的“仅线性”假设）。
技术 技术利用了分布式零知识和 BGIN’21。根据最近的一系列工作，使用次线性分布式零知识机器来实现低通信解决方案，以将半诚实编译为恶意安全。 这些协议的高层结构如下。 在协议中，除最后一步外，各方首先运行底层的半诚实安全协议。 然后，在交换最终消息和揭示输出之前，各方首先共同执行验证阶段，其中断言第一阶段的正确性。 这是通过在分布式数据上生成和验证零知识证明（以下简称“分布式零知识”）来完成的，这可以通过简单语言的次线性证明大小来完成。分布式零知识 (DZK) 证明考虑了具有单个证明者和多个验证者的设置，每个验证者都持有声明的各个部分； 证明者将证明的一部分发送给每个验证者，验证者之间进行交互以验证证明。 MPC 协议应用程序中 DZK 证明系统的具体结构和使用因作品而异：每一方单独作为证明者来断言自己的适当行为，或者各方共同模仿集体上的证明者一组生成的值，没有任何一方完全知道。
在任何多方设置中都会出现复杂情况，其中不止一个腐败方，因为在证明实体和验证实体之间可能会发生勾结。 为了提供可靠性，被证明的陈述必须以某种方式在各方之间稳健地持有，这样腐败的验证者就不能修改他的陈述部分以使证明不正确地被接受。 对于诚实多数的 MPC，这种稳健性是自然的，诚实的各方本身拥有足够的信息来确定（秘密）声明。 对于不诚实的大多数情况，确保鲁棒性不太清楚。BGIN的主要思想是，可以设计在预处理过程中产生的相关随机性，以便充当额外的“经销商”方，其行为必须独立于输入来确定 ，但保证其行为是诚实的。
当然，要使这种方法起作用，相关随机性的真实生成至关重要。 在理想化的预处理模型中，如 BGIN 中所考虑的那样，这是免费的：假设各方从理想的诚实经销商那里获得了从相关随机性中诚实生成的样本。 我们的挑战是消除这种假设，并在亚线性通信中以仍然满足整体安全性的方式生成这些值作为协议的一部分。 此外，我们希望在不求助于昂贵的通用工具（例如完全同态加密）的情况下这样做。 相反，我们将依赖任何加法同态加密。 这样做将需要我们在此过程中修改 BGIN’21 相关性和协议。 BGIN’21 经销商（略有修改）。 考虑 DZK 联合证明者仿真方法。 在半诚实执行之后，双方希望共同证明，对于每个乘法门，他们持有的输出线份额与他们持有的两条输入线份额正确对应。 为了将其压缩为单个验证而不是 |C|，各方对每个乘法门 g 采样随机系数 αg，并验证所有门检查的随机线性组合确实验证了。 这减少了证明单个 2 次多元多项式在 O(|C|) 秘密共享输入上评估为 0 的挑战。