Multiparty Computation from Somewhat Homomorphic Encryption

部分同态加密的多方计算

我们提出了一个通用的多方计算协议，以防止主动对手破坏多达 个用户。该协议可用于安全地计算任何有限域 上的算术电路。我们的协议由一个预处理阶段和一个更有效的在线阶段组成，前者与要计算的函数和输入无关，后者是实际计算的地方。在线阶段是无条件安全的，总的计算（和通信）复杂度是 的线性，即用户的数量，而早期的工作是 的平方。此外，每个用户所做的工作只比在明处计算电路所需的工作大一个小常数。我们表明这对大领域的计算来说是最佳的。在实践中，对于 个用户，一个安全的 位乘法可以在 毫秒内完成。我们的预处理是基于一个有点同构的密码系统。我们扩展了 Brakerski 等人的方案，因此我们可以执行分布式解密，并在一个密文中并行处理许多值。我们的预处理阶段的计算复杂度由公钥操作主导，我们需要 次安全乘法操作，其中 是一个参数，随着密码系统的安全参数而增加。这个模型的早期工作需要 操作。在实践中，预处理为 个用户准备了一个安全的 位乘法，大约需要 毫秒。

1 介绍

理论密码学的一个核心问题是安全的多方计算（MPC）。在这个问题中，持有隐私输入 的 方希望计算一个给定的函数 。一个安全的协议应该是这样的：诚实的参与者得到正确的结果，并且这个结果是唯一被释放的新信息，即使某些参与者的子集被对手控制。

在不诚实的多数情况下，即一半以上的参与者是腐败的，无条件安全协议不可能存在。在计算假设下，[6] 中显示了如何构建 UC - 安全的 MPC 协议，以处理除一方外所有各方都积极腐败的情况。为此所需的公钥机制通常很昂贵，因此很难为不诚实的多数人设计有效的解决方案。然而，最近有人提出了一种新的方法，使这种协议更加实用。这种方法的工作原理如下：首先在预处理模型中设计一个一般的 MPC 协议，其中假定可以访问一个 "可信的第三方"。这个第三方不需要知道要计算的函数，也不需要知道输入，他只是在计算开始前提供原材料。这使得 "在线" 协议只使用廉价的信息理论基元，因此是有效的。最后，人们通过一个使用公钥技术的安全协议来实现受信任的第三方，然后这个协议可以在预处理阶段运行。这方面目前的技术水平是 Bendlin 等人、Damga ̊rd/Orlandi 和 Nielsen 等人 [3,9,16] 的协议。Ishai 等人的 "MPC-in-thehead" 技术 [13,12] 具有类似的整体渐进复杂性，但常数较大，在线阶段效率较低。

最近，随着 Gentry [10] 提出的完全同态加密（FHE）的出现，另一种方法已经成为可能。在这种方法中，所有各方首先在 FHE 方案下对他们的输入进行加密；然后他们利用同态特性对密文进行所需函数的评估，最后他们对最终的密文进行分布式解密以获得结果。基于 FHE 的方法的优点是，只需要互动来提供输入和获得输出。然而，低带宽消耗是有代价的；目前的 FHE 方案非常慢，只能评估小电路，也就是说，它们实际上只提供所谓的部分同态加密（somewhat homomorphic encryption, SHE）。这一点可以通过以下方式来规避：或者通过假设循环安全和实施昂贵的引导操作，或者通过扩展参数大小来实现 "分级 FHE" 方案，该方案可以评估大程度的电路（指数级的数量）[4]。与其他方法一样，其主要成本是算术电路中的乘法数量。因此，虽然理论上有吸引力，但通过 FHE 的方法在实践中与传统的 MPC 方法没有竞争力。

1.1 本文的贡献

最优在线阶段：我们提出了一个预处理模型中的 MPC 协议，该协议可以在任何有限域 上安全地计算算术电路 。该协议在统计上是 UC 安全的，可以防止多达 个参与者的主动和适应性破坏，我们假设同步通信和安全的点对点通道。以 中的基本操作来衡量，所做的工作总量为 ，其中 是 的大小。这个模型中的所有早期工作的复杂性为 。类似的改进也适用于通信复杂度和人们需要从预处理中存储的数据量。因此，每个参与者在在线阶段所做的工作基本上是与 无关的。此外，它只比人们在明确的情况下计算电路所需的一个小常数系数大。这是预处理模型中第一个具有这些特性的协议。

最后，我们显示了一个下限，意味着在预处理所需的数据量方面，我们的协议在一个常数因素下是最优的。我们还得到了一个关于所需比特操作数量的类似下限，因此在我们的协议中所做的计算工作是最佳的，可以达到多项系数。

这里提到的所有结果对于大字段的情况都是成立的，也就是说，在小常数 的情况下，所需的错误概率是 。请注意，MPC 的许多应用需要整数运算、模块化还原、转换为二进制等，我们可以通过在 中进行计算， 足够大以避免溢出。这自然导致了大字段的计算。如前所述，我们的协议对所有场都有效，但像这个模型的早期工作一样，对于小场来说，它的效率较低，对于错误概率 来说，基本上是 的系数，详细情况见完整版本。

与 [3] 相比，获得我们的结果需要新的思路，[3] 以前是最先进的，它是基于加法秘密共享，其中秘密中的每个共享都使用信息论的消息认证码（ ）进行认证。由于每个参与者都需要有自己的密钥， 个共享中的每一个都需要用 个 来验证，所以这种方法本身就是二次方的。我们的想法是用一个全局密钥来验证秘密值本身而不是共享。这似乎导致了一个 "鸡和蛋" 的问题，因为如果不知道密钥，就无法检查 ，但如果密钥是已知的， 就可以被伪造。我们对这个问题的解决方案包括秘密共享密钥，谨慎地安排数值的披露时间，以及各种技巧来减少检查一组 的摊销成本。

有效地利用 FHE 进行 MPC：作为概念上的贡献，我们提出了我们认为是使用 FHE/SHE 进行计算效率高的 MPC 的 "正确" 方法，即使用它来实现预处理阶段。我们注意到，由于这种预处理通常是基于 Beaver [2] 的经典电路随机化技术，它可以通过并行评估许多小的乘法深度的小电路（在我们的例子中实际上是深度 1）来完成。因此，SHE 就足够了，我们不需要引导，而且我们可以使用 [17] 的 SHE SIMD 方法来并行处理单个密文中的许多值。

为了利用这个想法，我们将 SIMD 方法应用于 [5] 中的密码系统（也见 [11]，其中也使用了这种技术）。为了获得最佳性能，我们需要对我们可以使用的参数值进行非微妙的分析，为此我们证明了一些关于循环场嵌入的规范的结果。我们还为我们的密码系统设计了一个分布式解密程序。这个协议只对被动攻击具有鲁棒性。然而，这对于整个协议的主动安全是足够的。直观地说，这是因为对手能做的唯一破坏是在获得的解密结果中加入一个已知的错误项。这对在线协议的影响是，某些秘密值的共享可能是不正确的，但这将被涉及 的检查所捕获。最后，我们将 [3] 中关于明文知识的零知识证明用于我们的目的，特别是我们改进了对其提供的健全性保证的分析。这影响了密码系统的参数选择，因此提高了整体性能。

一种高效的预处理协议：综上所述，我们得到了一个恒定轮次的预处理协议，假设底层密码系统在语义上是安全的，它对 个参与者的主动和静态腐败是 UC 安全的，这由多项式（PLWE）假设得出。如果没有设置假设，就无法获得对不诚实的多数人的 UC 安全。在本文中，我们假设我们的密码系统的密钥对已经生成，并且秘密密钥已经在参与者之间共享。

以前在预处理 / 在线模型中的工作 [3,9] 在每个安全乘法中使用 公钥操作，而我们只需要 操作，其中 是一个随着 SHE 方案的安全参数增长的数字（在我们的具体实例中，在 中计算的 ， ）。我们强调，我们适应的方案与不允许这种优化的 [5] 的基本版本完全一样有效，所以改进确实是 "名副其实的"。

与上面提到的在整个协议中使用 FHE 的方法相比，我们结合预处理和在线阶段实现了一个从理论上无法比拟的结果，但更实用：我们需要更多的通信和回合，但计算开销要小得多 —— 我们需要 的公钥操作，而 FHE 方法则是 ，对于现实中的 和 值，我们有 。此外，我们只需要一个低深度的 SHE，这首先是更有效的。最后，我们可以把所有使用 SHE 的工作推到一个独立于函数的预处理阶段。

实践中的表现：预处理和在线阶段都已经实现，并在局域网上连接的最新机器上对 个参与者进行了测试。预处理需要大约 毫秒的摊销时间来准备一个 位 的 乘法，安全级别大致相当于 位 ，零知识证明的错误概率为 （错误概率可以通过重复 证明降低到 ，这最多需要两倍的时间）。这比初步估计的 [3] 的最有效实例快 到 个数量级。在线阶段在 毫秒的摊销时间内执行一个安全的 位乘法。这些粗略的数量级，以及处理非微不足道的参与者数量的能力，在本文所描述的协议的最近实施中得到了证实 [7]。

同时进行的相关工作：在最近的独立工作 [15,1,11] 中，Meyers at al., Asharov et al. 和 Gentry et al. 也使用 FHE 方案进行多方计算。他们遵循上述的纯 FHE 方法，使用为特定 FHE 方案定制的阈值解密协议。他们主要关注的是回合复杂度，而我们希望将计算开销降到最低。我们注意到，在 [11] 中，Gentry 等人通过展示一种使用 FHE SIMD 方法计算任何电路同态的方法来获得小的开销。然而，这需要完整的 FHE 与引导（在任意电路上工作），并且（目前）没有导致一个实用的协议。

在 [16] 中，Nielsen 等人考虑了布尔电路的安全计算。他们的在线阶段与 [3] 相似，而预处理是一个基于不经意传输的聪明和非常有效的构造。这个结果是对我们的补充，因为我们的目标是大领域的计算，这对某些应用来说是好的，而对于其他情况，布尔电路是表达所需计算的最紧凑的方式。当然，人们可以使用 [16] 中的预处理来为我们的在线阶段设置数据，但目前的基准表明，我们的方法对于大字段，例如 位或更大的字段来说更快。

在介绍的最后，我们将介绍一些基本的符号，这些符号将在本文中使用。对于一个向量 ，我们用 , 和 . 我们让 表示 的一个未指定的可忽略函数。 如果 是一个集合，我们让 表示就 上的均匀分布对变量 进行赋值；我们用 表示一个值 ，作为 的缩写。如果 是一个算法， 意味着将 的输出分配给 ，其中的概率分布是在 的随机硬币上。最后 意味着 " 被定义为 "。

2 在线协议

我们的目的是构建一个在 上对一些素数 进行算术多方计算的协议。更确切地说，我们希望实现 中提出的理想功能。 我们的 MPC 协议是由预处理（或离线）阶段和在线阶段组成的。在这一节中，我们首先介绍了在线阶段，该阶段假定可以获得一个理想功能 。在第 5 节中，我们展示了如何在一个独立的预处理阶段实现这一功能。

在我们的在线协议规范中，为简单起见，我们假设一个广播通道是以单位成本提供的，每一方只有一个输入，并且只有一个公共输出值需要计算。在完整版本中，我们解释了如何实现我们需要的点对点信道的广播，并解除对输入和输出数量的限制，而不影响整体的复杂性。

在介绍具体的在线协议之前，我们给出了结构背后的直觉和动机。我们将使用无条件安全的 来保护秘密值不被主动的对手所操纵。然而，我们不是像 [3] 中那样对秘密值的共享进行认证，而是对共享值本身进行认证。更具体地说，我们将使用一个在 中随机选择的全局密钥 ，对于每个秘密值 ，我们将在参与者之间加法分享 ，同时我们也秘密分享一个 。这种表示秘密值的方式是线性的，就像 [3] 中的表示一样，因此我们可以根据我们在预处理中产生的乘法三元组 `a la Beaver [2] 进行安全乘法。

一个直接的问题是，可靠地打开一个值似乎需要我们检查 ，而这需要参与方知道 。然而，一旦 被知道，其他值的 就可以被伪造。为了解决这个问题，我们把对 的检查（打开的值）推迟到输出阶段（当然，这可能意味着一些打开的值是不正确的）。在输出阶段，参与方产生一个随机的线性组合，包括已开的值和他们在相应的 中的共享；他们对结果作出承诺，然后才打开 （见图 1）。其直觉是，由于承诺的存在，当 被揭示时，腐败的参与方利用钥匙的知识已经太晚了。因此，如果 检查出来，所有打开的值都是高概率正确的，所以我们可以相信我们计算的输出值是正确的，并可以安全地打开它们。

值和 MAC 的表示：在在线阶段，每个共享值 的表示方法如下： 其中 ， 。参与方 公开持有 ， ， 。解释为 是全局密钥 下认证 的 。

计算：使用表征的自然分量相加，并抑制 , 的基本选择以保证可读性，对于秘密值 ， 和公共常数 ，我们显然有： 其中 。这种轻松添加公共值的可能性是 定义中的 "公共修饰语" 的原因。现在很清楚，我们可以直接对以这种方式表示的值进行安全的线性计算。

剩下的就是乘法了：这里我们使用预处理。我们希望预处理能够输出随机三元组 、 、 ，其中 。然而，我们的预处理产生的三元组满足 ，其中 是一个可以由对手引入的错误。因此，我们需要在使用该三元组之前对其进行检查。这种检查可以通过 "牺牲" 另一个三元组 、 、 来完成，其中同样的乘法平等应该成立（详见协议）。给出这样一个有效的三元组，我们可以用以下标准方式进行乘法运算。为了计算 ，我们首先打开 得到 ， 得到 。然后 。因此，新的表示可以计算为： 一个重要的注意点是，在我们的协议中，我们实际上不能保证我们的工作结果是正确的，因为我们没有立即检查开放值的 。在协议的第一部分，各方只做我们定义的部分开放，也就是说，对于一个值 ，每一方 将 发送给 ，后者计算 并将 广播给所有参与者。为了简单起见，我们在此假设我们总是通过 ，而在实践中，我们会平衡各参与者的工作量。

如前所述，我们将检查工作推迟到协议的输出阶段结束。为了检查 ，我们需要来自预处理的全局密钥 。我们从预处理中得到 ，但其表示方式略有不同： 其中 ， 。参与者 持有 ， ， 。我们的想法是， 是 的私钥 下认证 的 。为了打开 ，每个 向每个 发送他对 的共享 和他对 的 的共享 ， 是用 的私钥做的，然后 检查 。(为了只向 一方开放值，其他各方将简单地只向 发送他们的共享，由 来做检查。只需要 和 的共享就可以了）。

最后，预处理还将输出 对随机值 ，在两个呈现的表示中 ， 。这些对在协议的输入阶段使用。

在线阶段的完整协议如图 1 所示。它假定可以获得一个承诺功能 ，该功能只是接收参与者的承诺值，存储它们，并在承诺者的要求下向所有参与者揭示一个值。这样的功能可以有效地实现，例如，基于 加密或 假设 [8,14]。然而，我们在完整版中表明，我们可以只基于 ，以 的计算和通信成本做理想的承诺。

复杂性：一个安全乘法的（摊销）成本很容易看出是 中的 个局部基本运算，以及 个场元素的通信。线性运算有相同的计算成本，但不需要通信。输入阶段需要 个通信和计算来打开 到 和一个广播。做输出阶段需要打开 个承诺。事实上，所使用的承诺总数也是 ，所以这给复杂性增加了一个 项。因此，总的来说，我们得到了引言中所说的复杂度： 基本字段操作和存储 / 通信复杂度为 的字段元素。

我们现在可以说明在线阶段的安全定理，其证明可以在完整版本中找到。

定理 1：在 、 混合模型中，协议 实现了 的统计安全性，以抵御任何静态活动对手对多达 方的破坏。

基于 [18] 的一个结果，我们还可以显示一个协议所需的预处理数据量和工作量的下限。该证明在完整版中。

定理 2：假设一个协议 是预处理模型，可以计算出最多为 大小的 上的任何电路，对最多为 个主动腐败的参与者具有安全性。我们假设参与者提供的输入数量大致相同（每个 ），并且任何任何参与者都可能收到输出。那么预处理必须向每个参与者输出 比特，对于任何参与者 ，存在一个满足上述条件的电路 ，其中 的安全计算要求 执行的预期比特操作数为 。

很容易看出，我们的协议满足定理中的条件，并且它满足第一个约束的常数因素和第二个约束的多对数因素（作为安全参数的函数）。

图 1. 在线阶段

3 抽象的部分同态加密方案

在这一节中，我们指定了我们的密码系统需要的抽象属性。具体实例见第 6 节。

我们首先定义明文空间 。这将由特征 的有限域 的直接乘积给出。 中元素的组成式加法和乘法将用 和 表示。我们假定有一个注入式编码函数 ，它将 中的元素转化为环 中的元素，该环对于某个整数 来说等于 （作为一个 模）。我们还假设有一个解码函数 ，它接收 中的任意元素，并返回 中的元素。对于所有 ，我们要求 ，并且解码操作与场的特征兼容，即对于任何 我们有 。最后，编码函数产生 "短" 向量。更确切地说，对于所有 有 ，其中 。

中的两个运算将用 和 来表示。 中的加法运算被假定为分量式加法，而我们对乘法不作假定。我们所要求的是，对于所有的元素 ，以下的属性是成立的： 从现在开始，当我们讨论明文空间 时，我们假设它隐含着某个整数 的编码和解码函数。如果 中的元素在每个 槽中都有相同的分量，那么我们称之为 "对角线" 元素。我们令 对于 表示元素 。

我们的密码系统由以下定义的算法的元组 组成，并以安全参数 为准绳。

：这个参数生成算法输出一个整数 （如上），编码和解码函数的定义，以及一个随机算法 的描述，该算法输出 中的向量。我们假设 输出 ， ，但概率可忽略不计。加密算法使用 来选择加密时需要的随机硬币。算法 也输出一个加法非线性群 。群 也拥有一个（不一定是封闭的）乘法算子，它是换元的，分布在 的加法群中。群 是假设密文位于其中的群。我们用 和 来表示对 的操作，并以自然的方式将这些操作扩展到 元素的向量和矩阵上。最后， 输出了一个允许在 上进行算术 SIMD 电路的集合 ，这些是我们的方案能够评估密文的函数集合。我们可以把 看作是 的一个子集，在这里我们对函数 在 的的输入进行了总共 次的并行评估。我们假设所有其他算法都把 的输出 作为隐式输入。

：该算法输出一个公钥 和一个秘钥 。

：当输入 ， 时，这个确定性的算法输出一个密文 。当应用这个算法时，人们将从应用编码函数中获得 ，并通过调用 获得 。当我们写 时，这就是我们的意思，其中 。然而，我们在中间状态上定义 是很方便的， 。为了简化符号，如果随机性 的值对我们的讨论不重要，我们就写成 。为了使我们下面的零知识证明奏效，我们将要求在 中使用随机性 的明文 增加 个 "干净的" 密文（对于 的 "小" 值），结果是可以通过增加明文和随机性获得密文，作为整数向量，然后应用 ，即 ：在输入密匙和密文 时，它返回一个元素 ，或符号 。

现在我们能够定义上述抽象方案的各种属性，我们将需要这些属性。但首先要有一点符号。对于一个函数 ，我们让 表示 中的变量数，我们让 表示 在 上诱导的函数。也就是说，给定 ，我们用 替换每个 操作，用 替换每个 操作，用 替换每个常数 。另外，给定一组 向量 ，我们以自然的方式定义 ，在每个坐标上平行应用 。

正确性：直观地讲，正确性意味着，如果人们对应用于 加密的变量向量的函数 的结果进行解密，那么这应该返回与应用于 明文的函数相同的值。然而，为了在我们的协议中应用该方案，我们需要更自由一些，即解密结果应该是正确的，即使我们开始的密文不一定是由正常的加密算法产生的。它们只需要 "包含" 编码和随机性，而这些编码和随机性不能太大，从而使编码解码为合法的值。从形式上看，该方案被认为是 正确的，如果 我们将说一个密文是 可接受的，如果它可以作为上述实验中的密文 得到，即通过将 的一个函数应用于由 (合法) 编码和随机性产生的密文，这些密文由 和 所约束。

：这是一个随机算法，输出一个无意义的公钥 。我们要求对任何消息 的加密与对 的加密在统计上是不可区分的。此外，如果我们设置 和 ，那么 和 在计算上是不可区分的。这意味着该方案在通常意义上是 安全的。

分布式解密：我们假设，作为一个设定的假设，一个共同的公钥已经被设定，其中的秘钥已经以这样的方式在参与者之间秘密共享，他们可以合作解密一个密文。我们自始至终假定只有 可接受的密文被解密，这一约束由我们的主要协议保证。

我们注意到，为了显示 UC 安全性，总是需要一些设定的假设，这是我们在这里的目标。具体来说，我们假设有一个功能 ，如图 2 所示。它基本上生成一个密钥对，并使用一个秘密共享方案在参与者之间共享秘密密钥，该方案被假定为密码系统规范的一部分。由于我们想允许除一个参与者外的所有参与者被破坏，最大的不合格集合必须是 个参与者的所有集合。

我们注意到，可以做一个较弱的设置假设，如共同参考字符串（CRS），并使用 CRS 模型的一般 UC 安全多方计算协议来实现 。 虽然这可能不是很高效，但人们只需要在系统的生命周期内运行一次这个协议。

我们还希望我们的密码系统能够实现图 3 中的功能 ，它基本上规定了参与者可以合作解密一个 可接受的密文，但该协议只对被动攻击安全：对手得到正确的解密结果，但可以决定诚实的参与者应该了解哪个结果。

我们现在终于准备好定义底层密码系统应该满足的基本属性集，以便在我们的协议中使用。在这里，我们使用了一个 "信息论" 的安全参数 ，以控制我们下面的 证明中的错误。

定义 1：（可接受的密码系统）：让 包含形式为 的公式，以及所有 "更小" 的公式，即有较少的加法，可能没有乘法。如果一个密码系统是由具有上述属性的算法 定义的，是 正确的，其中 而其中 可以是一个任意的常数。最后，存在一个 中要求的秘密共享方案和一个协议 ，其特性是当与 组成时，它安全地实现了 的功能。

集合 被定义为包含我们在主要协议中需要的对密文的所有计算。在本文中，我们将假设 ， 在这里是以 、 和 来定义的。这是因为这些是我们可以通过我们的零知识协议迫使腐败的参与者遵守的界限，我们将看到。

图 2. 分布式密钥生成的理想功能

图 3. 分布式密钥生成和解密的理想功能

4 零知识证明的明文知识

本节介绍了一个零知识协议，该协议的输入是由我们协议中的一个参与者生成的 密文 ，他将作为验证者。如果验证人是诚实的，那么 ，其中 是从编码函数中得到的，即 ，而 是从 中生成的（所以我们可以假设 ）。我们的协议是一个零知识的明文知识证明（ ），其关系如下： 只有当密文 满足 和 时，零知识和完整性属性才成立。

在我们的预处理协议中，参与者将被要求为他们提供的所有密文提供这样一个 。根据密码系统的可接受性，这将意味着协议中出现的每个密文都是 可接受的，因此可以被正确解密。 也可以用一个标志 来调用，这将修改证明，使其额外证明 是一个对角元素。

该协议不是为了实现理想功能，但我们仍然可以使用它，并证明主协议的 UC 安全性，因为我们将始终通过调用 理想功能来生成挑战 （更多细节见完整版本）。

该协议及其安全性证明在完整版本中给出，其每个密文的计算复杂性基本上是恒定数量的加密成本。在完整版本中，我们还给出了 证明的一个变体，允许 、 的值更小，即 ， ，从而进一步提高性能。这个变体在使用 启发式执行时效率最高（尽管它也可以在没有随机口令的情况下工作），我们相信这个变体是实际执行的最佳选择。

5 预处理阶段

在这一节中，我们构建了协议 ，它在功能 （图 3）和 的存在下安全地实现了功能 。预处理使用上述具有 的抽象密码系统，但在线阶段是为 中的消息设计的。因此，我们将符号 和 扩展到 中的信息：由于 上的加法和乘法是分量级的，对于 ，我们定义 ，同样，对于 也是如此。反之，一旦在预处理中产生了一个关于向量的表示（或一对、三对），它将被分解成其坐标，以便在在线阶段使用。在图 4、5 和 6 中，我们介绍了被主预处理协议分几步访问的子协议。请注意，这些子协议并不是为了实现理想的功能：它们的目的只是为了总结主协议中在不同场合重复出现的部分。下面的定理 3 在完整版中得到了证明。

定理 3：协议 （图 7）实现了 的计算安全性，在 、 混合模型中，当底层密码系统是可接受的时候，可以抵御任何静态的、主动的对手破坏多达 方。

Fig. 4. The sub-protocol for additively secret sharing a plaintext m ∈ (Fpk )s on input a ciphertext em = Encpk(m)

图 4. 加法秘密共享明文 的子协议，其输入的密码文本

6 基于 LWE 的抽象方案的具体实例化

我们现在描述一下具体的方案，它是基于 Brakerski 和 Vaikuntanathan（BV）[5] 的某种同态加密方案。主要区别在于，我们只对乘法深度为 的电路的评估感兴趣，我们对在多个数据项上进行并行操作感兴趣，并且我们需要一个分布式的解密程序。在本节中，我们将详细介绍该方案和分布式解密程序；在完整版本中，我们将讨论该方案的安全性，并介绍一些参数大小的样本和性能数字。

参考文献

1. Asharov, G., Jain, A., L ́ opez-Alt, A., Tromer, E., Vaikuntanathan, V., Wichs, D.: Multiparty Computation with Low Communication, Computation and Interaction via Threshold FHE. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 483–501. Springer, Heidelberg (2012)

2. Beaver, D.: Efficient Multiparty Protocols Using Circuit Randomization. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 420–432. Springer, Heidelberg (1992)

3. Bendlin, R., Damg ̊ard, I., Orlandi, C., Zakarias, S.: Semi-homomorphic Encryption and Multiparty Computation. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 169–188. Springer, Heidelberg (2011)

4. Brakerski, Z., Gentry, C., Vaikuntanathan, V.: Fully homomorphic encryption without bootstrapping. Electronic Colloquium on Computational Complexity (ECCC) 18, 111 (2011)

5. Brakerski, Z., Vaikuntanathan, V.: Fully Homomorphic Encryption from RingLWE and Security for Key Dependent Messages. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 505–524. Springer, Heidelberg (2011)

6. Canetti, R., Lindell, Y., Ostrovsky, R., Sahai, A.: Universally composable two-party and multi-party secure computation. In: STOC, pp. 494–503 (2002)

7. Damg ̊ard, I., Keller, M., Larraia, E., Miles, C., Smart, N.P.: Implementing AES via an actively/covertly secure dishonest-majority MPC protocol. IACR Cryptology ePrint Archive, 2012:262 (2012)

8. Damg ̊ard, I.B., Nielsen, J.B.: Perfect Hiding and Perfect Binding Universally Composable Commitment Schemes with Constant Expansion Factor. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 581–596. Springer, Heidelberg (2002)

9. Damg ̊ard, I., Orlandi, C.: Multiparty Computation for Dishonest Majority: From Passive to Active Security at Low Cost. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 558–576. Springer, Heidelberg (2010)

10. Gentry, C.: Fully homomorphic encryption using ideal lattices. In: Mitzenmacher, M. (ed.) STOC, pp. 169–178. ACM (2009)

11. Gentry, C., Halevi, S., Smart, N.P.: Fully Homomorphic Encryption with Polylog Overhead. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 465–482. Springer, Heidelberg (2012)

12. Ishai, Y., Kushilevitz, E., Ostrovsky, R., Sahai, A.: Zero-knowledge from secure multiparty computation. In: Johnson, D.S., Feige, U. (eds.) STOC, pp. 21–30. ACM (2007)

13. Ishai, Y., Prabhakaran, M., Sahai, A.: Founding Cryptography on Oblivious Transfer – Efficiently. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 572–591. Springer, Heidelberg (2008)

14. Lindell, Y.: Highly-Efficient Universally-Composable Commitments Based on the DDH Assumption. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 446–466. Springer, Heidelberg (2011)

15. Myers, S., Sergi, M., Shelat, A.: Threshold fully homomorphic encryption and secure computation. IACR Cryptology ePrint Archive, 2011:454 (2011)

16. Nielsen, J.B., Nordholt, P.S., Orlandi, C., Burra, S.S.: A new approach to practical active-secure two-party computation. IACR Cryptology ePrint Archive, 2011:91 (2011)

17. Smart, N.P., Vercauteren, F.: Fully homomorphic SIMD operations. IACR Cryptology ePrint Archive, 2011:133 (2011)

18. Winkler, S., Wullschleger, J.: On the Efficiency of Classical and Quantum Oblivious Transfer Reductions. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 707723. Springer, Heidelberg (2010)