天天短讯！多方安全计算(6)：MPC中场梳理

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

天天短讯！多方安全计算(6)：MPC中场梳理

2022-12-23 23:10:07 来源：博客园

学习&转载文章：多方安全计算(6)：MPC中场梳理

前言

诚为读者所知，数据出域的限制约束与数据流通的普遍需求共同催生了数据安全计算的需求，近一两年业界又统将能够做到多方数据可用不可见的技术归入隐私计算范畴。粗略来说，隐私计算可分为以联邦学习为代表的机器学习类升级方案、以可信硬件为基础的可信执行环境类方案和以密码学相关技术为核心的多方安全计算类方案。

(资料图片仅供参考)

联邦学习类方案可视为机器学习在多数据源下的升级，对于模型优化等任务可较快完成；然而，更一般性的计算任务，又或者更一般性的场景（如一方提供模型，另一方提供数据），就超出了联邦学习的能力范畴。可信执行环境类方案由于使用可信硬件，可以相对简洁的完成对已有任务的安全迁移或新功能的编码；然而一方面，侧信道攻击与不断被发现的硬件设计漏洞使得TEE方案存在潜在隐患；另一方面，硬件采购这一过程会造成大量潜在客户的流失。

在之前的系列文章中：

安全多方计算(1)：不经意传输协议
安全多方计算(2)：隐私信息检索方案汇总分析
多方安全计算(3)：MPC万能钥匙-混淆电路
多方安全计算(4)：MPC万能积木-秘密共享
安全多方计算(5)：隐私集合求交方案汇总分析

我们对MPC中的部分核心技术与应用做了初步的介绍，在进一步具体介绍更困难的技术组件或场景应用之前，本文试图从宏观上对MPC中部分主要技术与场景做一个简单梳理。

简易框架

广义的MPC泛指所有多参与方下的密文计算问题；在此情况下，如何将MPC封装为一个易被使用的方案就是一个值得关注的问题。

以使用者的视角来看，最需要关注的是如何进行自身任务的创建与执行；用户通常了解与任务本身相关的参数，而不关心其实现机制，因而应该直接提供相应任务常用的接口，是以需要尽可能的补充应用的模板类型；实际而言，数据库操作与机器学习相关任务最受当前用户关注。然而，穷尽所有可能的任务也是不可能的，因而还需提供用户自身创建复杂任务的能力，即给予用户自定义组合基础运算的能力。综上，本文以为一个最简化的MPC方案总体设计应如图1所示；在此基础上，本文对现有部分重要技术做一个简单的罗列。请注意，受笔者能力与精力所限，本文所讨论内容仅为一个初级的梳理，不足以也不适用于实际工业化MPC模块设计；此外，模块之间的调用技术由于其极高的复杂性亦不在本文讨论范畴内，对此读者不妨参考[1]。

图1 MPC模块简易图

算法支撑层

密码算法模块

· 对称加密：经典加密方案，提供高速与强安全性加密，广泛用于支撑其余算法；通常基于置换、流加密、多重替换等实现，主流硬件对部分知名方案有一定优化；优先考虑SM4或AES方案，实际实现可参考2

· 非对称加密：经典加密方案，效率低于对称加密，常用于生成密钥，主流MPC方案使用不经意传输扩展结合对称与非对称加密以提升效率；通常基于某知名困难性假设，如大整数分解或离散对数问题；通常考虑SM2等基于椭圆曲线(ECC)的方案，实际实现可参考3

· 半同态加密：通常分为加法半同态与乘法半同态，可在密文上进行直接加法或乘法计算，而计算结果可正确的映射回明文中，实现效率通常低于非对称加密；通常基于素数域定制的困难性假设；加法半同态常考虑优化后的Paillier协议[4]，乘法半同态可优先考虑ElGamal算法

· 全同态加密：全同态加密常用有BFV/BGV/CKKS三种；其中CKKS支持浮点数计算；全同态方案通常基于格上的困难性假设，常关联打包(packing)与自举(bootstrapping)等技术；良好实现难度极高，应主要考虑调用业界知名库如seal等5；特别的，此类方案参数设定往往需要根据实际任务数值范围与计算深度进行调整

· 伪随机数模块：主要包含伪随机数生成器PRG，用于生成某范围内的伪随机数，其不可预测性是众多密码学算法的信任之源；实现的方式较多，读者不妨参考6了解细节，开源实现可参考2

· 不经意传输模块：主要包含标准不经意传输（OT，常基于对称与非对称加密），随机不经意传输（ROT，OT的一种变形），关联不经意传输（COT，OT的一种变形），不经意传输扩展（OTE，常基于IKNP或PCG）与不经意伪随机函数（OPRF，OTE的一种扩展）；前四者广泛用于秘密共享与混淆电路的实现中，而OPRF广泛用于专用计算模块中。相应的技术细节读者不妨参考安全多方计算(5)：隐私集合求交方案汇总分析，之后我们也会对本模块做更多说明。

· 关联伪随机数模块：常用于降低各类任务在线阶段（即得到实际输入后）的时间消耗；常见关联伪随机数协议有beaver triples，dabits，edabits等；主要用于基于秘密共享的密文乘法与密文比较运算中；通常基于FHE、COT或OLE完成批量构造；其应用方法不妨参考[7]，部分生成方法不妨参考[8]，部分开源实现可见9。值得注意的是，很多工作中通过引入可信第三方的形式生成其它特殊形式的关联伪随机数，但实用性较低。

数据结构模块

· 编码与解码：用于对输入数据进行编码；通常需考虑浮点数、负数与所选择环/域的映射以及多个数间的packing；由于不同密码学方案对编码方式的要求相差极大，实践中此模块很难独立实现。

· 布谷鸟哈希：广泛用于专用隐私计算模块中，用于降低通信与计算开销，其实现可参考2。

· ORAM：可译为不经意随机访问机；通过增加冗余存储与进行冗余访问的方式，涉及读取、解密、读写、重加密、写回几种关键操作，确保服务端无法推测访问信息所在实际位置。借助ORAM可广泛实现不经意数据结构，进而进一步支撑MPC的实现；但其实际实现不易且与其它模块较难兼容，因而实际实现优先级较低。

值得注意的是，由不经意传输所引申出了较多特殊的不经意结构，如不经意栈、不经意队列、不经意键值存储等；但此类方案通常与某些定制化方案高度绑定，因此本文不在此具体罗列。

网络通信模块

· boost.asio：C++最常用的扩展库，基于tcp/udp；简单易用，且C++23中可能纳入标准库；部分现有隐私计算开源库10中使用。

· zmq：不仅是一个网络通信库，还是一个高级的异步并发框架，适于超大数据量的通信，配置方便，部分现有隐私计算开源库11使用。

· grpc:基于HTTP2.0协议，广泛用于大数据的双向传输，部分隐私计算工业界产品中宣称使用其完成联邦学习等过程的通信。

基础运算层

通用计算模块

本部分需提供用户包含四则运算、基本初等函数、比较、排序、矩阵乘法（对于矩阵的复杂运算已有较多研究，但似乎未看到实际可用者）等功能。通常涉及到如下两个模块：

· 秘密共享：MPC中通常使用线性秘密分享(LSSS)，具有加法同态性；主要包含三种，加法秘密共享，shamir秘密共享，常用于三方的复制秘密共享。在之前的文章中，我们讨论过如何使用秘密共享完成加减乘运算；主流方案通常基于牛顿迭代方案实现除法计算，基于分段拟合的方案实现开方等计算；结合edabits等实现比较运算；基于比较运算与乘法组合完成排序运算；基于多项式拟合完成其它运算。

· 混淆电路：混淆电路涉及电路生成，实际使用中通常需依赖开源框架或特殊编程语言(obliv-c)。其核心在于与门与或门的安全计算方案，通常需结合Free XOR以及半门或切割技术。

实际计算时，通常糅合上述两类方案与同态加密以保证更高的效率，其实现思路读者不妨参考[12]与[13]。

专用计算模块

本部分所提供的方法介于基础运算层与高级应用层之间，既可作为独立任务为用户所使用，也常需要组合用于某个更大的任务中，常用的此类技术如下：

· 隐私集合求交PSI：两方或多方有数据集合，在不暴露每个参与者集合元素的情况下，让一方或多个参与方知晓交集元素的信息。此技术应用面极广，通常视数据规模、数据规模差异、网络带宽等基于OPRF或同态实现，部分典型工作读者不妨参考之前的文章。

· 隐私集合求并PSU：与PSI类似，使一方或多方知晓参与者集合的并集结果，其核心在于向其它参与方隐藏已有的具体信息；使用面相对狭窄，常用于安全数据库处理中；通常基于OPRF与隐私相等性测试（PEQT）技术实现[14]。

· 隐私信息检索PIR：通常专指基于keyword-pir，即查询方给出一个查询关键字，服务方（实践中通常为单服务器）提供该关键字对应的一个搜索结果；当需要多关键字多结果时，也常称为labeled psi；通常基于多项式编码与同态加密实现11。

信息扰动模块

在部分实际场景中，需直接暴露或提供信息，而不是基于信息进行安全计算；此时通常要确保信息具有一定的统计可用性和个体安全性，传统加密方案或上述功能性加密方案都不可用，此模块常借助于差分隐私技术完成，主要分为两类：

· 中心差分隐私：各参与方首先将输入上传至某个可信任的中心处，由中心处进行数据的整体扰动；从数据类型来说主要分为浮点数、整数与枚举型数值；从方法来说，主要分为拉普拉斯机制、指数机制、高斯机制，实现过程读者不妨参考15。

· 本地差分隐私：各方首先在本地将数据进行扰动，然后上传扰动后的数据至中心方；中心方通常会额外进行信息的无偏校正；本地差分隐私通常以随机响应扰动为主，对连续型数值通常需先进行离散化分类；实现过程读者不妨参考16。

高级应用层

数据库处理

数据库是现有最主流的数据存储方式，对其进行联邦改造以支持联合数据分析具有显著的意义。其难点一方面在于提供用户类SQL的编程方式，以及对用户需求的抽象语法树解析与分布式执行规划，另一方面在于使用安全的方法对数据库的内容进行实际计算处理，除标准算术运算与各类比较外，主要分为两部分：

· 联邦聚合：主要包含SUM、AVG、MIN/MAX等关键字；底层实现通常基于秘密共享或同态的数值运算，如需对个体进行保护，可结合差分隐私技术

· 联邦连接：主要包含JOIN等关键字；底层实现通常基于明文排序与基于秘密共享的比较运算，部分情形可结合隐私集合求并技术

机器学习预测

机器学习包含逻辑回归、决策树、神经网络等算法；在密文计算层面，对各类机器学习算法的密文改造方法是类似的；因此，不对此细分。

· 安全两方预测：一方提供数据，另一方提供模型，两方不暴露彼此的信息。实践中通常基于同态加密完成主体计算部分，用不经意传输辅助完成比较运算，读者可参考[13]了解更多信息。当两方拓展为多方时，由于其它的技术缺乏拓展性或在编码中存在显著的难度，通常主要秘密共享技术完成，对此读者不妨参考[17]。

· 安全外包预测：常见场景为，模型以公开或加密的形式存储在多个云服务器（通常为两个）中，数据提供者将数据进行切分，多个云服务器之间通过密文交互，完成模型的前馈，并最终将密文结果返回给数据拥有者，数据拥有者从多份密文结果中恢复正确结果。本过程事实上是安全两方预测的加强版本，因为其需要计算参与方既不知道数据，也不知道模型，实践中通常基于秘密共享技术完成，读者不妨参考[18]。

机器学习训练

· 通用两方建模：两个参与方各自拥有部分数据，事先约定好模型种类、结构与超参数，通过密文交互完成两方数据的协同建模。此功能与联邦学习类似，但相比联邦学习，理论精度更高，但通信量与计算复杂度都远高于对应的联邦学习方案。在计算机制上与机器学习预测类似，可基于同态与不经意传输完成；实践中也常基于秘密共享完成，但秘密分享乘法带来的环溢出问题仍缺少高效的解决方案。读者不妨参考[19]。

· 差分隐私建模：由于完全基于密码学方案的建模方案效率过低，部分方案考虑使用差分隐私对输入特征、梯度信息、结果输出进行扰动；此过程本质上是依靠随机梯度下降(SGD)本身较强的容错性，且此方案可抵抗成员推理攻击、模型反演攻击等常见攻击方法；也因此，差分隐私也常被结合进联邦学习策略中。然而，差分隐私类的方案通常会造成较为明显的精度损失，这限制了其实际使用场景，具体方案读者不妨参考[20]。

总结

本文从使用的角度对多方安全计算体系内的部分技术与场景做了一个简单的梳理，希望能使读者对MPC的架构有一个更直观的认识。再次请读者注意，本文仅为一份理论化的空谈（作者太谦虚了），在实践中使用的方案通常不会也无法进行严格的进行分层分块。在后面的文章中，我们将重新聚焦于具体的理论细节并做相应的实现详解。

参考文献

[1]: Zheng W, Deng R, Chen W, et al. Cerebro: A Platform for {Multi-Party} Cryptographic Collaborative Learning[C]//30th USENIX Security Symposium (USENIX Security 21). 2021: 2723-2740.

[4]: Damgård I, Jurik M, Nielsen J B. A generalization of Paillier’s public-key system with applications to electronic voting[J]. International Journal of Information Security, 2010, 9(6): 371-385.

[7]: Escudero D, Ghosh S, Keller M, et al. Improved primitives for MPC over mixed arithmetic-binary circuits[C]//Annual International Cryptology conference. Springer, Cham, 2020: 823-852.

[8]: Mohassel P, Zhang Y. Secureml: A system for scalable privacy-preserving machine learning[C]//2017 IEEE symposium on security and privacy (SP). IEEE, 2017: 19-38.

[12]: Patra A, Schneider T, Suresh A, et al. {ABY2. 0}: Improved {Mixed-Protocol} Secure {Two-Party} Computation[C]//30th USENIX Security Symposium (USENIX Security 21). 2021: 2165-2182.

[13]: Huang Z, Lu W, Hong C, et al. Cheetah: Lean and Fast Secure Two-Party Deep Neural Network Inference[J]. IACR Cryptol. ePrint Arch., 2022, 2022: 207.

[14]: Kolesnikov V, Rosulek M, Trieu N, et al. Scalable private set union from symmetric-key techniques[C]//International Conference on the Theory and Application of Cryptology and Information Security. Springer, Cham, 2019: 636-666.

[17]: Byali M, Chaudhari H, Patra A, et al. FLASH: fast and robust framework for privacy-preserving machine learning[J]. Cryptology ePrint Archive, 2019.

[18]: Huang K, Liu X, Fu S, et al. A lightweight privacy-preserving CNN feature extraction framework for mobile sensing[J]. IEEE Transactions on Dependable and Secure Computing, 2019, 18(3): 1441-1455.

[19]: Wagh S, Tople S, Benhamouda F, et al. Falcon: Honest-majority maliciously secure framework for private deep learning[J]. arXiv preprint arXiv:2004.02229, 2020.

[20]: Arachchige P C M, Bertok P, Khalil I, et al. Local differential privacy for deep learning[J]. IEEE Internet of Things Journal, 2019, 7(7): 5827-5842.

关键词：机器学习伪随机数数据结构