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

一、研究背景目前PPML主要依赖安全多方计算MPC技术使多个参与方能够在不泄露各自数据的情况下共同完成机器学习计算。然而目前已有的大多数MPC方案存在两个问题1. 大部分协议只考虑半诚实Semi-honest攻击模型默认参与者都会遵守协议实际部署中服务器可能故意作弊因此需要支持恶意安全Malicious Security2 恶意安全协议通信开销过大在PPML中大部分计算发生在环上环上的恶意安全协议比有限域上的协议复杂得多通信成本甚至超过计算成本成为部署PPML最大的瓶颈本文的核心目标就是设计一个通信高效、且能抵御恶意攻击的PPML框架使其性能接近半诚实Semi-honest场景下的协议。PPML的定义与价值隐私保护机器学习PPML是一种创新技术能够在保障敏感信息安全的前提下实现数据挖掘和机器学习使组织在不泄露隐私的情况下利用数据价值二、研究难点1. 环上的恶意安全验证困难绝大多数高效的恶意安全MPC技术如基于拉格朗日插值的批验证都构建在域Field如素数域 ℤₚ上。域中每个非零元素都有乘法逆元即可以做除法而环中则存在大量不可逆元素这使得域上的技术不能直接搬到环。直接迁移会让通信量增加约2倍。2. 乘法验证无法批量压缩为确保恶意安全必须在计算后对结果进行验证。最直接的方式是对每个乘法门Multiplication Gate逐一验证但这会产生与计算电路规模成正比的通信量代价极高。因此必须设计批量验证Batch Verification才能真正用于PPML。3. 混合电路与非线型函数的安全高效实现难神经网络不仅包含线性运算如矩阵乘法还包含大量非线性函数如ReLU、比较、截断。这些非线性操作在二进制电路上更高效而线性操作在算术电路上更优。如何在恶意安全模型下安全、高效地实现算术与二进制世界之间的转换并正确执行截断操作以避免数值溢出是构建完整PPML框架的又一难题。三、关键技术技术一基于扩展环的恶意安全乘法验证技术解决的问题有限环中乘法不可逆导致误差隐藏概率高现有协议批量验证通信量随乘法门数量线性增长。解决方案将原始环​扩展为多项式环其中f(x)是定义在​上的d次不可约多项式扩展环方案流程①乘法三元组压缩将N个乘法验证“打包”成一个单一的内积验证。其中这一步在本地计算使恶意方无法让两个不同位置的错误相互抵消。这样原本需要检查 N 个等式现在只需要检查 1 个等式通信量从 O(N) 降为 O(log N)。并且引入r的幂次权重如果恶意方在多个门上引入错误,那么总错误为其中是一个多项式要让总错误为0就需要 E(r)0即 r是多项式 E(X) 的根。而 r是从整个环中均匀随机选取的所以 r 恰好是某个根的概率小到可以忽略。②拉格朗日插值降维把相邻两项配对用直线表示每对的两个数用三个冗余点0、1、2锁定总曲线的形状随机选一个点 ζ作为新的验证位置每做一次验证项数减半。压缩阶段把 N 个乘法门变成了 1 个 N 维内积等式但这个内积仍然有 N 项。如果直接验证这个 N 维内积通信量还是 O(N)。降维的目的就是把 N 项逐轮减半重复 R 次后维度降到从而把通信量降到 O(log N)。③内积验证现在只剩下一个维度很小记为的内积等式各方共同生成随机多项式计算加权内积若Δ0则以高概率确认内积正确基于Schwartz-Zippel引理即z 是等于所有 xiyi之和Schwartz-Zippel引理非零误差多项式在随机挑战下的根概率不超过d64,l64时概率约0)确保验证可靠性。技术二支持混合电路与非线性函数的统一框架解决的问题非线性函数如ReLU、比较运算在算术电路中效率低需在算术与二进制计算间切换解决方案本文采用daBits双认证比特技术作为核心桥梁。daBits是一种同时在算术环 ℤ₂^ℓ 和二进制域 ℤ₂ 上被共享的随机比特。利用daBits协议可以安全地将算术共享转换为二进制共享反之亦然。这使得安全截断Truncation利用daBits和恶意安全的内积协议生成正确的截断对安全地处理定点数乘法后的缩放问题。非线性函数求值将复杂的比较、ReLU等操作交给更高效的二进制电路处理而将线性操作保留在高效的算术电路中。至关重要的是所有形式的秘密分享转换都最终依赖于本文设计的恶意安全乘法协议Π_Mult从而实现了整个框架安全性的统一和简化。技术三GPU加速的后处理验证阶段解决的问题多项式环上的计算如高次多项式乘法引入了巨大的计算开销成为新的性能瓶颈。解决方案作者观察到验证阶段涉及的多项式运算具有高度并行性。因此他们将该阶段即Post-processing中的批验证的所有计算卸载到GPU上进行加速。通过这种“计算换通信”的策略使得验证阶段的计算延迟被大幅削减不会成为整个协议的瓶颈。实验表明GPU加速后的验证阶段耗时远低于在线计算阶段。四、主要结论与贡献本文的主要贡献可归纳为协议性能领先提出了一种新的恶意安全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*bmod N1如果这样的b存在我们就说a是可逆的b是a的逆元。在环中一个数字a存在乘法逆元的充要条件是a和模数N互质即它们的最大公约数 (gcd) 等于 1。让我们把模数换成一般的即模 N 数字 2gcd(2,) 2不等于1。所以2没有逆元。数字 4gcd(4,) 4假设 ℓ ≥ 2不等于1。所以4没有逆元。数字 6gcd(6,) 2不等于1。所以6没有逆元。核心结论只要是偶数它就和模数有公因数 2即不互质因此偶数在环中没有乘法逆元。2. 环和域的概念①环环Ring是一个代数结构可理解为一组允许做加法、减法和乘法的数字集合并且这些运算遵循一些常规的规则比如结合律、分配律。最直观的例子整数集合 ℤ对任意两个整数你都可以进行加、减、乘结果仍然是整数。本文中的环这表示的是模 2^ℓ 的整数环。ℓ 是比特长度如64。它的元素是0, 1, 2, ..., 2^ℓ - 1。所有运算结果都对2^ℓ取模以确保结果仍在集合内。计算机中的数据就是二进制表示的用来编码数据比如定点数可以完美契合计算机的算术逻辑实现高效计算。②域在环的所有规则之上额外增加了一条最重要的规则除了 0 以外每一个非零元素都必须能做除法即存在乘法逆元以模7为例记作 ℤ₇找数字2的逆元找一个数b使得2 × b ≡ 1 (mod 7)b4时2 × 4 8mod 7 1 所以数字2在域 ℤ₇ 中有逆元逆元是4③环和域的区别环Ring不要求每个元素都能做除法。例如在 ℤ₂^64 中偶数2就没有乘法逆元因为没有任何整数乘以2 再模2^64 等于1。域Field在环的加、减、乘基础上还要求每个非零元素都有乘法逆元即可以做除法。3. 两种核心秘密共享方案用于3PC场景① [·]ₗ-sharing加法共享定义将秘密​如64位整数拆分为两个份额和满足持有方式参与方​ 持有持有​​ 不直接持有份额但协调生成过程。线性同态性支持加法和常数乘法例如c 为公开常数。示例若 x 5持持则② 〈·〉ₗ-sharing带随机值的共享定义引入随机值将 x表示为为公开值同时对进行 [·]ₗ-sharing即持有方式RSS持有和随机值的份额持有持有。优势支持“可验证重构”任意两方协作可检测恶意篡改如和可通过恢复 x若结果不一致则中止协议。示例若 x5随机值 3则。持持恢复时 x 8 - 1 - 2 5。③ 为什么需要两种共享方案[·]ₗ-sharing轻量级适合高效线性运算如加法但不支持乘法验证。〈·〉ₗ-sharing通过引入随机值和可验证重构支持恶意安全验证是实现乘法门批量校验的基础。类比理解[·]ₗ-sharing 类似“两人各持一把钥匙需同时插入才能开门”〈·〉ₗ-sharing 则增加了“钥匙防伪标签”开门时需验证标签一致性防止假钥匙。4.核心运算协议①乘法门基于ASTRA协议实现zx⋅y离线阶段生成随机计算并共享给在线阶段P1​ 和 P2​ 各自持有公开值原始数据 x, y已被随机数“掩盖”随机数份额​ 和。本地计算重构②内积运算扩展乘法至n-维内积通信成本与单次乘法相当离线阶段生成​在线阶段本地计算结果最终减去得到内积 z类比理解乘法门如同计算 (ab)(cd) ac ad bc bd但提前约定 ad bc bd的值即在线只需计算 ac。内积相当于计算多个乘法的总和但通过统一的随机参数抵消所有交叉项避免重复通信。通过这种“离线预处理在线轻量计算”的模式协议在保证恶意安全性的同时实现了高效的隐私保护机器学习推理。5.Schwartz-Zippel引理多项式根的稀疏性原理Schwartz-Zippel引理是代数中的一个重要工具用于判断两个多项式是否相等核心思想是随机选取一个输入值代入多项式若结果为零则多项式大概率是零多项式即所有系数均为零。在文档的恶意安全MPC协议中该引理被用于降低误差隐藏的概率确保验证的可靠性。引理的核心内容对于一个非零多项式f(x)系数取自有限域或环其次数为 d若从大小为 S 的集合中随机选取一个值 rr则 f(r) 0 的概率不超过通俗解释次数为 d的非零多项式最多有 d个根使多项式值为零的输入。若从 |S| 个可能的输入中随机选一个恰好选中根的概率不超过​。关键意义通过增大集合 S的大小如文档中的环大小或多项式环维度可将“误判概率”非零多项式被误认为零多项式降至可忽略。应用扩展环验证文档中为解决有限环中乘法不可逆导致的误差隐藏问题协议将份额扩展到多项式环f(x)是 d次不可约多项式并利用Schwartz-Zippel引理保证安全性误差多项式化将攻击者引入的误差 ee 表示为多项式原环元素作为常数项其余系数随机。随机挑战验证通过随机选取验证 e(r) 0 是否成立。概率保证根据引理非零误差多项式 e(x) 满足 e(r) 0的概率不超过2ld​2^l为环大小。若取 d64、l64则概率低至几乎不可能发生