基于RLWE的多方同态加密：当多方计算遇见同态加密

来自 RLWE 的 MHE：当 MPC 遇到同态加密

安全多方计算（MPC）实现了密码学的一个雄心勃勃的承诺：在保持正确性和分配信任的同时，对私有输入进行计算。然而，这个承诺在通信开销方面付出了巨大的代价。秘密共享协议中的每一次乘法都需要一轮交互，这意味着具有乘法深度 DDD 的电路需要在所有参与方之间至少进行 DDD 次同步交换。当考虑到每层消息数量扩展为 O(N2)O(N^2)O(N2) 的常见广播模式时，瓶颈就变得显而易见，吞吐量受限于网络延迟而不是算术速度。活跃性要求使情况更加脆弱，因为所有参与方必须在整个计算过程中保持在线，单个掉队者可能会使所有进程停滞，而掉线可能会迫使完全重启。

多方同态加密（MHE）解决了这些痛点，即通信开销和同步要求，而没有牺牲使 MPC 具有价值的分布式信任模型。核心洞察力非常巧妙：我们不共享数据，而是共享解密能力。各方合作生成一个公钥，同时将相应的私钥以加性方式在他们之间共享。这种设置解锁了一些非凡的东西，任何人都可以完全以非交互方式对密文进行任意电路的计算，计算期间不需要任何一方在线。唯一的交互发生在输出边界，各方在简短、带宽高效的步骤中进行协作以提供最终结果。

这种架构的转变从根本上改变了成本结构，从“每乘法层一轮”变为“每个结果一轮短的交互”，每方通信随着 NNN 线性扩展，并支持异步、广域部署。

理解 MPC 基线

安全模型

MPC 协议在以下几种选择下进行分析：

敌手行为。

• 半诚实（又名被动）：各方遵守代码，但试图从记录中推断出额外信息；通过模拟证明隐私性。
• 隐蔽（ε\varepsilonε-隐蔽）：敌手可能会偏离，但被捕获的概率 ≥1−ε\ge 1-\varepsilon≥1−ε；当威慑足够时有用。
• 恶意（主动/拜占庭）：允许任意偏差；协议添加检查/MAC/零知识证明，以在欺骗的情况下保持正确性和隐私性。

腐败模式。

• 静态：损坏的集合在协议开始之前就已确定。
• 自适应：敌手可以在运行期间选择破坏谁（甚至基于看到的消息或密钥）。
• 抢跑/强抢跑：在每一轮中，敌手首先看到诚实的消息，然后选择自己的消息，模拟最坏情况下的调度能力。

阈值/谁更强。

• 诚实多数：t<n/2t < n/2t<n/2（或 t<n/3t < n/3t<n/3 与广播）能够实现更强的活跃性，公平性和有保证的输出交付（GOD）通常可以通过更简单的工具实现。
• 不诚实多数：t≥n/2t \ge n/2t≥n/2 需要更重的原语（OT，承诺，HE）；通常，你可以通过（可识别的）中止获得隐私+正确性，但不能获得公平性/GOD。

目标（你证明的内容）。

• 隐私：除了输出之外，没有其他信息泄露（通过理想/真实范式的模拟器）。
• 正确性/可靠性：诚实方的输出等于 f(x1,…,xn)f(x_1,\dots,x_n)f(x1​,…,xn​)。
• 鲁棒性/活跃性：尽管有 ttt 次破坏，协议仍能完成。
• GOD（有保证的输出交付）和公平性：每个人都获得输出，并且没有人提前知道；没有诚实多数/额外设置通常是不可能的。
• 可识别中止和选择性中止抵抗：如果协议停止，你可以准确定位作弊者；中止不应泄露与输入相关的位。

证明框架/可组合性。

• 独立（基于模拟）：在隔离运行时的安全性。
• UC / GUC / JUC, IITM, CoSP：可组合模型，其中安全性在任意并发下得到保留；指定一个理想的功能 F\mathcal{F}F 并构建一个模拟器 S\mathcal{S}S 对抗环境 Z\mathcal{Z}Z。
• 计算与统计/完美：多项式时间假设下的保证与信息论安全性。

我们在这里假设什么。 在本文中，我们在非诚实多数、半诚实模型中工作，具有静态损坏且没有私有通道。

为了理解我们正在改进的内容，让我们简要地研究一下传统的 MPC 如何处理计算。在域 Fp\mathbb{F}_pFp​ 上的加性秘密共享中，秘密 x∈Fpx \in \mathbb{F}_px∈Fp​ 被分成共享 ⟨ ⁣⟨x⟩ ⁣⟩=(x1,…,xN)\langle\!\langle x \rangle\!\rangle = (x_1, \dots, x_N)⟨⟨x⟩⟩=(x1​,…,xN​)，其中 ∑ixi≡x(modp)\sum_i x_i \equiv x \pmod p∑i​xi​≡x(modp)。这种方法的美妙之处在于它的线性性，加法和标量乘法成为纯粹的本地运算，不需要任何通信。

乘法提出了一个完全不同的挑战。虽然各方可以在本地计算 ⟨ ⁣⟨x⟩ ⁣⟩i⋅⟨ ⁣⟨y⟩ ⁣⟩i\langle\!\langle x \rangle\!\rangle_i \cdot \langle\!\langle y \rangle\!\rangle_i⟨⟨x⟩⟩i​⋅⟨⟨y⟩⟩i​，但结果并不是 xyxyxy 的正确共享。标准的解决方案依赖于 Beaver 三元组，(a,b,c)(a,b,c)(a,b,c) 的经过身份验证的共享，其中 c=a⋅bc = a \cdot bc=a⋅b。给定 xxx 和 yyy 的共享以及一个三元组，在线乘法协议通过同步广播打开掩码值 d=x−ad = x - ad=x−a 和 e=y−be = y - be=y−b，然后使用恒等式 xy=c+ae+bd+dexy = c + ae + bd + dexy=c+ae+bd+de 在本地计算结果。

这种预处理范式，以 SPDZ 等协议为例，将工作分为一个离线阶段，该阶段使用某种同态加密生成经过身份验证的三元组，然后是一个轻量级的在线阶段，该阶段使用这些三元组。虽然这种分离使得即使在恶意设置中也能进行快速的在线计算，但它并没有消除根本的瓶颈：你仍然需要每乘法层一次交互式的打开。

实际成本累积得很快。每次打开通常涉及广播，除非你部署更复杂的网络原语，否则每层创建 Θ(N2)\Theta(N^2)Θ(N2) 条消息。一个掉队者会延迟整个回合，掉线需要重新共享或中止协议，并且在恶意设置中，每次打开都会带来额外的 MAC 检查和一致性验证开销。即使使用矢量化的批量操作，核心约束仍然不变，加法是免费的，但乘法需要交互。

这是我们正在努力改进的基线：用非交互式计算替换那些 DDD 交互式乘法层，同时保留“没有单方可以单独解密”的信任模型。

MHE 范式

我们的目标是简单而雄心勃勃：像标准同态加密一样保持计算的非交互性，同时像 MPC 一样保持解密能力的分布性。设置阶段让 NNN 方运行 RLWE/BFV 方案的分布式密钥生成（DKG），发布一个联合公钥 pkpkpk 以及用于重线性化、伽罗瓦运算和自举的必要计算密钥。私钥永远不会被组装，而是保持以加性方式共享为 s=∑i=1Nsis = \sum_{i=1}^N s_is=∑i=1N​si​，其中第 iii 方仅持有 sis_isi​。

设置完成后，工作流程变得非常简单。任何数据所有者都可以将其输入 xxx 加密为 ct←Encpk(x)ct \leftarrow \mathrm{Enc}_{pk}(x)ct←Encpk​(x)，并且从那时起，任何人，甚至一个完全不受信任的服务器，都可以通过计算 ctout←Eval(f;ct1,…,ctm;eval-keys)ct_{\text{out}} \leftarrow \mathrm{Eval}(f; ct_1,\ldots,ct_m; \text{eval-keys})ctout​←Eval(f;ct1​,…,ctm​;eval-keys) 来计算任意函数，而无需与各方进行任何交互或了解有关输入的任何信息。这完全消除了“每乘法层一轮”的瓶颈。

唯一剩余的交互发生在输出时，各方协作进行集体密钥切换（CKS），以从共享秘密 sss 切换到目标密钥 s′s's′。通常，此目标是 s′=0s'=0s′=0 以进行集体解密，或者它可能是通过公钥切换（PCKS）协议的另一方的公钥。关键在于，这种繁重的计算（整个电路计算）可以离线且非交互地运行，各方仅在线一次，以获取每个方的尺寸随 NNN 线性扩展的短记录。

与传统 MPC 的对比非常明显。MPC 共享数据本身，用加性共享 ⟨ ⁣⟨x⟩ ⁣⟩=(x1,…,xN)\langle\!\langle x\rangle\!\rangle=(x_1,\dots,x_N)⟨⟨x⟩⟩=(x1​,…,xN​) 替换每个秘密 xxx 并在这些共享上直接运行计算，而 MHE 共享解密能力。输入在联合公钥下加密一次，而私钥保持以加性方式共享。任何人都可以非交互地对密文进行计算，并且只有在最后各方才会协作进行解密。

基于 MBFV 的 MPC 协议

本节介绍我们使用 BFV/RLWE 加密在二次幂分圆环 Rq=Zq[X]/(Xn+1)R_q=\mathbb{Z}_q[X]/(X^n+1)Rq​=Zq​[X]/(Xn+1) 和 Rt=Zt[X]/(Xn+1)R_t=\mathbb{Z}_t[X]/(X^n+1)Rt​=Zt​[X]/(Xn+1) 上进行的具体实例化，其中缩放参数 Δ≈⌊q/t⌋\Delta\approx \lfloor q/t \rfloorΔ≈⌊q/t⌋。该协议涉及 NNN 方 P1,…,PN\mathcal{P}_1,\ldots,\mathcal{P}_NP1​,…,PN​，他们共同持有以加性方式共享的密钥 s=∑isis=\sum_i s_is=∑i​si​，同时发布一个联合公钥 pkpkpk 并提供重线性化、伽罗瓦运算和自举的必要计算密钥。

工作流程遵循清晰的关注点分离。数据所有者在公钥 pkpkpk 下加密 RtR_tRt​ 中的消息，不受信任的计算方 E\mathcal{E}E 在没有任何方交互的情况下离线执行所有同态工作，最后，一组合格的参与方协作以集体或向指定接收方 R\mathcal{R}R 发布结果。在整个过程中，我们保持公共记录原则，其中所有交互步骤都可以在经过身份验证的广播通道上记录，而无需私有通信通道。

分布式密钥生成

我们的方法的基础在于创建一个 BFV 密钥，该密钥永远不会被组装，同时仍然表现得像一个标准的小范数密钥。这个过程非常简单，不需要任何通信。每个参与方 Pi\mathcal P_iPi​ 在本地使用标准的 BFV 密钥生成算法采样一个小共享 si←BFV.SecKeyGen()s_i \leftarrow \texttt{BFV.SecKeyGen}()si​←BFV.SecKeyGen()，并且联合密钥被加性地定义为 s=[∑i=1Nsi]qs = \big[\sum_{i=1}^N s_i\big]_qs=[∑i=1N​si​]q​。

这种非交互式方法意味着没有消息交换，不需要私有通道，并且完整的密钥 sss 从未以明文形式存在于任何地方。权衡是 sss，作为 NNN 个小多项式的总和，其范数随着 NNN 的增加而增加。参数选择必须考虑这种增长，但即使对于中等数量的参与方，也不会造成根本的瓶颈。

一旦各方完成此分布式密钥生成，他们将继续使用以下公共记录过程来推导联合公钥和计算密钥，所有这些都建立在共享密钥 sss 的加性结构之上。

集体公钥生成

为联合秘密 s=∑isis=\sum_i s_is=∑i​si​ 创建一个 BFV 公钥，而无需组装 sss，这需要仔细的协调，但协议本身非常简单明了。关键的见解是使用公共参考字符串来确保所有各方都使用相同的随机多项式 p1∈Rqp_1 \in R_qp1​∈Rq​。在被动安全模型中，这可以使用像 BLAKE2b 这样的伪随机函数从共享种子中确定性地推导出来，从而保证每个人都导出相同的 p1p_1p1​ 值。

每个参与方 Pi\mathcal P_iPi​ 从指定的误差分布中采样一个小误差项 ei←χe_i \leftarrow \chiei​←χ 并发布他们的贡献 p0,i=[−sip1+ei]q∈Rqp_{0,i} = \big[-s_i p_1 + e_i\big]_q \in R_qp0,i​=[−si​p1​+ei​]q​∈Rq​。聚合步骤非常简单，任何人都可以将这些贡献相加得到

p0=[∑ip0,i]q=[−(∑isi)p1+∑iei]qp_0 = \big[\sum_{i} p_{0,i}\big]_q = \big[-\big(\sum_{i} s_i\big) p_1 + \sum_{i} e_i\big]_qp0​=[i∑​p0,i​]q​=[−(i∑​si​)p1​+i∑​ei​]q​

这给了我们联合公钥 cpk=(p0,p1)\mathrm{cpk} = (p_0, p_1)cpk=(p0​,p1​)。

此构造使用秘密 sss 和聚合误差 e=∑ieie=\sum_i e_ie=∑i​ei​ 保持完全的 BFV 结构。安全论证很明确：由于 p1p_1p1​ 在 RqR_qRq​ 中均匀分布，并且聚合误差 eee 具有小范数，因此在决策 RLWE 假设下，该对 (p0,p1)(p_0,p_1)(p0​,p1​) 在计算上与标准的 BFV 公钥无法区分。

虽然最坏情况下的范数 ∥s∥\lVert s\rVert∥s∥ 和 ∥e∥\lVert e\rVert∥e∥ 随 NNN 线性增长，但是可以在设置期间考虑这种参数缩放，而不会为合理的参与方数量创建根本的可伸缩性障碍。通信配置文件非常高效，每个参与方只需要一次广播，并且是完全公共的记录，不需要私有通道。建立联合公钥 cpk\mathrm{cpk}cpk 后，标准的 BFV 加密完全按照单密钥设置中的方式进行，但现在在共享密钥 sss 下运行。

重线性化密钥生成

与公钥生成相比，在多方设置中生成重线性化密钥需要更多的技巧，因为我们需要在共享秘密 s=∑isis=\sum_i s_is=∑i​si​ 下“加密” s2ws^2\mathbf{w}s2w，而不使用公共加密预言机，同时保持较低的噪声水平。

以下解决方案使用公共 coins 结合共享秘密的加性结构来模拟中心化 BFV 重线性化密钥的质量。该协议将向量 a∈Rqℓ\mathbf{a}\in R_q^{\ell}a∈Rqℓ​ 作为公共输入，该向量从公共参考字符串中采样，以及分解基 w=(w0,…,wℓ−1)⊤\mathbf{w}=(w^0,\ldots,w^{\ell-1})^\topw=(w0,…,wℓ−1)⊤，而每个参与方 PiP_iPi​ 贡献其私钥共享 sis_isi​。

该协议分两个协调步骤进行。在第一步中，每个参与方 PiP_iPi​ 采样一个小掩码项 uiu_iui​ 以及误差向量 e0,i,e1,i←χℓ\mathbf{e}_{0,i},\mathbf{e}_{1,i}\leftarrow\chi^{\ell}e0,i​,e1,i​←χℓ，然后发布贡献

(h0,i,h1,i)=(−uia+siw+e0,i,sia+e1,i).(\mathbf{h}_{0,i},\mathbf{h}_{1,i})=\big(-u_i\mathbf{a}+s_i\mathbf{w}+\mathbf{e}_{0,i}, s_i\mathbf{a}+\mathbf{e}_{1,i}\big).(h0,i​,h1,i​)=(−ui​a+si​w+e0,i​,si​a+e1,i​).

聚合后，这些贡献产生

h0=∑jh0,j=−ua+sw+e0 和 h1=∑jh1,j=sa+e1,\mathbf{h}_0=\sum_j\mathbf{h}_{0,j}=-u\mathbf{a}+s\mathbf{w}+\mathbf{e}_0 \text{ and } \mathbf{h}_1=\sum_j\mathbf{h}_{1,j}=s\mathbf{a}+\mathbf{e}_1,h0​=j∑​h0,j​=−ua+sw+e0​ 和 h1​=j∑​h1,j​=sa+e1​,

其中 u=∑juju=\sum_j u_ju=∑j​uj​，s=∑jsjs=\sum_j s_js=∑j​sj​，并且 ed=∑jed,j\mathbf{e}_d=\sum_j\mathbf{e}_{d,j}ed​=∑j​ed,j​。

第二步使用这些聚合值 h0,h1\mathbf{h}_0,\mathbf{h}_1h0​,h1​ 来完成重线性化密钥构造。每个参与方采样新鲜的误差项 e2,i,e3,i←χℓ\mathbf{e}_{2,i},\mathbf{e}_{3,i}\leftarrow\chi^{\ell}e2,i​,e3,i​←χℓ 并发布

(h0,i′,h1,i′)=(sih0+e2,i,(ui−si)h1+e3,i).(\mathbf{h}'_{0,i},\mathbf{h}'_{1,i})=\big(s_i\mathbf{h}_0+\mathbf{e}_{2,i}, (u_i-s_i)\mathbf{h}_1+\mathbf{e}_{3,i}\big).(h0,i′​,h1,i′​)=(si​h0​+e2,i​,(ui​−si​)h1​+e3,i​).

聚合这些最终贡献会产生重线性化密钥

rlk=(r0,r1)=(h0′+h1′,h1)=(−sb+s2w+se0+e1+ue2+e3,b).\mathbf{rlk}=(\mathbf{r}_0,\mathbf{r}_1)=(\mathbf{h}'_0+\mathbf{h}'_1, \mathbf{h}_1) = \big(-s\mathbf{b} + s^2\mathbf{w} + s\mathbf{e}_0 + \mathbf{e}_1 + u\mathbf{e}_2 + \mathbf{e}_3,\; \mathbf{b}\big).rlk=(r0​,r1​)=(h0′​+h1′​,h1​)=(−sb+s2w+se0​+e1​+ue2​+e3​,b).

通信要求适中，每个参与方在 ℓ\ellℓ 数字上进行两次公共广播，不需要私有通道。此构造成功使用公共 coins 和共享秘密结构来模拟中心化 BFV 重线性化密钥质量，从而大大改善了重线性化密文的噪声配置文件。

集体密钥切换

集体密钥切换（CKS）协议在非交互式计算阶段和结果传输之间提供了关键桥梁。给定在联合秘密 s=∑isis=\sum_i s_is=∑i​si​ 下加密的密文 ct=(c0,c1)ct=(c_0,c_1)ct=(c0​,c1​)，CKS 将其切换到各方集体知道的输出密钥 s′s's′，而不会泄露任何单独的共享 sis_isi​。目标密钥 s′s's′ 可能是出于解密目的的零，或者是旋转访问集后的新共享密钥。

协议设计优先考虑简单性和效率。每个参与方通过采样新鲜的涂抹噪声 eie_iei​ 并发布 hi=(si−si′)c1+ei∈Rqh_i = (s_i - s'_i)c_1 + e_i \in R_qhi​=(si​−si′​)c1​+ei​∈Rq​ 来做出贡献，其中 si′s'_isi′​ 表示他们对目标密钥的共享。然后，任何聚合器都可以计算 h=∑ihi=(s−s′)c1+eCKSh = \sum_{i} h_i = (s - s')c_1 + e_{\text{CKS}}h=∑i​hi​=(s−s′)c1​+eCKS​，其中 eCKS=∑ieie_{\text{CKS}}=\sum_i e_ieCKS​=∑i​ei​，并输出切换的密文 ct′=(c0′,c1)ct'=(c_0',c_1)ct′=(c0′​,c1​)，其中 c0′=c0+hc_0' = c_0 + hc0′​=c0​+h。

要查看下 s′s's′ 的正确性运行 BFV 解密

BFV.Dec(s′,ct′)=⌊tq[c0′+s′c1]q⌉=⌊tq[c0+(s−s′)c1+eCKS+s′c1]q⌉=⌊tq[Δm+ect+eCKS]q⌉=m,\begin{aligned} \mathrm{BFV.Dec}(s',ct') &= \left\lfloor \tfrac{t}{q}\Big[\, c_0' + s'c_1 \,\Big]_q \right\rceil \\ &= \left\lfloor \tfrac{t}{q}\Big[\, c_0 + (s-s')c_1 + e_{\text{CKS}} + s'c_1 \,\Big]_q \right\rceil \\ &= \left\lfloor \tfrac{t}{q}\Big[\, \Delta m + e_{\text{ct}} + e_{\text{CKS}} \,\Big]_q \right\rceil \;=\; m, \end{aligned}BFV.Dec(s′,ct′)​=⌊qt​[c0′​+s′c1​]q​⌉=⌊qt​[c0​+(s−s′)c1​+eCKS​+s′c1​]q​⌉=⌊qt​[Δm+ect​+eCKS​]q​⌉=m,​

前提是切换后的噪声 ∥ect+eCKS∥∞\lVert e_{\text{ct}} + e_{\text{CKS}} \rVert_\infty∥ect​+eCKS​∥∞​ 保持在 BFV 解码半径 q/(2t)q/(2t)q/(2t) 内。每个贡献 hih_ihi​ 都被新鲜噪声 eie_iei​ 掩盖，从而确保各个 (si−si′)c1(s_i - s'_i)c_1(si​−si′​)c1​ 项在信息论上保持隐藏，而记录仅显示输出密文 ct′ct'ct′ 所隐含的内容。

通信配置文件非常出色，每个参与方只需广播一个环元素，再加上一个聚合步骤。这代表了“短边界回合”，它结束了完全离线评估。对于特殊情况的解密，设置 s′=0s'=0s′=0 给我们

c0′=c0+sc1+eCKS≈Δm+(ect+eCKS)c_0' = c_0 + s c_1 + e_{\text{CKS}} \approx \Delta m + (e_{\text{ct}}+e_{\text{CKS}})c0′​=c0​+sc1​+eCKS​≈Δm+(ect​+eCKS​)

允许在零密钥下直接解码以恢复消息 mmm。

公钥切换

虽然集体密钥切换处理各方集体知道目标密钥的情况，但公钥切换（PCKS）解决了必须将结果传递给仅公开了某个未知秘密 s′s's′ 的公钥 pk′=(p0′,p1′)pk'=(p_0',p_1')pk′=(p0′​,p1′​) 的外部接收者的情况。对于向解密访问集之外的接收者“推送”传递输出至关重要，在这种情况下 CKS 将不适用。

该协议在处理不知道目标密钥的额外复杂性的同时，保持相同的公共记录原则。每个参与方 PiP_iPi​ 采样小项 uiu_iui​ 和新鲜噪声 e0,i,e1,ie_{0,i}, e_{1,i}e0,i​,e1,i​ 从指定的误差分布中，然后发布

(h0,i,h1,i)=(sic1+uip0′+e0,i,uip1′+e1,i).(h_{0,i}, h_{1,i}) = \big(s_i c_1 + u_i p_0' + e_{0,i}, u_i p_1' + e_{1,i}\big).(h0,i​,h1,i​)=(si​c1​+ui​p0′​+e0,i​,ui​p1′​+e1,i​).

聚合后，切换后的密文变为 ct′=(c0′,c1′)=(c0+h0,h1)ct'=(c_0',c_1') = (c_0 + h_0, h_1)ct′=(c0′​,c1′​)=(c0​+h0​,h1​)，其中 h0=∑ih0,ih_0=\sum_i h_{0,i}h0​=∑i​h0,i​ 和 h1=∑ih1,ih_1=\sum_i h_{1,i}h1​=∑i​h1,i​。

使用 p0′=−(s′p1′+epk)p_0' = -\big(s' p_1' + e_{\mathrm{pk}}\big)p0′​=−(s′p1′​+epk​) 和 u=∑iuiu=\sum_i u_iu=∑i​ui​，ed=∑ied,ie_d=\sum_i e_{d,i}ed​=∑i​ed,i​ 对于 d∈{0,1}d\in\{0,1\}d∈{0,1}，根据 s′s's′ 解密产生

Dec(s′,ct′)=⌊tq[c0′+s′c1′]q⌉=⌊tq[c0+sc1+up0′+e0+s′(up1′+e1)]q⌉=⌊tq[Δm+ect+ePCKS]q⌉=m,\begin{aligned} \mathrm{Dec}(s',ct') &= \left\lfloor \tfrac{t}{q}\,[\, c_0' + s' c_1' \,]_q \right\rceil \\ &= \left\lfloor \tfrac{t}{q}\,[\, c_0 + s c_1 + u p_0' + e_0 \;+\; s' (u p_1' + e_1) \,]_q \right\rceil \\ &= \left\lfloor \tfrac{t}{q}\,[\, \Delta m + e_{\mathrm{ct}} \;+\; e_{\mathrm{PCKS}} \,]_q \right\rceil \;=\; m, \end{aligned}Dec(s′,ct′)​=⌊qt​[c0′​+s′c1′​]q​⌉=⌊qt​[c0​+sc1​+up0′​+e0​+s′(up1′​+e1​)]q​⌉=⌊qt​[Δm+ect​+ePCKS​]q​⌉=m,​

只要总噪声保持在 BFV 解码半径内，其中

ePCKS=e0+s′e1+uepk.e_{\mathrm{PCKS}} \;=\; e_0 \;+\; s' e_1 \;+\; u\, e_{\mathrm{pk}}.ePCKS​=e0​+s′e1​+uepk​.

因此 ∥ect+ePCKS∥∞<q/(2t)\|e_{\mathrm{ct}} + e_{\mathrm{PCKS}}\|_\infty < q/(2t)∥ect​+ePCKS​∥∞​<q/(2t) 保证了正确性。

安全性论证借鉴了 CKS，每个贡献都被新鲜噪声和公钥项掩盖，使得在半诚实模型中，给定输出密文， transcripts 是可模拟的。任何一方都无法获知目标密钥 s′s's′，并且不需要私有通道。成本概况与 CKS 匹配，每个参与方广播两个环元素外加聚合，从而能够高效地传递给外部接收方，同时保持所有安全属性。

在表示之间架桥

使用单轮协议和公共 transcripts 在密文（MHE 表示）和加法 shares（MPC 表示）之间无缝移动的能力，开启了强大的混合计算策略。这些桥接协议 Enc2Share 和 Share2Enc 充当了我们的集体引导方法的基石。

从密文到 Shares

Enc2Share 协议从一个 BFV 密文 ct=(c0,c1)ct=(c_0, c_1)ct=(c0​,c1​) 开始，该密文在集体密钥下加密消息 m∈Rtm\in R_tm∈Rt​，并生成加法 shares M1,…,MN∈RtM_1,\dots,M_N\in R_tM1​,…,MN​∈Rt​，使得 ∑iMi≡m(modt)\sum_i M_i \equiv m \pmod t∑i​Mi​≡m(modt)。该方法巧妙地将集体密钥切换与本地掩码相结合，以在整个转换过程中保持隐私。

每个参与方 PiP_iPi​ 采样一个新鲜掩码 Mi←RtM_i \leftarrow R_tMi​←Rt​ 和 smudging 噪声 e0,i←χCKSe_{0,i} \leftarrow \chi_{\text{CKS}}e0,i​←χCKS​，然后计算一个被掩码的部分解密

h0,i=sic1−ΔMi+e0,i,Δ=⌊q/t⌋.h_{0,i} = s_i c_1 - \Delta M_i + e_{0,i}, \qquad \Delta=\lfloor q/t\rfloor.h0,i​=si​c1​−ΔMi​+e0,i​,Δ=⌊q/t⌋.

参与方 P2,…,PNP_2,\ldots,P_NP2​,…,PN​ 发布它们的 h0,ih_{0,i}h0,i​ 值，而指定的参与方 P1P_1P1​ 则保留其自己的项。公共贡献聚合为

h0=∑i=2Nh0,i=(s−s1)c1−Δ(M−M1)+e0,h_0 = \sum_{i=2}^N h_{0,i} = (s-s_1)c_1 - \Delta(M-M_1) + e_0,h0​=i=2∑N​h0,i​=(s−s1​)c1​−Δ(M−M1​)+e0​,

其中 M=∑iMiM=\sum_i M_iM=∑i​Mi​ 并且 e0=∑i=2Ne0,ie_0=\sum_{i=2}^N e_{0,i}e0​=∑i=2N​e0,i​。

然后，参与方 P1P_1P1​ 在本地添加其秘密部分 s1c1s_1 c_1s1​c1​ 并应用 BFV 舍入映射以获得其 share：

y=c0+h0+s1c1=c0+sc1−Δ(M−M1)+e0,M1=[⌊tq[y]q⌉]t≡m−∑i=2NMi(modt),\begin{aligned} y &= c_0 + h_0 + s_1 c_1 = c_0 + s c_1 - \Delta(M-M_1) + e_0,\\ M_1 &= \Big[\Big\lfloor \tfrac{t}{q}[y]_q \Big\rceil\Big]_t \equiv m - \sum_{i=2}^N M_i \pmod t, \end{aligned}yM1​​=c0​+h0​+s1​c1​=c0​+sc1​−Δ(M−M1​)+e0​,=[⌊qt​[y]q​⌉]t​≡m−i=2∑N​Mi​(modt),​

因为 c0+sc1=Δm+ectc_0+s c_1=\Delta m+e_{\text{ct}}c0​+sc1​=Δm+ect​ 并且舍入会消除有界噪声。

隐私保护来自应用于每个已发布的 h0,ih_{0,i}h0,i​ 的 −ΔMi-\Delta M_i−ΔMi​ 掩码和新鲜的 smudging 噪声 e0,ie_{0,i}e0,i​，确保没有参与方了解底层消息 mmm，同时保持可模拟的 transcripts。只有 P1P_1P1​ 将公共总和与其私有项 s1c1s_1 c_1s1​c1​ 组合以获得其 share M1M_1M1​；没有任何一方会看到 mmm 本身。通信成本非常低，除了私有剩余的持有者外，每个参与方一个环元素，再加上一次解码操作。P1P_1P1​ 的角色是任意的，并且可以在不同的协议执行中轮换。

从 Shares 到密文

Share2Enc 协议逆转了此过程，从消息 mmm 的加法 shares M1,…,MNM_1,\dots,M_NM1​,…,MN​ 开始，并生成一个加密 mmm 的 BFV 密文 ct=(c0,c1)ct=(c_0, c_1)ct=(c0​,c1​)（在集体密钥下）。核心思想是将 (ΔMi,a)(\Delta M_i, a)(ΔMi​,a) 视为在平凡密钥零下的“明文密文”，然后应用集体密钥切换以从密钥零移动到共享密钥 sss。

使用从公共参考字符串中采样的公共元素 a∈Rqa \in R_qa∈Rq​，每个参与方 PiP_iPi​ 采样新鲜噪声 e1,i←χe_{1,i} \leftarrow \chie1,i​←χ 并计算一个贡献

ui=−sia+ΔMi+e1,iu_i = -s_i a + \Delta M_i + e_{1,i}ui​=−si​a+ΔMi​+e1,i​

其中噪声 e1,ie_{1,i}e1,i​ 提供通常的 smudging。所有参与方在单个轮次中同时发布他们的 uiu_iui​ 值。

组合器（任何参与方）聚合这些贡献以形成输出密文：

ct′=(∑i=1Nui,a)=(Δm−sa+e,a)ct' = \big(\sum_{i=1}^N u_i, a\big) = \big(\Delta m - s a + e, a\big)ct′=(i=1∑N​ui​,a)=(Δm−sa+e,a)

其中 e=∑ie1,ie=\sum_i e_{1,i}e=∑i​e1,i​，它具有标准的 BFV 加密形状。正确性如下，因为

c0′+sc1′=∑i(−sia+ΔMi+e1,i)+(∑isi)a=Δ∑iMi+∑ie1,i=Δm+e,c_0' + s c_1' = \sum_i(-s_i a + \Delta M_i + e_{1,i}) + \Big(\sum_i s_i\Big)a = \Delta \sum_i M_i + \sum_i e_{1,i} = \Delta m + e,c0′​+sc1′​=i∑​(−si​a+ΔMi​+e1,i​)+(i∑​si​)a=Δi∑​Mi​+i∑​e1,i​=Δm+e,

并且在标准解码界限下，BFV 舍入映射以极大的概率恢复 mmm。

直觉是，每个参与方贡献其集体密钥项 −as-as−as 的 share（即 −asi-a s_i−asi​），其缩放消息 ΔMi\Delta M_iΔMi​ 的 share 及其自己的新鲜噪声 e1,ie_{1,i}e1,i​。将这些贡献相加即可得到适当的 BFV 密文结构。或者，可以将 (ΔMi,a)(\Delta M_i, a)(ΔMi​,a) 视为“密钥为零下的明文密文”，并且该协议实现了从密钥零到共享密钥 sss 的集体密钥切换。

隐私保护来自每个贡献中的新鲜 smudging 噪声 e1,ie_{1,i}e1,i​，确保每个已发布对 (a,ui)(a, u_i)(a,ui​) 都显示为具有密钥 (−si)(-s_i)(−si​) 和嵌入消息 ΔMi\Delta M_iΔMi​ 的标准 RLWE 样本。通信成本非常低，每个参与方在一个带有公共 transcript 的单轮中一个环元素。组合器不需要任何秘密信息，只需要公共值 aaa 和已发布的 uiu_iui​ 项，但会生成只有参与方才能集体解密的密文。

集体引导

BFV 密文不可避免地会通过加法和乘法运算累积噪声，并且一旦此噪声接近解码界限，某种形式的刷新就变得必要。传统的 bootstraping 以同态方式评估解密函数，这在计算上是昂贵的。我们的集体 bootstraping 方法将这种繁重的计算换成了已经共享密钥的参与方之间的单个简短交互轮次，从而生成本质上是相同明文的新鲜加密的密文。

该方法利用了 BFV 解密结构，其中密文 (c0,c1)(c_0, c_1)(c0​,c1​) 通过以下公式解密为明文 mmm：

m=[⌊tq[c0+sc1]q⌉]t,Δ≈⌊qt⌋m = \Big[\Big\lfloor \tfrac{t}{q}\,\big[c_0+s\,c_1\big]_q \Big\rceil\Big]_t, \qquad \Delta \approx \big\lfloor\tfrac{q}{t}\big\rfloorm=[⌊qt​[c0​+sc1​]q​⌉]t​,Δ≈⌊tq​⌋

该协议将公共参考字符串元素 a∈Rqa \in R_qa∈Rq​ 以及需要刷新的密文 ct=(c0,c1)ct=(c_0, c_1)ct=(c0​,c1​) 作为公共输入。每个参与方 PiP_iPi​ 贡献其秘密 share sis_isi​，其中 s=∑isis=\sum_i s_is=∑i​si​，并且该协议生成一个刷新的密文 ct′=(c0′,c1′)ct'=(c_0',c_1')ct′=(c0′​,c1′​)，其噪声方差已重置为大约 Nσ2N\sigma^2Nσ2。

协议机制

在单个通信轮次期间，每个参与方执行相同的本地计算。参与方 PiP_iPi​ 首先采样一个掩码 share Mi∈RtM_i \in R_tMi​∈Rt​，该 share 将用于隐藏底层明文，以及 smudging 噪声 e0,i←χCKS(σct2)e_{0,i} \leftarrow \chi_{\mathrm{CKS}}(\sigma_{ct}^2)e0,i​←χCKS​(σct2​) 和新鲜噪声 e1,i←χe_{1,i} \leftarrow \chie1,i​←χ。这些随机元素确保没有单个参与方可以了解正在刷新的明文的任何信息。然后，参与方发布两个组件：

h0,i=sic1−ΔMi+e0,ih1,i=−sia+ΔMi+e1,i\begin{aligned} h_{0,i} &= s_i c_1 - \Delta M_i + e_{0,i}\\[2pt] h_{1,i} &= -s_i a + \Delta M_i + e_{1,i} \end{aligned}h0,i​h1,i​​=si​c1​−ΔMi​+e0,i​=−si​a+ΔMi​+e1,i​​

当这些贡献在所有参与方之间聚合时，我们获得捕获集体秘密的值，同时保持掩码结构：

h0=∑ih0,i=sc1−ΔM+e0,h1=∑ih1,i=−sa+ΔM+e1h_0=\sum_i h_{0,i}= s\,c_1 - \Delta M + e_0,\qquad h_1=\sum_i h_{1,i}= -s\,a + \Delta M + e_1h0​=i∑​h0,i​=sc1​−ΔM+e0​,h1​=i∑​h1,i​=−sa+ΔM+e1​

其中 M=∑iMiM=\sum_i M_iM=∑i​Mi​ 表示所有掩码 shares 的总和，而 e0=∑ie0,ie_0=\sum_i e_{0,i}e0​=∑i​e0,i​ 和 e1=∑ie1,ie_1=\sum_i e_{1,i}e1​=∑i​e1,i​ 是聚合的噪声项，它们为安全性提供了必要的随机化。

构建新鲜密文

组合器使用这些聚合值来构建一个刷新的密文，该密文使用重置噪声加密相同的明文。该构建遵循一种特定模式，该模式确保结果具有适当的 BFV 结构：

c1′=ac0′=[⌊tq[c0+h0]q⌉]tΔ+h1\begin{aligned} c_1' &= a\\[2pt] c_0' &= \Big[\Big\lfloor \tfrac{t}{q}\,[\,c_0+h_0\,]_q \Big\rceil\Big]_t\,\Delta + h_1 \end{aligned}c1′​c0′​​=a=[⌊qt​[c0​+h0​]q​⌉]t​Δ+h1​​

这种构造可能看起来很复杂，但它自然地遵循 BFV 解密结构和秘密共享方案的加法属性。

为什么这行得通：正确性论证

关键的见解在于理解舍入操作内部发生了什么。当我们计算 c0+h0c_0+h_0c0​+h0​ 时，我们本质上是在执行部分解密，同时保持加法结构：

c0+h0=c0+sc1−ΔM+e0=Δm+ect⏟old noise−ΔM+e0c_0+h_0 = c_0 + s c_1 - \Delta M + e_0 = \Delta m + \underbrace{e_{\text{ct}}}_{\text{old noise}} - \Delta M + e_0c0​+h0​=c0​+sc1​−ΔM+e0​=Δm+old noiseect​​​−ΔM+e0​

舍入和缩放操作提取明文信息，同时消除旧噪声：

[⌊tq[c0+h0]q⌉]t=(m−M+small)modt\Big[\Big\lfloor \tfrac{t}{q}\,[c_0+h_0]_q \Big\rceil\Big]_t = (m - M + \text{small}) \bmod t[⌊qt​[c0​+h0​]q​⌉]t​=(m−M+small)modt

其中“small”项表示 ecte_{\text{ct}}ect​ 和 e0e_0e0​ 的残余影响，这些影响通过舍入过程得到控制。将其代入我们的构造中，得到：

c0′=−sa+Δm+(e1+Δ⋅small),c1′=ac_0' = -s a + \Delta m + (e_1 + \Delta \cdot \text{small}),\qquad c_1'=ac0′​=−sa+Δm+(e1​+Δ⋅small),c1′​=a

这正是以密钥 sss 加密明文 mmm 的有效 BFV 加密结构，但现在噪声项完全来自新鲜的随机性 e1e_1e1​，而不是来自先前操作的累积噪声。

理解 Bootstraping 属性

使该协议符合 bootstraping 条件的是噪声概况的完全更新。刷新的密文具有来自总和 ∑ie1,i\sum_i e_{1,i}∑i​e1,i​ 的噪声，其方差大约为 Nσ2N\sigma^2Nσ2，以及来自舍入过程的小贡献。至关重要的是，这种新噪声与威胁要违反解码界限的旧累积噪声 ecte_{\text{ct}}ect​ 完全独立。

smudging 噪声 e0,ie_{0,i}e0,i​ 起着不同但同样重要的作用，它们确保可以在不知道明文 mmm 的情况下模拟协议 transcript，从而在整个刷新过程中保持隐私。这意味着生成的密文 ct′ct'ct′ 的行为与相同明文 mmm 的全新加密完全一样，从而可以进行进一步的同态评估，而无需首先进行 bootstraping 的噪声约束。

效率概况引人注目：输出密文 ct′=(c0′,a)ct'=(c_0',a)ct′=(c0′​,a) 加密相同的明文 mmm，噪声重置为以 Nσ2N\sigma^2Nσ2 缩放的新鲜水平。由于任何一方都无法获知 mmm 并且所有 transcripts 保持可模拟，因此保持了隐私。通信成本仅涉及一个广播轮次，其中每个参与方贡献两个环元素，从而使总体复杂度与参与方数量 NNN 成线性关系。

示例

以下示例演示了使用 Lattigo 的 BGV 方案的 3 方多方同态加密 (MHE) 工作流程。三个本地模拟的参与方运行集体公钥生成 (CKG)，每个参与方加密一个整数，一个协调器添加密文，并且结果通过公钥切换 (PCKS) 重新加密到接收方并解密，因此没有单个参与方持有联合密钥。

package main

import (
    "flag"
    "fmt"
    "log"

    "github.com/tuneinsight/lattigo/v6/core/rlwe"
    "github.com/tuneinsight/lattigo/v6/multiparty"
    "github.com/tuneinsight/lattigo/v6/ring"
    "github.com/tuneinsight/lattigo/v6/schemes/bgv"
    "github.com/tuneinsight/lattigo/v6/utils/sampling"
)

type party struct {
    sk *rlwe.SecretKey
}

func main() {
    // CLI
    a := flag.Int("a", 7, "party A integer") // party A 整数
    b := flag.Int("b", 12, "party B integer") // party B 整数
    c := flag.Int("c", 20, "party C integer") // party C 整数
    flag.Parse()

    // Parameters: small demo (N=2^12, t=65537). Very short Q-chain for adds only.
    // 参数：小型演示 (N=2^12, t=65537)。 非常短的 Q 链，仅用于添加。
    params, err := bgv.NewParametersFromLiteral(bgv.ParametersLiteral{
        LogN:             12,
        PlaintextModulus: 65537, // 明文模数
        LogQ:             []int{54, 55},
        LogP:             []int{55},
    })
    check(err)

    encoder := bgv.NewEncoder(params)

    // Receiver keypair (for output via PCKS)
    // 接收方密钥对（用于通过 PCKS 输出）
    tsk, tpk := rlwe.NewKeyGenerator(params).GenKeyPairNew()

    // 3 parties with independent secret shares
    // 具有独立秘密 shares 的 3 个参与方
    var parties = make([]party, 3)
    for i := range parties {
        parties[i].sk = rlwe.NewKeyGenerator(params).GenSecretKeyNew()
    }

    // Collective Public Key Generation (CKG)
    // 集体公钥生成 (CKG)
    crs, err := sampling.NewKeyedPRNG([]byte("mpbgv-sum-ckg-seed"))
    check(err)
    pk := execCKG(params, crs, parties)

    // Each party: encode & encrypt its scalar under collective pk
    // 每个参与方：在集体 pk 下编码并加密其标量
    ctA := encryptScalar(params, pk, encoder, *a)
    ctB := encryptScalar(params, pk, encoder, *b)
    ctC := encryptScalar(params, pk, encoder, *c)

    // Homomorphic addition
    // 同态加法
    eval := bgv.NewEvaluator(params, nil, false)
    tmp := bgv.NewCiphertext(params, 1, params.MaxLevel())
    sum := bgv.NewCiphertext(params, 1, params.MaxLevel())
    check(eval.Add(ctA, ctB, tmp))
    check(eval.Add(tmp, ctC, sum))

    // Re-encrypt result to receiver’s pk (PCKS)
    // 将结果重新加密到接收方的 pk (PCKS)
    encOut := execPCKS(params, tpk, sum, parties)

    // Receiver decrypts (Decrypt returns no value in v6)
    // 接收方解密（解密在 v6 中不返回值）
    decryptor := rlwe.NewDecryptor(params, tsk)
    pt := bgv.NewPlaintext(params, encOut.Level())
    decryptor.Decrypt(encOut, pt)

    // Decode first slot
    // 解码第一个槽
    dec := make([]uint64, params.MaxSlots())
    check(encoder.Decode(pt, dec))
    res := int(dec[0])

    fmt.Printf("Inputs: a=%d, b=%d, c=%d\n", *a, *b, *c) // 输入：a=%d, b=%d, c=%d\n
    fmt.Printf("Homomorphic sum (decrypted): %d\n", res)     // 同态和（解密）：%d\n
    if res == *a+*b+*c {
        fmt.Printf("Check: %d+%d+%d = %d ✅\n", *a, *b, *c, res) // 检查：%d+%d+%d = %d ✅\n
    } else {
        fmt.Printf("Check: %d+%d+%d != %d ❌\n", *a, *b, *c, res) // 检查：%d+%d+%d != %d ❌\n
    }
}

// encryptScalar encodes x in slot 0 and encrypts it under the collective pk.
// encryptScalar 在槽 0 中编码 x 并在集体 pk 下加密它。
func encryptScalar(params bgv.Parameters, pk *rlwe.PublicKey, enc *bgv.Encoder, x int) *rlwe.Ciphertext {
    pt := bgv.NewPlaintext(params, params.MaxLevel())
    batch := make([]uint64, params.MaxSlots())
    if x < 0 {
        t := uint64(params.PlaintextModulus())
        batch[0] = (t - uint64(-x)%t) % t
    } else {
        batch[0] = uint64(x)
    }
    check(enc.Encode(batch, pt))

    encryptor := rlwe.NewEncryptor(params, pk)
    ct := bgv.NewCiphertext(params, 1, params.MaxLevel())
    check(encryptor.Encrypt(pt, ct))
    return ct
}

// execCKG runs multiparty collective public-key generation.
// execCKG 运行多方集体公钥生成。
func execCKG(params bgv.Parameters, crs sampling.PRNG, P []party) *rlwe.PublicKey {
    ckg := multiparty.NewPublicKeyGenProtocol(params)
    crp := ckg.SampleCRP(crs)

    shares := make([]multiparty.PublicKeyGenShare, len(P))
    for i := range shares {
        shares[i] = ckg.AllocateShare()
        ckg.GenShare(P[i].sk, crp, &shares[i])
    }

    combined := ckg.AllocateShare()
    for i := range shares {
        ckg.AggregateShares(shares[i], combined, &combined)
    }

    pk := rlwe.NewPublicKey(params)
    ckg.GenPublicKey(combined, crp, pk)
    return pk
}

// execPCKS re-encrypts ctIn to tpk using the PublicKeySwitch protocol.
// execPCKS 使用 PublicKeySwitch 协议将 ctIn 重新加密到 tpk。
func execPCKS(params bgv.Parameters, tpk *rlwe.PublicKey, ctIn *rlwe.Ciphertext, P []party) *rlwe.Ciphertext {
    pcks, err := multiparty.NewPublicKeySwitchProtocol(
        params,
        ring.DiscreteGaussian{Sigma: 1 << 30, Bound: 6 * (1 << 30)},
    )
    check(err)

    shares := make([]multiparty.PublicKeySwitchShare, len(P))
    for i := range shares {
        shares[i] = pcks.AllocateShare(params.MaxLevel())
        pcks.GenShare(P[i].sk, tpk, ctIn, &shares[i])
    }

    combined := pcks.AllocateShare(params.MaxLevel())
    for i := range shares {
        check(pcks.AggregateShares(shares[i], combined, &combined))
    }

    out := bgv.NewCiphertext(params, 1, params.MaxLevel())
    pcks.KeySwitch(ctIn, combined, out)
    return out
}

func check(err error) {
    if err != nil {
        log.Fatal(err)
    }
}

结论

多方同态加密从根本上通过从“共享数据”转向“共享解密能力”来重塑协作私有计算。这种范式转变将成本概况从每乘法层需要一个交互轮次转变为每个结果仅需要一个短轮次，而通信规模与参与方数量成线性关系。

MBFV 工具包通过精心设计的协议使这成为现实，这些协议在保持 BFV 级别安全性的同时支持分布式操作。集体密钥生成会生成标准外观的公钥，而无需组装密钥，密钥切换协议（CKS 和 PCKS）仅提供具有公共 transcripts 的高效输出传递。

也许最重要的是，这种方法支持真正的异步计算，即繁重的评估在线下进行，而无需所有参与方同时在线。唯一的同步点发生在输出时，与传统的 MPC 协议相比，大大提高了实际可部署性，传统的 MPC 协议在掉队者处停滞不前，并且难以处理网络分区。

致谢

这篇文章的灵感来自 Victor Mouchet、Juan Ramón Troncoso-Pastoriza、Jean-Philippe Bossuat 和 Jean-Pierre Hubaux 的“基于环-错误学习的多方同态加密”。 非常感谢 Lattigo 的维护者，他们的实现有助于形成对实际参数化和成本的直觉。

• 原文链接： hexens.io/blog/mhe-from-...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～