恶意安全三方计算：基于批量验证与GPU加速的高效隐私机器学习推理

1. 项目概述：当恶意安全遇上高效计算

在隐私保护机器学习（PPML）的实际落地过程中，我们常常面临一个核心矛盾：如何在确保安全性的前提下，实现接近明文计算的性能？传统的半诚实安全模型假设参与者会“诚实地”遵循协议，但这在现实商业或医疗合作中往往过于理想。一旦有参与者心怀不轨，试图通过偏离协议来窃取他人隐私或破坏计算结果，整个系统的安全性便荡然无存。因此，恶意安全模型应运而生，它要求协议即使在面对主动作恶的参与者时，也能保证计算的正确性和输入的隐私性。

然而，恶意安全通常意味着巨大的性能开销。额外的零知识证明、一致性检查等机制，使得恶意安全协议的计算和通信成本远高于半诚实协议。本文要探讨的，正是一个试图打破这一僵局的方案：一个面向三方计算（3PC）场景的恶意安全协议，它通过一系列精巧的设计，特别是批量验证技术，在保证恶意安全的同时，将乘法等核心操作的通信开销大幅降低，并利用GPU加速实现了高性能的隐私保护机器学习推理。

简单来说，这个框架的目标是：让三个互不信任的参与方，能够像信任一个可信第三方那样，安全地协同完成一个机器学习模型的推理（或训练），且任何一方都无法独自窥探或篡改他人的输入数据与中间结果。它不是为了解决所有MPC问题，而是精准地瞄准了“诚实多数”（3方中至多1方恶意）这一经典且实用的场景，并在其中寻求性能的极致优化。

2. 核心思路：从“逐个检查”到“批量打包验证”

要理解这个协议为何高效，关键在于抓住其核心验证逻辑的转变。在早期的恶意安全MPC协议中，验证每一个乘法操作的正确性都需要独立的、昂贵的密码学操作（如承诺、零知识证明），这导致了通信轮次和带宽的线性增长。

2.1 传统验证的瓶颈

想象一下三个厨师（P0, P1, P2）合作做一道秘制酱料，每人持有一部分独家香料（秘密份额）。他们需要将多种香料混合（乘法运算）。在半诚实设定下，大家按菜谱（协议）操作即可。但在恶意设定下，我们需要防止某个厨师偷偷加入劣质香料或偷看别人的配方。传统方法好比每混合两种香料，就请一个中立裁判来检查一次混合过程是否合规，这无疑会让做菜速度慢得惊人。

2.2 批量验证的灵感

本协议采用的思路是“延迟审计，批量处理”。它允许厨师们先按照流程快速完成所有香料的混合（在线计算阶段），生成大量的中间混合品（乘法三元组或内积结果）。最后，在“上菜”之前，通过一个高效的批量验证流程，一次性检查所有混合操作的正确性。

其数学基础是将多个在整数环Z_{2^ℓ}上的验证问题，“打包”转换到多项式环Z_{2^ℓ}[x]/f(x)上进行。这里，ℓ是比特长度（如64），f(x)是一个d次不可约多项式。协议的核心验证协议Π_{MultVerify}和Π_{InnerVerify}正是基于此。

为什么选择多项式环？在多项式环上，我们可以利用其代数结构。多个独立的数值验证问题，可以通过给每个问题分配一个多项式上的不同“评估点”来编码。然后，验证一个随机线性组合的结果是否正确，就能以极高的概率推断出所有原始问题是否正确。这类似于抽查质检：不是检查每一件产品，而是随机抽取几件混合后的样品进行检测。如果样品合格，那么整批产品合格的概率就非常高。协议中通过多轮（R轮）的维度约减（Π_{Reduce}）操作，将需要验证的向量对数量不断折半，最终浓缩到只需验证一对，极大地减少了最终的验证开销。

一个简单的类比：假设要验证100个等式a_i * b_i = c_i是否都成立。传统方法需验证100次。批量验证则生成一个随机向量r，计算A = Σ(r_i * a_i),B = Σ(r_i * b_i),C = Σ(r_i * c_i)，然后只需验证一次A * B = C是否成立。如果原始等式中有一个不成立，那么最终等式极大概率也不成立。本协议的思路与此类似，但更复杂、更严谨，且工作在秘密分享的背景下。

2.3 三方复制秘密分享的基础

该协议建立在“三方复制秘密分享”之上。对于一个秘密值x，其分享⟨x⟩由三个份额组成：(m, [x]_1, [x]_2)。其中：

• m由 P0 持有，称为“MAC值”，用于后续验证。
• [x]_1由 P1 持有。
• [x]_2由 P2 持有。 并且满足关系：x = m - [x]_1 - [x]_2（在相应的环上）。任何一方都无法单独恢复x，需要至少两方合作。

这种分享方式天然支持线性运算（加法和常数乘法）的本地计算，无需通信。挑战在于非线性的乘法运算，这正是协议需要重点保护和验证的部分。

3. 恶意安全乘法协议详解

乘法是机器学习计算图（尤其是神经网络）中最核心、最耗时的操作之一。矩阵乘、卷积最终都归结为大量的乘加运算。因此，一个高效的恶意安全乘法协议是整个框架的基石。

3.1 协议流程与角色分工

协议Π_{Mult}的核心目标是让三方安全地计算⟨z⟩ = ⟨x⟩ * ⟨y⟩，并确保结果是正确的。整个过程分为预处理阶段和在线阶段，这是MPC的典型模式，旨在将耗时的密码学操作前置，以优化在线计算速度。

预处理阶段（离线）： 这个阶段与输入x, y无关，目的是预先生成一个“乘法三元组”(⟨a⟩, ⟨b⟩, ⟨c⟩)，其中c = a * b。这个三元组是随机的，并且其正确性将通过后续的批量验证来保证。

1. 随机数生成：P0和P1共同生成随机数a1, b1；P0和P2共同生成a2, b2；P1和P2共同生成a3, b3。通过这种方式，任何单一参与方都不知道完整的a或b（a = a1 + a2 + a3,b同理）。
2. 本地构造分享：各方利用上述随机数，本地构造出⟨a⟩和⟨b⟩的复制秘密分享。例如，⟨a1⟩被构造为(0, a1, 0)，意味着P0持有MAC值0，P1持有份额a1，P2持有份额0。
3. 计算c的分享：这是关键步骤。各方需要计算⟨c⟩ = ⟨a⟩ * ⟨b⟩的分享。由于a和b的完整值无人知晓，直接计算不可行。协议利用Beaver乘法技巧：x*y = (x-a+a)*(y-b+b) = ... = (x-a)(y-b) + (x-a)b + a(y-b) + ab。其中(x-a)和(y-b)可以在线阶段通过重构公开值（称为ε和δ）得到，而a, b, ab就是预处理生成的三元组。 因此，在预处理阶段，各方需要通过一次安全的乘法协议，计算出⟨c⟩的初始分享。这个过程本身可能也需要验证，它被融入到后续的批量验证中。

在线阶段： 当实际的输入⟨x⟩和⟨y⟩就绪后：

1. 掩码打开：各方本地计算⟨ε⟩ = ⟨x⟩ - ⟨a⟩和⟨δ⟩ = ⟨y⟩ - ⟨b⟩，然后协作重构出公开值ε和δ。由于a, b是随机的，ε和δ不会泄露x和y的信息。
2. 结果计算：各方本地计算⟨z⟩ = ⟨c⟩ + ε * ⟨b⟩ + δ * ⟨a⟩ + ε * δ。根据Beaver公式，这正好等于⟨x * y⟩。
3. （关键）延迟验证：此时并不立即验证⟨z⟩的正确性。相反，这个乘法操作产生的“需求”——即需要验证(⟨a⟩, ⟨b⟩, ⟨c⟩)这个三元组是否正确，以及在线阶段的计算是否被正确执行——被记录下来，放入一个待验证的批次G中。

批量验证阶段（后处理）： 在所有乘法操作（可能成千上万次）的在线阶段都完成后，系统调用Π_{MultVerify}协议，对整个批次G中的所有三元组进行一次性的、高效的验证。

1. 问题转换：如图7所示，协议将|G|个在环Z_{2^ℓ}上的三元组验证问题，通过引入随机线性组合，转换到多项式环Z_{2^ℓ}[x]/f(x)上，变成一个对单个“聚合”三元组的验证问题。
2. 维度约减：通过R轮Π_{Reduce}操作，将需要验证的向量对数量指数级减少（每轮减半）。
3. 最终验证：对最后剩下的一对向量，调用一个轻量级的验证子协议Π_{InnerVerify}进行检查。如果通过，则以极高的概率表明整个批次G中的所有乘法都是正确的；否则，中止协议。

3.2 通信开销分析

这是该协议性能优势的量化体现。对于一个乘法操作：

• 预处理阶段：平均摊销通信量为ℓ比特。这主要来自于生成随机数和对和交互。
• 在线阶段：通信量为2ℓ比特。这主要用于重构两个公开值ε和δ。
• 验证阶段：这是额外的开销，但被所有乘法操作分摊。其通信量为O(R * ℓ * d)，其中R = log|G|，d是多项式次数。当批量大小|G|很大时，R增长缓慢，因此每个乘法摊销到的验证开销变得很小。

实操心得：批量大小的权衡批量大小|G|是性能调优的关键参数。|G|越大，摊销效果越好，每个乘法的验证开销越低。但是，|G|越大，意味着在线阶段需要缓存更多的中间状态，内存开销增加，并且验证阶段的延迟（需要等到所有在线计算完成）也会变长。在实践中，需要根据具体任务的计算图规模和可用内存来设定一个合适的批次大小。对于神经网络推理这种层数固定、操作数可预估的任务，可以将整个前向传播的所有乘法作为一个批次，以达到最优的摊销效果。

4. 从乘法到机器学习框架：关键组件构建

仅有高效的乘法还不够，一个完整的PPML框架需要处理线性操作（矩阵乘、卷积）、非线性激活函数（ReLU, Sigmoid）以及定点数运算中的精度处理（截断）。

4.1 高效内积与卷积

在机器学习中，向量内积、矩阵乘法和卷积占据了绝大部分计算量。本协议将内积视为一系列乘法的扩展，并设计了对应的恶意安全内积协议Π_{Inner}。

内积协议Π_{Inner}： 计算⟨z⟩ = Σ_{i=1}^n ⟨x_i⟩ * ⟨y_i⟩。其半诚实版本可以看作是对一个2次n元多项式的求值，预处理仅需ℓ比特通信，在线阶段需2ℓ比特。为了升级到恶意安全，同样采用了图7所示的批量验证协议Π_{InnerVerify}，其原理与乘法批量验证完全相同。对于维度为n的内积，其通信开销与n次独立的乘法相近，但通过批量验证，其验证开销被所有内积操作共同分摊。

卷积与矩阵乘法的实现： 在框架中，一个m维输出的卷积或矩阵乘法，被视作m个独立的内积。因此，只需调用m次Π_{Inner}协议即可。这种设计保持了模块的简洁性，并且由于内积协议本身的高效和可批量验证性，使得这些线性层也能享受到恶意安全下的高性能。

4.2 恶意安全截断协议

机器学习通常使用定点数来模拟实数。两个k比特小数精度的定点数相乘后，小数部分会扩展为2k比特，需要进行截断以保持精度不变。截断操作本身不是线性的，在秘密分享下无法直接进行。

协议Π_{Trunc}的设计： 如图8所示，该协议的核心思想是“预计算截断对”。在预处理阶段，各方合作生成一个随机数r及其截断后的值r' = truncate(r, t)（t为截断位数）的秘密分享⟨r⟩和⟨r'⟩，并且保证r'确实是r的正确截断。

1. 随机比特生成：P0和P1生成随机比特列表{b1_j}，P0和P2生成{b2_j}。
2. 构造r和r'：计算r = Σ 2^j * (b1_j ⊕ b2_j)，r' = truncate(r, t)。通过巧妙的构造，可以在秘密分享的形式下，利用Π_{Inner}协议计算出⟨r⟩和⟨r'⟩。
3. 在线阶段：对于输入⟨x⟩，各方公开ε = x - r。然后，本地计算⟨y⟩ = ⟨r'⟩ + ε。由于ε是公开的，且r'是r的截断，因此y就是x的截断结果。

优势：该协议最大的亮点在于，在线阶段无需任何通信。所有复杂的密码学操作都在预处理阶段完成，在线阶段仅需一次本地加法和一次公开重构，速度极快。这比一些需要在线交互的截断方案（如SWIFT的独立截断协议）有显著优势。

注意事项：概率性误差需要明确的是，这是一种概率性截断协议。它引入了一个最低有效位的误差，误差概率与数据的有效范围有关。在大多数机器学习应用中，这种极小的、有界的误差是可以接受的，因为它对模型精度的影响微乎其微，远低于模型本身的噪声和量化误差。但在对数值精度要求极其严苛的场景下，需要评估此误差的影响。

4.3 非线性函数评估：edaBits的运用

ReLU、Sigmoid等非线性函数是神经网络的灵魂，但其计算在算术秘密分享上非常低效。标准的做法是将其转换到布尔电路（基于XOR和AND）上进行计算，这需要daBits或edaBits。

daBits与edaBits：

• daBit：一个数据对(⟨r⟩_ℓ, ⟨r⟩_1)，其中r ∈ {0,1}，⟨r⟩_ℓ是r在较大环Z_{2^ℓ}上的算术分享，⟨r⟩_1是r在布尔环Z_2上的布尔分享。两者表示的是同一个比特。
• edaBit：daBit的多比特扩展，{⟨r⟩_ℓ, {⟨r[i]⟩_1}_{i∈[ℓ]}}，其中r是ℓ比特的整数，{⟨r[i]⟩_1}是r的每个比特的布尔分享。

如何使用edaBit计算非线性函数： 假设我们要计算一个非线性函数f(x)，其中x以算术分享⟨x⟩_ℓ形式存在。

1. 比特提取：利用一个预生成的edaBit{⟨r⟩_ℓ, {⟨r[i]⟩_1}}。
   • 各方本地计算⟨Δ⟩_ℓ = ⟨x⟩_ℓ - ⟨r⟩_ℓ。
   • 协作公开Δ = x - r。由于r是随机的，Δ不泄露x。
   • 将公开的Δ的每个比特Δ[i]转化为布尔分享⟨Δ[i]⟩_1（这可以本地完成，因为Δ是公开的）。
   • 现在，各方拥有了r的每个比特的布尔分享⟨r[i]⟩_1，以及Δ的每个比特的布尔分享⟨Δ[i]⟩_1。
   • 通过一个全加器（Full Adder）布尔电路，计算⟨x[i]⟩_1 = ⟨r[i]⟩_1 ⊕ ⟨Δ[i]⟩_1（考虑进位链）。最终得到x的每个比特的布尔分享{⟨x[i]⟩_1}。
2. 布尔电路评估：在得到x的比特分享后，就可以用高效的布尔电路MPC协议（如Garbled Circuit或GMW）来计算f(x)的布尔分享。因为f(x)通常可以表示为比特的逻辑运算。
3. 分享转换（可选）：如果需要将结果f(x)的布尔分享⟨y⟩_1转换回算术分享⟨y⟩_ℓ，可以借助另一个daBit，通过公式⟨y⟩_ℓ = Δ + ⟨r⟩_ℓ - 2Δ·⟨r⟩_ℓ实现，其中Δ = y ⊕ r被公开。

edaBit的生成： 如图9所示，生成edaBit本身也需要安全的乘法操作。协议通过两轮乘法（或一轮内积）来构造。关键在于，生成edaBit的乘法操作，同样可以被纳入到前述的批量验证框架中，从而保证了整个流程的端到端恶意安全性。

5. 实战：GPU加速与性能调优

理论设计再精妙，最终也需要通过实践来检验。该框架的一个突出特点是其面向GPU平台的高效实现，基于修改版的Piranha框架。

5.1 实验环境与对比基准

• 硬件：8核CPU，32GB内存，4张Nvidia 2080 Ti GPU。
• 网络：模拟了局域网（LAN）、城域网（MAN）和广域网（WAN）三种延迟与带宽条件。
• 对比协议：选择了该领域公认的先进方案进行对比，包括半诚实/恶意安全的ABY3、BLAZE以及恶意安全的SWIFT协议。
• 核心参数：环大小ℓ=64（对应64位整数），多项式次数d=64，定点数小数部分精度为16比特。

5.2 核心参数R的优化选择

批量验证中的维度约减轮数R是一个关键的性能权衡参数。R越大，最终需要验证的数据维度越小，验证阶段的通信量越低。但R每增加1，就增加一轮通信延迟。

实测发现：

• 在数据量较小（如|G|=2^18）时，R不宜过大，否则额外的通信轮次带来的延迟会抵消通信量减少的收益。在MAN环境下，R=7左右是最优的。
• 在数据量巨大（如|G|=2^20）且网络带宽受限的WAN环境下，应选择更大的R（如9或10），因为此时带宽是主要瓶颈，减少通信量的收益远大于增加一轮延迟的成本。
• 调优建议：在实际部署中，可以根据预估的批量大小和网络状况（RTT、带宽），通过简单的基准测试来确定最优的R值。可以预先制作一个查找表。

5.3 通信与性能对比结果

通信开销： 图10的结果非常直观。对于单次乘法，当批量规模较小时，本协议的验证开销占比相对明显，总通信量可能略高于SWIFT。但是，随着批量规模|G|的增长，其摊销优势尽显。

• 在大规模输入下，本协议的乘法总通信量约为SWIFT的50%，ABY3的15%。
• 对于带截断的1024维内积，通信量仅为SWIFT的50%，ABY3的0.02%。这凸显了批量验证对复合操作（内积包含大量乘法）的巨大优化效果。

运行时间： 图11和图12展示了运行时间的对比。

• 小数据量：由于额外的验证轮次，本协议在线时间可能略慢于SWIFT和ABY3。
• 大数据量/高深度：在数据饱和（大规模矩阵）或电路深度较大（如32层、128层）时，本协议凭借更优的通信复杂性和对GPU并行计算的更好利用，实现了高达2倍的吞吐量提升。特别是在深度较大的电路中，本协议和ABY3的轮次优势使得它们受网络延迟的影响小于SWIFT。

5.4 神经网络推理端到端评估

协议在三个经典CNN模型上进行了测试：一个浅层网络（S-NN）、LeNet和VGG-16。表II和图14揭示了在真实ML任务中的性能表现。

关键发现：

1. 验证开销占比：对于小模型（S-NN），验证阶段的时间占总运行时间的比例相当可观。这是因为计算本身很快，而验证的固定开销（如通信轮次）显得突出。
2. 计算与通信瓶颈转移：随着模型变大变复杂（LeNet -> VGG）：
   • 在线执行阶段：通信延迟成为绝对主导。图14清晰显示，在LeNet和VGG的在线阶段，通信耗时远大于GPU计算耗时。优化网络带宽和减少通信轮次是提升性能的关键。
   • 验证阶段：计算延迟成为主导。验证阶段的核心是大量的本地多项式运算和少量的通信，因此GPU的计算能力成为瓶颈。
3. 可行性：即使对于VGG-16这样的中等规模模型，在LAN环境下也能在秒级（约1.3秒在线计算+0.26秒验证）完成一次恶意安全的隐私保护推理，这证明了该框架的实用性。

实操心得：网络环境决定架构这些数据给我们的启示是，在设计部署方案时，必须首要考虑网络条件。

• 跨数据中心（WAN）：通信是主要瓶颈。应尽可能增大批量大小|G|以减少摊销通信量，并选择最优的R值。可能需要对计算任务进行聚合，减少频繁的交互。
• 内部集群（LAN/MAN）：随着模型复杂度和计算量上升，GPU计算和验证阶段的计算也会成为瓶颈。此时，拥有强大的GPU算力同样重要。可以考虑采用更高带宽的InfiniBand网络来缓解通信压力。

6. 常见问题与深度思考

在实际部署和复现此类协议时，会遇到一些典型问题。以下是我基于经验的一些总结。

6.1 安全性假设与威胁模型

Q：这个协议能防什么样的攻击者？A：该协议在“诚实多数”模型下达到恶意安全。具体来说，在三个参与方中，最多允许一个被敌手完全控制（恶意腐败），其余两方必须是诚实的。敌手可以任意偏离协议（如发送错误消息、中止协议）。协议保证：1)隐私性：恶意方无法学到诚实方的任何私有输入信息；2)正确性：除非协议中止，否则输出的结果一定是按照预定函数正确计算得出的。

Q：如果两个参与方合谋呢？A：该协议不抵抗两方合谋攻击。在三方复制秘密分享中，任何两方合谋就能恢复出完整的秘密。这是“诚实多数”模型的固有局限。如果需要抵抗任意两方合谋，需要采用更复杂的秘密分享方案（如Shamir秘密分享）和协议，这通常会带来更高的开销。

6.2 精度与误差处理

Q：定点数截断带来的概率性误差会影响模型精度吗？A：在绝大多数计算机视觉和自然语言处理任务中，影响可以忽略不计。现代神经网络本身对噪声和数值扰动具有一定的鲁棒性。概率性截断引入的误差是均匀分布的、有界的（通常是最低有效位级别的），其影响远小于模型训练中的随机梯度下降噪声或模型量化带来的误差。在部署前，建议在公开数据集上对比明文浮点模型与使用该协议（含截断）的定点加密模型的精度，以确认可接受性。

Q：如何选择定点数的小数位精度k？A：这是一个经验性参数。通常，k=16或k=20对于许多模型已经足够。太小的k会导致精度损失和模型失效；太大的k会增加通信量（因为环大小ℓ固定，整数部分比特变少）和溢出风险。一个实用的方法是：在明文环境下，用定点数算术模拟推理，逐步降低k，直到模型精度开始显著下降，然后选择那个临界值作为安全值。

6.3 工程实现挑战

Q：如何高效管理预计算材料（三元组、截断对、edaBits）？A：这是工程上的核心挑战。预计算材料与输入数据无关，可以提前大量生成并存储。建议：

1. 流水线化：将预计算作为一个常驻后台服务，持续生成材料并存入缓存队列。
2. 按需生成：根据任务的计算图，精确估算所需各类材料的数量和规格，避免生成过多或类型不匹配的材料。
3. 内存与磁盘交换：对于超大规模任务，预计算材料可能无法全部放入内存。需要设计高效的缓存机制，将近期要用的材料放在内存，其余的序列化到磁盘。
4. 分布式生成：预计算本身也可以并行化。可以部署多个预计算节点，协同生成材料，提升整体吞吐量。

Q：GPU实现有哪些需要注意的坑？A：

1. 内核函数设计：MPC中的许多操作（如本地份额相加、与公开常数相乘）是高度并行的简单操作。应设计高效的CUDA内核，避免过多的核函数启动开销和全局内存访问。
2. 数据传输：GPU与主机内存之间、以及网络之间的数据传输是瓶颈。应尽可能让数据留在GPU显存中，减少PCIe拷贝。使用GPU Direct RDMA技术（如果网络硬件支持）可以让GPU显存直接与网卡通信，大幅提升效率。
3. 同步点：协议中的通信轮次是天然的同步点。需要精细安排计算和通��的重叠（计算-通信重叠），以隐藏通信延迟。例如，在等待上一轮网络消息的同时，可以计算下一层中不依赖于该消息的部分。

6.4 协议扩展与局限性

Q：这个协议能用于训练吗？A：本文主要聚焦于推理。理论上，该框架也可用于训练，因为训练的核心操作（前向传播、反向传播、梯度更新）同样由线性操作和非线性激活组成。然而，训练涉及迭代和大量的中间状态，会带来新的挑战：

1. 状态管理：模型的权重和优化器状态（如动量）需要以秘密分享形式持续维护，增加了复杂性。
2. 动态计算图：某些训练操作（如Dropout）会引入随机性，需要协调各方的随机数生成器。
3. 性能要求：训练的计算量远大于推理，对通信和计算效率的要求更高。虽然批量验证的优势依然存在，但需要更极致的优化。 目前已有一些工作将类似思想扩展到训练，但通常需要更多的工程努力。

Q：能否支持多于三方的场景？A：该协议的核心——基于多项式环的批量验证和复制秘密分享——可以推广到n方、诚实多数（即恶意方少于n/2）的场景。但具体细节需要调整，例如秘密分享方案可能变为n选t的门限分享，批量验证的公式也需要相应修改。通信复杂度会随着参与方数量增加而增长，但批量验证带来的摊销优势依然有效。