Turbospeedz: 使用函数相关预处理技术提高SPDZ协议在线效率
前言
1
设计概览在安全多方计算协议中，任意函数 都可以表示成由加法门和乘法门组成的电路 。加法可以本地计算，乘法则需要调用Beaver三元组。利用Beaver三元组实现乘法时，在线计算阶段需要通信公开两个输入的掩码后值，这会造成通信量。本文在函数相关预处理模型下，利用随机掩码技术将公开操作从乘法门的输入线路转移到输出线路，从而减少了倍的通信。当然，上述技术会增加预计算的开销，进而增加总的开销。进一步，本文针对SPDZ系列方案中的Overdrive进行了修改，也对预计算进行了优化，使得Turbospeedz的整体通信优于Overdrive。2
SPDZ回顾2.1 SPDZ分享语义-分享在SPDZ系列协议中有个参与方，其中最多个可以被恶意敌手控制。秘密值被分享给满足；同时秘密全局MAC密钥也分享为，且。
2.2 基本运算
给定，其中是处于秘密分享，是公开值：
，，是线性运算，即各方可以在本地计算、不需要交互； 需要利用Beaver三元组交互计算乘法，在该计算过程中需要公开两个掩码值。
2.3 MACCheck协议
本文黑盒调用SPDZ的验证协议来保证计算的正确性。该验证失败的概率是。当足够大的时候，失败的概率是可忽略的。
2.4 SPDZ预处理和在线计算
预处理阶段，各方交互生成Beaver乘法三元组，平方数对，随机秘密值，和输入掩码。其中公开给。生成上述关联随机数的理想功能简记为。在线计算阶段，输入方首先计算并公开，然后所有参与方本地计算。加法门可以本地计算得到。对于乘法门，多方则需要交互公开和。进而，每一方在本地计算
3
在线计算改进
基于黑盒调用SPDZ预处理的在线计算改进
Turbospeedz首先黑盒调用SPDZ的预处理过程，生成需要的关联随机数来加速在线计算。本文需要的关联随机数如下：
置换值（permutation element）：对于电路中的线，生成随机元素（其秘密分享记作）。置换值在预计算阶段生成，独立于实际输入，且置换值也独立于Beaver乘法三元组。
外部值(external value):在线计算阶段，秘密拥有者计算，并公开。
加法门可以很直观的验证其可以本地计算：
对于乘法门，假设已有Beaver乘法三元组，本文首先定义了输入偏移（input offsets）：
进一步定义调节外部值如下：
从上式本文有：
上式可以用在在线计算阶段计算乘法输出，进一步设置输出线的置换值为（加入是为了让满足独立随机）。
类似的，平方函数可以计算如下：
上述该计算可以利用预计算关联随机数其中来实现。
鉴于以上推导，黑盒调用SPDZ预计算实现关联随机数生成的协议如下：
而本文提出在线优化协议如下：
可以看到，本文在线计算协议只需要公开一个元素。
针对Overdrive的预处理改进
为了提升预计算的效率，本文在Overdrive的基础上提出了如下优化：
令输出线的置换元素等于乘法三元组中的可以节省开销，但是这不安全，因为置换元素必须是独立随机的。从另一个角度，本文做如下优化：如果一条输出线是下一层乘法的输入，那么令输出的随机置换为下一层乘法对应的乘法三元组。因为三元组中的是随机独立的，所以这样是安全的。
本文令同一条线的三元组中的相同，即便该线可能输入不同的乘法门。很显然，该优化不可以再黑盒调用SPDZ，因为SPDZ对于每一个乘法门独立随机生成三元组。
鉴于上述优化，第三节中定义的和将为，这会进一步简化协议设计和实现。
基于上述优化的预计算协议如下：
总结
本文利用电路已知条件，基于掩码秘密分享技术进一步提升了在线计算的性能。一般的，该掩码秘密分享可以进一步迁移到任意秘密分享提升在线计算性能。相关协议设计和应用的论文有ABY2.0，Meteor，和ScoinFL等。
参考文献
[1] https://eprint.iacr.org/2020/1225
[2] https://eprint.iacr.org/2023/100
[3] https://arxiv.org/abs/2210.07376
作者简介：董业，本科毕业于山东大学计算机科学与技术专业，目前在中国科学院信息工程研究所攻读博士学位。主要研究兴趣包括隐私保护、安全多方计算、同态加密和机器学习。知乎：酸菜鱼。
往期推荐
1.FedPAC | 概率近似正确联邦学习
2.利用不经意传输完成隐私集合求交中国密码学会及各分支机构2023年主要学术活动计划4.笔记分享 | 冯登国院士MPC讲座（2）——基于秘密分享方法的安全多方计算协议