高效鲁棒的隐私保护机器学习框架
论文发表在PoPETs20，下载链接https://eprint.iacr.org/2019/1365
之前介绍的有关PPML的论文，大多数还是围绕半诚实（semi-honest）模型展开的工作。核心的任务聚焦于在保证隐私的情况下尽可能的提升系统性能。除了ABY3保证了正确性（correct with abort）和ASTRA进一步保证了公平性（Fairness）。FLASH进一步实现了输出可达性（Guaranteed Output Delivery，GOD），即无论恶意敌手进行何种攻击诚实参与方都可以得到计算结果。FLASH采用了4方计算架构，在诚实大多数（最多1方是静态恶意敌手）情况下可以满足GOD安全。其核心的设计思想在于，当检测到恶意行为时可以定位到恶意方在两方之间（但是不能确定具体是哪一方），但是可以确定剩余的两方是诚实参与方。如此，则可以令诚实参与方获得数据明文，从安全计算转化为明文计算（不对诚实参与方保护隐私）。
1）FLASH首先基于Additive Shairing（-sharing）设计了4方下的Mirrored Sharing（-sharing）方案；
2）进一步构造了Bi-Convey原语用来在4方下将 和 共有的输入在的辅助下传送给，该过程或者成功传送（和没有恶意行为），或者和能确定敌手在（，）之间（之后和交换各自的share恢复明文，进行明文计算）；
3）最终，关于乘法和比较等操作的构造，则是让每一次交互都可以抽象成一次Bi-Convey过程，从而使得整个系统能够满足GOD安全性要求；
4）进一步，FLASH构造了面向机器学习的计算模块，包括向量乘法、激活函数计算、截断、比特转化等，并对这些模块做了进一步优化。例如，向量乘法的通信量与向量大小无关、函数的近似等。并和ABY3、ASTRA进行了比较。性能的理论提升如下表。
Additive Sharing（-sharing）：对于，在2方下可以被分享为 和，满足。其中每一个参与方持有一份。
Mirrored Sharing（-sharing）：对于在4方下：
存在和满足：；
被-sharing分享在参与方之间，即，。而参与方则都持有和；
类似的， 被-sharing 分享在之间，即，。而则都持有和。整体的语义分享如下：
： ： ： ： 很显然，从-sharing 的线性性质可以很容易的推导出-sharing 的线性，即支持非交互计算加法和明文-密文乘法。
4.1 Bi-Convey
如前所属，Bi-Convey 在4方下将 和 共有的输入在的辅助下传送给，该过程或者成功传送（和没有恶意行为），或者和能确定敌手在（，）之间（之后和交换各自的share恢复明文，进行明文计算）。具体来说：
和各自将发送给。同时，和将关于的承诺发送给。当然，关于承诺使用的随机数是相同的； 如果收到的是相等的，那么和均没有作恶。接受，令，并丢弃来自的任何信息；否则，令，其中表示的share和随机数种子； 对于，如果收到的承诺相同，则令；否则令； 和互相交换msg； 如果且，则接受和匹配的。否则，和可以在本地恢复明文进行明文计算。
4.2 Input Sharing
在Input Sharing阶段，Dealer可能是恶意的敌手，那么其可能分发给不同的参与方的share不匹配。为了确认一致性，需要在share之后利用承诺进行验证。例如，如果Dealer是，在预计算阶段，所有的参与方根据共享的随机数种子生成（）。在线计算阶段，计算并把发送给和。最后，利用承诺来进行验证，取majority为最终分享结果。Dealer是其他参与方的情况类似。具体协议如下。
4.3 Circuit Evaluation
加法和明文-密文乘法比较容易，难点在于密文-密文乘法。对于乘法，中两方的目标是计算
令 ，，其中。那么根据-sharing的语义，在预计算阶段的随机数生成基础上，可以在本地计算，可以在本地计算。但是这并不能保证和能够成功的被获得。为了解决这个问题，进一步将和分解为，。其中，被和共有，被和共有，。如此一来，，则可以利用成功发送给中两方。其中可以在预计算也利用共享随机数种子和原语生成。最终，在计算之后便可以计算，并利用将发送给。具体协议如下。
4.4 Output Computation
恢复算法比较直观，因为每一方缺失的份额都被其他三方持有，所以可以令其他三方中两方发送缺失的份额，而剩下的一方直接发送对应的哈希值，最终结果取majority。具体协议如下。
ML Building Blocks
进一步构造面向ML计算的安全计算模块。
5.1 Arithmetic/Boolean Couple Sharing Primitive
在之后的计算中，会出现秘密值只被或者中两方持有，持有双方试图生成的情况。对于这种情况的sharing，可以令被另外两方完全持有的分享为0，从而减少开销。具体来说，如果被中两方持有，则；如果被中两方持有，则。具体协议如下。
注意，Case 2存在笔误：1)；2)。
5.2 Dot Product
对于向量内积 ，可以简单的调用乘法协议完成，但是这会使得通信和向量大小正相关。为了使得通信量独立于向量大小，可以借鉴ABY3中的方法，即现在share上做完加法求和再对求和结果进行通信。需要改变的则是对于的计算，类似的还有关于的计算。其余计算则没有太大改变。具体协议如下。
5.3 MSB Extraction
对于比较u<v，其等价于提取的最高有效位 。本文采取和ASTRA相同的设计思想：对于随机数，有。因此，可以令参与方在预计算阶段生成和，其中。在线计算阶段，则求调用并公开计算结果从而求得，然后计算，最后计算。但是利用乘法隐藏真实值是有一定的泄露的：例如，如果是奇数，而公开的是偶数，那么一定是偶数。所以，这种方法的安全性并不如one-time-pad。
5.4 Truncation
为了防止多次连续乘法造成溢出，本文截断方案采取类似ABY3中的截断方法：首先生成的秘密分享，其中。在线计算计算，乘法计算完成时公开，并截断获得。进一步，利用协议生成，并计算最后结果。具体协议如下。
5.5 Bit Conversion
在5.3节中，协议求得的是Boolean shares。但是计算得到Boolean shares之后，ML中后续的任务往往又涉及到乘法等算术计算。因此，需要将Bit的Boolean shares转化为等价的Arithmetic shares。对于比特 ，有：
5.6 Bit Insertion
给定Boolean shared的比特 和Arithmetic shared的，求在ML计算中是很常见的一种操作，比如。一种直接的方法可以首先调用实现Bit Conversion然后再调用协议实现乘法。进一步，本文提出了如下方法减少通信量和通信轮数。具体来说，对于
其中， , 。如此，参与方可以首先对于生成关于和的-shares，对于生成关于和的-shares，如此参与方可以本地计算, , , （每一项都被2个参与方共有）。最后，调用实现传输并计算最终的。具体协议如下。
本文做了关于关键模块的性能测试，进一步进行了ML模型的性能实验。对于ML中的算子，矩阵乘法、卷积可以归约到向量乘法，可以用分段函数计算（分段方法和SecureML一样），而则使用可以先做再求乘积。实验结果和ABY3进行比较。
6.1 模块实验
1）Dot Product：
首先在固定向量长度下比较FLASH和ABY3的Latency；
其次，比较性能在特征增加时带来的Latency变化。
2）MSB Extraction
首先比较一次协议调用的Latency：
进一步，比较多次调用的Latency增长趋势：
3）Truncation
Latency 和 Throughput 比较如下：
4）ML Evaluation
首先比较关于线性回归和Logistic回归的Latency。
接下来，比较两种回归的Throghput。
最后比较NN模型的Latency和Throghtput。
本文是比较早的一项实现GOD安全性的安全ML的工作，而且不再需要用广播。对后来的工作有很多借鉴意义。但是，也有许多需要改进之处，例如如何在实现GOD的情况下实现Privacy尚未得到很好的解决。
作者简介：
董业， 本科毕业于山东大学计算机科学与技术专业，目前在中国科学院信息工程研究所攻读博士学位。 主要研究兴趣包括隐私保护、安全多方计算、同态加密和机器学习。个人主页：https://ye-d.github.io/，知乎：酸菜鱼。
编辑：李安国
2021联邦学习全球研究与应用趋势报告 | 附下载链接
隐私计算打造资金监管新范式，打开大湾区数据要素流通新空间
隐私计算头条周刊（9.12-9.18)
END
开放隐私计算
OpenMPC