MPC基础

多方计算（MPC）允许多个参与方在不共享私有数据集的情况下进行联合分析。本文实现了一种三方计算协议，支持在非公开数据集上执行感知机和支持向量机（SVM）算法。

MPC协议中，每个持有秘密数据x_i的参与方共享输入函数f，均可获得f(x1,…,xn)的输出而不泄露其他方数据。姚氏百万富翁问题是最早的MPC案例，双方通过混淆电路在不透露具体金额的情况下比较财富多少。

安全MPC协议

秘密共享机制

以三方向模数p=43的有限域为例：

• Party1持有x1=11，生成随机值r2=21、r3=36
• 分配份额：share1 = (x1 - r2 - r3) mod 43 = 40
• share2 = r2 = 21, share3 = r3 = 36 单个或多个份额组合均无法还原原始数据。

加法协议

三方分别持有x1=11, x2=12, x3=13的份额：

1
2
3

Party1: [40,13,8]
Party2: [21,2,17]  
Party3: [36,40,31]

各方直接相加本地份额：

• Party1: 40+13+8 = 18 mod 43
• Party2: 21+2+17 = 40 mod 43
• Party3: 36+40+31 = 21 mod 43 最终18+40+21=36 mod 43，与11+12+13=36一致。

标量加/乘操作可通过单方调整份额完成：

• 标量加法：Party1将份额加5即可获得5+z的份额
• 标量乘法：所有方将z的份额乘5即可获得5z份额

乘法协议

基于Beaver三元组(a,b,c=ab)实现：

1. 各方持有x1,x2及三元组的秘密份额
2. 计算(x1-a)和(x2-b)的份额并广播
3. 通过标量乘法计算yb和az份额
4. 对yb,az,c的份额执行安全加法获得(yb+az+c)
5. 与yz相加最终得到x1×x2的份额

优化策略

电路复杂度挑战

• 算术电路规模与输入数据量正相关
• 比较运算需构造零点数占半输入空间的多项式
• 传统方案电路规模与有限域大小成正比

突破性方案

采用Catrina和de Hoogh的截断协议方法论：

• 通过模余数协议构建高效截断协议
• 将电路规模从场规模降为场比特大小
• 实现指数级电路压缩

实现成果

协议架构

基于Araki方案实现：

• 秘密共享、加法、乘法基础协议
• 专用安全比较和截断协议
• 点积计算协议
• 混合安全计算模型

性能表现

• 单次迭代仅需约15个逻辑门
• 支持任意精度定点运算
• 分类精度与原始算法一致
• 感知机与SVM算法均成功验证

（图2：左-感知机算法伪代码，右-单次迭代混合电路） （图3：左-SVM梯度下降伪代码，右-SVM单次迭代混合电路）

迭代策略

提供三种收敛处理方案：

1. 预先约定固定迭代次数
2. 公开披露epsilon值
3. 通过额外MPC计算收敛检查

结论

本项目成功解决了MPC机器学习中的固定点运算、电路规模和循环依赖等核心难题，首次实现三方参与的隐私保护机器学习训练。混合模型使得复杂电路可手工编写，为安全计算领域提供新范式。

作者系Trail of Bits实习生，基于博士研究方向完成该项目的创新突破。