《The Communication-Friendly Privacy-PreservingMachine Learning against Malicious Adversaries》

m0_65356559

344人浏览 · 2026-06-29 14:54:08

m0_65356559 · 2026-06-29 14:54:08 发布

一、研究背景

目前PPML主要依赖安全多方计算（MPC）技术，使多个参与方能够在不泄露各自数据的情况下共同完成机器学习计算。然而，目前已有的大多数MPC方案存在两个问题：

1. 大部分协议只考虑半诚实（Semi-honest）攻击模型

默认参与者都会遵守协议
实际部署中服务器可能故意作弊，因此需要支持恶意安全（Malicious Security）

2 恶意安全协议通信开销过大

在PPML中，大部分计算发生在环 $\mathbb{Z}_2{^{l }}$ 上
环上的恶意安全协议比有限域上的协议复杂得多
通信成本甚至超过计算成本，成为部署PPML最大的瓶颈

本文的核心目标就是设计一个通信高效、且能抵御恶意攻击的PPML框架，使其性能接近半诚实（Semi-honest）场景下的协议。

PPML的定义与价值：隐私保护机器学习（PPML）是一种创新技术，能够在保障敏感信息安全的前提下实现数据挖掘和机器学习，使组织在不泄露隐私的情况下利用数据价值

二、研究难点

1. 环上的恶意安全验证困难：绝大多数高效的恶意安全MPC技术（如基于拉格朗日插值的批验证）都构建在域（Field）（如素数域 ℤₚ）上。域中每个非零元素都有乘法逆元（即可以做除法），而环 $\mathbb{Z}_2{^{l }}$ 中则存在大量不可逆元素，这使得域上的技术不能直接搬到环。直接迁移会让通信量增加约2倍。

2. 乘法验证无法批量压缩：为确保恶意安全，必须在计算后对结果进行验证。最直接的方式是对每个乘法门（Multiplication Gate）逐一验证，但这会产生与计算电路规模成正比的通信量，代价极高。因此必须设计：批量验证（Batch Verification）才能真正用于PPML。

3. 混合电路与非线型函数的安全高效实现难：神经网络不仅包含线性运算（如矩阵乘法），还包含大量非线性函数（如ReLU、比较、截断）。这些非线性操作在二进制电路上更高效，而线性操作在算术电路上更优。如何在恶意安全模型下，安全、高效地实现算术域与二进制域之间的转换，并正确执行截断操作以避免数值溢出，是构建完整PPML框架的又一难题。

三、关键技术

技术一：基于扩展环的恶意安全乘法验证技术

解决的问题：有限环 $\mathbb{Z}_2{^{l }}$ 中乘法不可逆，导致误差隐藏概率高；现有协议批量验证通信量随乘法门数量线性增长。
解决方案：将原始环 $\mathbb{Z}_2{^{l }}$ 扩展为多项式环 $\mathbb{Z}_{2^l}[x]/f(x)$ ，其中f(x)是定义在 $\mathbb{Z}_2{^{l }}$ 上的d次不可约多项式

扩展环方案流程：

①乘法三元组压缩：

将N个乘法验证 $z^{\left ( i\right )}=x^{\left ( i\right )}\cdot y^{\left ( i\right )}$ “打包”成一个单一的内积验证 $z=\sum_{i}^{N-1} x^{'\left ( i \right )}y^{\left ( i \right )}$ 。

其中，

$z=r^{0}\cdot z^{\left ( 0 \right )}+r^{1}\cdot z^{\left ( 1 \right )}+r^{2}\cdot z^{\left ( 2 \right )}+...$

$x^{'\left ( i \right )}=r^{i}\cdot x^{(i)}$

这一步在本地计算使恶意方无法让两个不同位置的错误相互抵消。

这样，原本需要检查 N 个等式，现在只需要检查 1 个等式，通信量从 O(N) 降为 O(log N)。

并且引入r的幂次权重，如果恶意方在多个门上引入错误 $e^{(0)},e^{(1)},e^{(2)}...$ ,那么总错误为 $r^{0}e^{0}+r^{1}e^{1}+r^{2}e^{2}+...=E(r)$

其中 $E(X)=e^{0}+e^{1}X+e^{2}X+...$ 是一个多项式，要让总错误为0，就需要 E(r)=0，即 r是多项式 E(X) 的根。而 r是从整个环中均匀随机选取的，所以 r 恰好是某个根的概率小到可以忽略。

②拉格朗日插值降维：

把相邻两项配对，用直线表示每对的两个数；用三个冗余点（0、1、2）锁定总曲线的形状；随机选一个点 ζ作为新的验证位置；每做一次，验证项数减半。

压缩阶段把 N 个乘法门变成了 1 个 N 维内积等式，但这个内积仍然有 N 项。如果直接验证这个 N 维内积，通信量还是 O(N)。降维的目的就是把 N 项逐轮减半，重复 R 次后，维度降到 $N/2^R$ ，从而把通信量降到 O(log N)。

③内积验证：

现在只剩下一个维度很小（记为 $M=N/2^R$ ）的内积等式： $z=\sum_{i=0}^{M-1} x^{\left ( i \right )}y^{\left ( i \right )}$

各方共同生成随机多项式 $\alpha \in \mathbb{Z}_{2^l}[x]/f(x)$

计算加权内积 $\Delta =\sum_{i=0}^{M-1} (\alpha \cdot x^{\left ( i \right )})\cdot y^{\left ( i \right )}-\alpha \cdot z$

若Δ=0，则以高概率确认内积正确（基于Schwartz-Zippel引理），即z 是等于所有 xiyi之和

Schwartz-Zippel引理：非零误差多项式在随机挑战下的根概率不超过 $\frac{d}{2^l}$ （d=64,l=64时概率约 $10^{-17}$ $\approx$ 0)，确保验证可靠性。

技术二：支持混合电路与非线性函数的统一框架

解决的问题：算术域擅长加法和乘法，而二进制域更擅长比较等非线性操作。许多隐私保护机器学习应用两者都需要，而MPC 中算术和二进制两种计算域之间转换效率低下；
解决方案：daBits（双认证比特）是一种同时在算术环 ℤ₂^ℓ 和二进制域 ℤ₂ 上被共享的随机比特。本文采用daBits 协议，它通过在预处理阶段提前生成并验证好“双语随机数”，可以高效、安全地实现算术域与二进制域之间的转换。

假设把算术秘密 [x]转换成二进制秘密 [x]。用 daBits 的方法：

1.预处理阶段已经准备好了很多 daBit，每个 daBit 是一个随机比特 b，同时有 [b]算术和 [b]二进制。

2.在线阶段，你需要转换 x 时，拿一个 daBit b 出来。

3.在算术语言里，公开计算 [d]算术=[x]算术−[b]算术，然后把 d 重构出来（d 是公开的）。

4.因为 d是公开的，在二进制语言里可以公开地计算 [x]二进制=d+[b]二进制（异或操作）。

四、主要结论与贡献

本文的主要贡献可归纳为：

协议性能领先：提出了一种新的恶意安全3PC乘法协议。与最先进的同类协议（如SWIFT）相比：
- 在线阶段通信量减少 33%，离线阶段减少 67%。
- 在批量处理大尺寸数据时，整体吞吐量是SWIFT和ABY3的 2倍。
- 总通信量仅为SWIFT的约 50%，ABY3的约 15%。
验证开销可控：通过批验证机制，验证阶段的通信开销与电路规模呈对数关系。实验表明，对于复杂模型（如VGG），验证阶段产生的通信和运行时间远小于在线执行阶段，说明引入恶意安全所带来的额外代价已降至可接受范围。
框架实用性强：成功构建了一个端到端的、针对恶意敌手的隐私保护机器学习框架。该框架成功运行了VGG、ResNet等现代CNN模型，并证明其能在秒级时间内完成复杂模型的推理，具备了实际部署的潜力。

五、基础知识

1. 逆元：

在数学中，一个数字 a 的“乘法逆元”指的是另一个数字 b，使得它们相乘的结果等于乘法单位元（也就是数字 1）。

用公式表示就是：a × b ≡ 1 (mod N) 即（a*b）mod N=1

如果这样的 b 存在，我们就说 a 是可逆的，b 是 a 的逆元。

在环 $\mathbb{Z}_{N}$ 中，一个数字 a 存在乘法逆元的充要条件是：a 和模数 N 互质，即它们的最大公约数 (gcd) 等于 1。

让我们把模数换成一般的 $\mathbb{Z}_2{^{l }}$ （即模 N = $2^{l}$ ）：

数字 2：gcd(2, $2^{l}$ ) = 2，不等于1。所以2没有逆元。
数字 4：gcd(4, $2^{l}$ ) = 4（假设 ℓ ≥ 2），不等于1。所以4没有逆元。
数字 6：gcd(6, $2^{l}$ ) = 2，不等于1。所以6没有逆元。

核心结论： 只要是偶数，它就和模数 $2^{l}$ 有公因数 2（即不互质），因此偶数在环 $\mathbb{Z}_2{^{l }}$ 中没有乘法逆元。

2. 环和域的概念

①环：

环（Ring）是一个代数结构，可理解为一组允许做加法、减法和乘法的数字集合，并且这些运算遵循一些常规的规则（比如结合律、分配律）。
最直观的例子：整数集合 ℤ
- 对任意两个整数，你都可以进行加、减、乘，结果仍然是整数。
本文中的环： $\mathbb{Z}_2{^{l }}$
- 这表示的是 模 2^ℓ 的整数环。ℓ 是比特长度（如64）。
- 它的元素是 0, 1, 2, ..., 2^ℓ - 1。
- 所有运算结果都对 2^ℓ 取模，以确保结果仍在集合内。
- 计算机中的数据就是二进制表示的，用 $\mathbb{Z}_2{^{l }}$ 来编码数据（比如定点数）可以完美契合计算机的算术逻辑，实现高效计算。

②域：

在环的所有规则之上，额外增加了一条最重要的规则：除了 0 以外，每一个非零元素都必须能做除法（即存在乘法逆元）
以模7 为例（记作 ℤ₇），找数字2的逆元：找一个数 b，使得 2 × b ≡ 1 (mod 7)

b=4时，（2 × 4 = 8）mod 7 =1 所以，数字 2 在域 ℤ₇ 中有逆元，逆元是 4

③环和域的区别：

环（Ring）：不要求每个元素都能做除法。例如，在 ℤ₂^64 中，偶数 2 就没有乘法逆元（因为没有任何整数乘以2 再模2^64 等于1）。
域（Field）：在环的加、减、乘基础上，还要求每个非零元素都有乘法逆元（即可以做除法）。

3. 两种核心秘密共享方案（用于3PC场景）

① [·]ₗ-sharing（加法共享）

定义：将秘密 $x \in \mathbb{Z}_{2^L}$ （如64位整数）拆分为两个份额 $[x]_1$ 和 $[x]_2$ ，满足 $x = [x]_1 + [x]_2 \mod 2^L$
持有方式：参与方 $P_1$ 持有 $[x]_1$ ， $P_2$ 持有 $[x]_2$ ， $P_0$ 不直接持有份额但协调生成过程。
线性同态性：支持加法和常数乘法，例如：
- $[x] + [y] = ([x]_1 + [y]_1, [x]_2 + [y]_2)$
- $c \cdot [x] = (c \cdot [x]_1, c \cdot [x]_2)$ （c 为公开常数）。

示例：若 x = 5， $P_1$ 持 $[x]_1=3$ ， $P_2$ 持 $[x]_2 = 2$ ，则 $3 + 2 = 5 \mod 2^L$

② 〈·〉ₗ-sharing（带随机值的共享）

定义：引入随机值 $r_{x}$ ，将 x表示为 $m_x = x + r_x$ （ $m_x$ 为公开值），同时对 $r_{x}$ 进行 [·]ₗ-sharing，即 $[r_x]_1 + [r_x]_2 = r_x$
持有方式（RSS）：
- $P_0$ 持有 $[r_x]_1$ 和 $[r_x]_2$ （随机值的份额）；
- $P_1$ 持有 $(m_x, [r_x]_1)$ ， $P_2$ 持有 $(m_x, [r_x]_2)$ 。
优势：支持“可验证重构”，任意两方协作可检测恶意篡改（如 $P_1$ =和 $P_2$ 可通过 $m_x - [r_x]_1 - [r_x]_2$ 恢复 x，若结果不一致则中止协议）。

示例：若 x=5，随机值 $r_{x}$ = 3，则 $m_x = 5 + 3 = 8$ 。 $P_1$ 持 $(8, [r_x]_1=1)$ ， $P_2$ 持 $(8, [r_x]_2=2)$ ，恢复时 x = 8 - 1 - 2 = 5。

③ 为什么需要两种共享方案？

[·]ₗ-sharing：轻量级，适合高效线性运算（如加法），但不支持乘法验证。
〈·〉ₗ-sharing：通过引入随机值和可验证重构，支持恶意安全验证，是实现乘法门批量校验的基础。

类比理解：

[·]ₗ-sharing 类似“两人各持一把钥匙，需同时插入才能开门”；
〈·〉ₗ-sharing 则增加了“钥匙防伪标签”，开门时需验证标签一致性，防止假钥匙。

4. 核心运算协议

①乘法门

基于ASTRA协议实现z=x⋅y：

离线阶段：生成随机 $r_z$ ， $P_0$ 计算 $\Gamma = r_x \cdot r_y + r_z$ 并共享给 $P_1, P_2$ ；

在线阶段：

P1 和 P2 各自持有：

公开值 $m_x = x + r_x$ ， $m_y = y + r_y$ （原始数据 x, y已被随机数“掩盖”）；
随机数份额 $[r_x]_1, [r_x]_2$ 和 $[r_y]_1, [r_y]_2$ 。

$P_1, P_2$ 本地计算 $[m_z] = x*y+[r_z]=m_x m_y - m_x [r_y] - m_y [r_x] + [\Gamma]$ ，重构 $m_z$

②内积运算
扩展乘法至n-维内积 $z = \sum_{i=0}^{n-1} x_i \cdot y_i$ ，通信成本与单次乘法相当：

离线阶段：生成 $[\Gamma] = \sum (r_{x_i} r_{y_i}) + r_z$ ；

在线阶段：本地计算 $[m_z] = \sum (m_{x_i} m_{y_i} - m_{x_i} [r_{y_i}] - m_{y_i} [r_{x_i}]) + [\Gamma]$

结果：最终 $m_z = \sum x_i y_i + r_z$ ，减去 $r_z$ 得到内积 z

类比理解

乘法门：如同计算 (a+b)(c+d) = ac + ad + bc + bd，但提前约定 ad + bc + bd的值（即 $\Gamma$ ），在线只需计算 ac。
内积：相当于计算多个乘法的总和，但通过统一的随机参数 $\Gamma$ 抵消所有交叉项，避免重复通信。

通过这种“离线预处理+在线轻量计算”的模式，协议在保证恶意安全性的同时，实现了高效的隐私保护机器学习推理。

5. Schwartz-Zippel引理：多项式根的稀疏性原理

Schwartz-Zippel引理是代数中的一个重要工具，用于判断两个多项式是否相等，核心思想是：随机选取一个输入值代入多项式，若结果为零，则多项式大概率是零多项式（即所有系数均为零）。在文档的恶意安全MPC协议中，该引理被用于降低误差隐藏的概率，确保验证的可靠性。

引理的核心内容

对于一个非零多项式 f(x)（系数取自有限域或环），其次数为 d，若从大小为 S 的集合中随机选取一个值 rr，则 f(r) = 0 的概率不超过 $\frac{d}{|S|}$

通俗解释：次数为 d的非零多项式最多有 d个根（使多项式值为零的输入）。若从 |S| 个可能的输入中随机选一个，恰好选中根的概率不超过 $\frac{d}{|S|}$ 。
关键意义：通过增大集合 S的大小（如文档中的环大小或多项式环维度），可将“误判概率”（非零多项式被误认为零多项式）降至可忽略。

应用：扩展环验证

文档中，为解决有限环 $\mathbb{Z}_{2^l}$ 中乘法不可逆导致的误差隐藏问题，协议将份额扩展到多项式环 $\mathbb{Z}_{2^l}[x]/f(x)$ （f(x)是 d次不可约多项式），并利用Schwartz-Zippel引理保证安全性：

误差多项式化：将攻击者引入的误差 ee 表示为多项式 $e(x) = e_0 + e_1 x + \dots + e_d x^d$ （原环元素作为常数项，其余系数随机）。
随机挑战验证：通过随机选取 $r \in \mathbb{Z}_{2^l}[x]/f(x)$ ，验证 e(r) =0 是否成立。
概率保证：根据引理，非零误差多项式 e(x) 满足 e(r) = 0的概率不超过 $\frac{d}{2^l}$ 2ld（2^l为环大小）。若取 d=64、l=64，则概率低至 $\frac{64}{2^{64}} \approx 10^{-17}$ ，几乎不可能发生

6. 双认证位（daBits）

定义：双认证位（daBits）是一种在隐私保护机器学习（PPML）中用于连接算术共享与布尔共享的密码学原语，由Rotaru和Wood提出。其核心是生成一对共享值：

算术共享：在有限环 $\mathbb{Z}_{2^l}$ 上表示为 $\langle r \rangle_l$ ，支持高效的线性运算（如内积、矩阵乘法）；
布尔共享：在二元域 $\mathbb{Z}_2$ 上表示为 $\langle r[i] \rangle_1$ ，支持非线性运算（如比较、ReLU激活函数）。