【本报告由百度安全实验室与上海交通大学LATTICE 实验室联合完成】
隐私保护集合交集(Private Set Intersection, PSI) 计算属于安全多方计算领域的特定应用问题，不仅具有重要的理论意义也具有很强的应用价值。随着用户数据的隐私保护越来越受到重视，这一方向的研究更是符合人们日益强烈的在享受各类依赖个人信息的业务的便利性的同时最大程度保护个人信息私密性的需要。本文首先分析比较了17种基于多方安全计算或者全同态加密的PSI 协议方案，包括攻击模型、安全模型、性能测试等。结果表明目前EC-ROM/DE-ROM [9] 是目前最快的基于密码学的公开安全PSI 协议。同时，文章也对最新的基于SGX的PSI 协议做了对比分析。结果表明百度安全实验室自主提出的基于SGX 的PSI 协议在性能方面是目前最快的PSI 协议(EC-ROM 和DE-ROM) 的60 倍。而且在安全性，灵活性和多功能性等方面SGX PSI 比传统的PSI 具有不同程度的优势，比如SGX PSI 可以自适应2 方，3 方以及任意不同数量的参与者，而传统PSI 在参与方数目自适应方面尚有明显差距。
1、传统PSI
隐私保护集合交集协议允许持有各自集合的两方来共同计算两个集合的交集运算。在协议交互的最后，一方或是两方应该得到正确的交集，而且不会得到交集以外另一方集合中的任何信息。保护集合的隐私性是在很多场景下是自然甚至是必要的需求，比如当集合是某用户的通讯录或是某基因诊断服务用户的基因组，这样的输入就一定要通过密码学的手段进行保护。
值得注意的虽然PSI 协议的发展非常迅速，而且对于数据隐私性保护的需求也日益强烈，在目前很多应用场景下，高效而不安全的协议还是主流选择。因此了解PSI 协议的最新成果以及它们合适的应用场景将会对使用PSI 协议替换现有非安全协议起到非常大的帮助。
1.1 PSI 的应用场景
PSI 拥有很多实际应用场景，这里只挑选典型的两种应用场景—计算广告的实际效果和寻找联系人。
计算广告的实际效果线上广告是一种重要的广告形式。对于广告的有效程度的衡量的常见方法是计算所谓的转换率，也就是浏览广告的用户中有多少用户最终浏览了相应的商品页面，或是最终购买了相应的商品或是服务。一种通用的计算方法是由计算浏览广告的用户信息（由广告发送方占有）和完成相应交易的用户信息（由商家占有）的交集来计算（如计算交易总额或是总交易量等）。而与此同时双方的用户信息又是私密的，如果使用不安全的协议会导致一方的信息暴露给另一方，从而造成用户和商家或是广告主的隐私泄露。
注意到现有的很多类似应用场景下，所使用的协议仍然是不安全的，也就是说在计算广告相关数据的同时，隐私信息也受到了严重的威胁。1
1 一个例子是 Facebook 与信用卡信息持有方的合作：
https://www.eff.org/deeplinks/2012/09/deep-dive-facebook-and-datalogix-whats-actually-getting-shared-and-how-you-can-opt.
寻找联系人 当一个用户注册使用一种新的服务（如微信、Whatsapp 等）的时候，从用户的现有联系人中寻找有哪些已经注册了同类的服务是一种在大多数情况下十分必要的操作。通过将用户的联系人发送给服务提供商可以有效地完成这项功能，但是与此同时用户的联系人信息，一种在大多数情况下被认为是隐私的信息，也被暴露给服务提供商了。因此在这种场景下，将用户的联系人信息作为一方的输入，将服务提供商的所有用户信息作为另一方的输入来进行PSI 协议可以完成发现联系人的功能，而且可以防止交集以外的信息泄露给任何一方。
值得注意的是在这种特定的应用场景下，大多数情况是用户的联系人集合的基数远小于已注册的用户集合的基数。
传统的PSI 协议考虑的是两方集合大小基本相等的情况，在这种场景下大集合将会成为性能瓶颈。一些研究成果集中对于这种比较常见而有实际应用价值的场景做优化，并且取得了较好的成果。
1.2 PSI 协议的性能分析
不同PSI 协议的计算复杂度和通信复杂度在表1中有所示。表中的计算复杂度是通过非对称或是对称密码原语的使用次数衡量的，通信复杂度是通过在信道上传输的比特数衡量的。这里的假设是每完成一次OT 协议花费3 次对称密码操作（对于使用布隆过滤器的花费2.5 次对称密码操作）。计算姚氏电路中的与门使用4 次对称密码操作，计算GMW 电路中的与门使用6 次对称加密操作。
在同一类别中的PSI 方案大多数拥有类似的复杂度。朴素哈希方法与服务器辅助的方法需要对每一个元素执行一次对称加密操作（哈希），基于公钥的协议需要对每一个元素执行两次公钥操作，并且需要发送两个密文和一个哈希值。基于电路的方法的计算复杂度与电路中与门的数量成正比，在基于布隆过滤器的协议中，计算复杂度与布隆过滤器的大小成正比。在基于OT 的协议中，基于布隆过滤器的协议[3]，通信复杂度是与安全参数κ的平方成正比的，但是在[7] 中的协议，通信复杂度是与κ呈线性关系。
表 1: 不同 PSI 协议的复杂度比较，其中 sym 与 pk 分别表示对称与非对称操作的统计，t = NX + NY , m = max(NX , NY )，β ≈ λ + 2 log n − 1，ϵ, k, s, maxb 是哈希函数用到的参数，v 是在 OT 扩展协议中，使用的哈希函数的输出长度，C 是一个常数，表示 [1] 的同态操作产生的密文扩展。标有 * 的是在恶意模型下安全的协议。
2、基于MesaTEE 的PSI
2.1 MesaTEE 简介
MesaTEE 是全球首个通用安全计算平台（Universal Secure Computing，简称USC）。它为对安全和隐私有强诉求的场景提供了下一代通用安全计算能力，使得敏感数据即便在企业外环境和离岸场景下也能安全受控的流通和处理，而不会被泄漏或者滥用。这在全球关注隐私的今天格外重要，使得很多大数据业务成为可能。同时，由于USC/MesaTEE 天生的弱中心架构，也使得它和区块链形成完美的互补，填补了区块链急缺的高性能隐私数据处理能力。
MesaTEE 综合采用三项核心安全技术，包括百度安全实验室提出的混合内存安全技术（Hybrid Memory Safety与Non-bypassable Security Paradigm），机密计算技术（Confidential Computing，如Intel SGX），以及可信计算技术（如TPM），构建了完整的FaaS 通用计算框架，提供了严密而实用的隐私和安全保障能力。与传统基于密码学的多方安全计算或全同态加密技术相比，USC/MesaTEE 性能一般会快百倍以上，而且编程模式与传统编程一致，适合普通程序员快速上手进行应用。后继版本也会支持MesaPy（百度安全实验室推出的内存安全的Python）等安全语言，进一步降低开发门槛。如图1所示，MesaTEE 通过提供可信且安全的隔离执行计算环境，重新定义了未来的大数据商业模式。即使客户端和服务/平台提供商不完全相互信任，也可以有效地保护数据或模型的机密性和完整性。
同时，MesaTEE 大大简化了可信计算基础（TCB）、信任边界、和信任模型复杂度，让整个软件栈的审计和验证变得实际可操作。
2.2 基于MesaTEE 的PSI 协议
目前MesaTEE PSI 是以Intel SGX 为信任根的基础上搭建起来的。Intel SGX 提供了根植于CPU 的硬件可信和高强度的隔离运行环境（enclave）。即使攻击者控制了操作系统和其他特权级软件，也无法直接访问enclave（即无法修改也无法读取信息）。Intel SGX 还提供远程认证服务，即enlave 中的程序向其第三方证明其可信性。基于以上特性，我们可以基于SGX 建立一个可信的可验证的PSI server。这样，其他PSI 的参与方都可以通过远程认证来验证PSI server 是否处于可信状态。
图2给出了一个MesaTEE PSI 协议的流程图。图中该协议虽然以两个参与者为例子，但该协议兼容并且很容易扩展到三个或者多个参与者的情况。
第一步：参与PSI 的各个参与方（两方或者多方）和PSI 服务器通讯，服务器为各个参与方产生随机salt。
– 参与方对服务器进行远程认证，确保服务器处于可信状态。
– 服务器通过硬件指令生成随机salt，比如通过rdrand 指令。
第二步：服务器通知参与方，让参与方通过生成的salt 对数据进行散列。
– 服务器把salt 发回各个参与方。
– 各个参与方对自己的数据和salt 进行散列，使得攻击者无法通过hash 结果反推原始数据。
– 排序散列之后的数据。因为salt 的使用，排序结果仍然打破hash 和原始数据对应的order 关系，使得侧信道攻击更加困难。
第三步：参与方向服务器传输处理好的数据并要求服务器进行PSI 操作。
– 参与方把排序后的随机盐hash 数据加密传回服务器，并使用不同的传输密钥。
– 服务器在接收各个参与方的数据后开始做PSI。由于是排序的hash 数据，所以可以做流式求交，并且可以分布式并行处理。
– 服务器通过一个bit vector 来表达对PSI 结果。这样做的目的同样是缓解侧信道攻击。
第四步：服务器传vector 给各个参与方。每个参与方获得的vector 是不同的。
第五步：参与方通过自己的vector 来获得最终的PSI 结果。
该基于SGX 的PSI 协议不仅高效，而且具有很高的安全性：
1）具有SGX 的强隔离和可信等特性；
2）缓解了潜在的SGX 自身的侧信道攻击。使得该协议比单纯的Intel SGX 具有更高的安全性。
2.3 MesaTEE PSI 的优势
传统的PSI 是基于密码难题来构建可信根的。另外一种构建可信根的技术就是使用可信硬件，比如Intel 的SGX就是使用CPU 作为可信根（如图3)。使用SGX 作为可信根的好处是：
1）SGX 的可信根比以往其他的可信根（比如TPM）都要更小更可信；
2）SGX 提供一个安全可信的运行环境，从而保障代码和数据的机密性和完整度；
3）SGX可信运行环境可以提供近似原生态的运行速度，从而大大降低运行时期的性能开销。
在此基础上，MesaTEE PSI 还进一步加强了系统的安全性：
保证里面运行软件的内存安全性，使得诸如use after free、double free、buffer overflow 等内存安全问题不会发生。
MesaTEE 采用了“不可绕过范式”（Non-bypassable Security Paradigm），约束所有控制流和数据流必须经过关键检查点，显著减轻了审计和访问控制的难度，极大缩小了攻击面，归约了访问控制策略的部署，也让以此为基础的安全形式化验证变得实际可行。
采样抵御侧信道攻击的编程模式，使得潜在的侧信道攻击变得异常困难甚至无法完成。
相比于基于SGX 的PSI，传统的PSI 有着诸多的不足：
对于指定的协作运算，一旦预处理结束那些保密的信息只能被预先指定的参与方使用。缺少灵活的增加或减少参与方的能力。MesaTEE PSI 就没有这样的限制。
对于指定的运算模式，一旦预处理结束各方就只能做之前确定好的运算。缺少灵活的增加运算的能力。MesaTEE PSI 就没有这样的限制。
每一个参与方都需要互相交换信息，这样就造成了性能损失和无法避免的高延迟。MesaTEE PSI 只需要和中心可信节点通讯，有效的避免了这些问题。
传统的semi-honest 的PSI 不具有对运算结果的完整性保证。MesaTEE 的PSI 具有天然高效的完整度保护。从这个角度出发，MesaTEE PSI 比这类传统PSI 具有更高的安全性。如果要扩展传统PSI 增加完整度保护（比如扩展到malicious model 的情况），会使得整个协议的性能有数量级程度的下降。MesaTEE 仍可以匹配这类最强安全强度的传统PSI。
SGX PSI 可以自适应2 方，3 方以及任意不同数量的参与者，传统PSI 在这个自适应方面就明显不足。
在此之外，相比于传统的PSI 方案，MesaTEE PSI 在性能方面也有着明显的优势。
2.4 MesaTEE PSI 的性能优势
为了全面展示MesaTEE PSI 的性能优势，我们和一些高性能的传统PSI 做了性能对比。实验搭建在LAN 的环境下面。LAN 的传输速度10Gbps。参与方进行单线程的PSI 运算。参与方机器配置：Intel(R) Xeon(R) CPU E3-1280 v6 @ 3.90GHz 和128MB 的SGX enclave 内存。对于多线程情况，MesaTEE 方案可以很容易开启多个可信节点进行扩展。
对比结果总结在图4里面。图4的横轴是求交集合的大小，纵轴是求交所需时间。从图中我们可以观察到有些传统PSI 方案只能在很小的dataset 上面进行PSI 运算（比如RR [8]，SM32，SM64 [9] 等）。这样的方案往往只能处理百万以内的数据，超过这个数据量就无法完成整个运算。对于EC-ROM 和DE-ROM 方案[9]，他们克服了其他传统PSI 的瓶颈，可以处理较大数据集（比如超过千万的数据集）。但是和MesaTEE PSI 相比较，仍具有较大的性能不足（见图4)。从图中结果我们可以看到，MesaTEE PSI 比目前最快的传统PSI 方案还要快60 倍以上。而且，MesaTEE PSI 可以做分布式并行流式求交。这样性能差距还会进一步拉大。MesaTEE PSI 可以自由的从2 方求交、3 方求交扩展到任意多方求交，而且代价基本不变。事实上，参与者越多，要分析的数据集越大，与传统方法相比，MesaTEE PSI 会显示出更大的性能优势，还可以解决传统PSI 无法完成的复杂计算场景问题。
参考文献
[1] Chen, H., Laine, K., and Rindal, P. Fast private set intersection from homomorphic encryption. Cryptology ePrint Archive, Report 2017/299, 2017.https://eprint.iacr.org/2017/299.
[2] Cristofaro, E. D., and Tsudik, G. Practical private set intersection protocols with linear complexity. In Financial Cryptography and Data Security, 14th International Conference, FC 2010, Tenerife, Canary Islands, Spain, January 25-28, 2010, Revised Selected Papers (2010), R. Sion, Ed., vol. 6052 of Lecture Notes in Computer Science, Springer, pp. 143–159.
[3] Dong, C., Chen, L., and Wen, Z. When private set intersection meets big data: an efficient and scalable protocol. In 2013 ACM SIGSAC Conference on Computer and Communications Security, CCS’13, Berlin, Germany, November 4-8, 2013 (2013), A. Sadeghi, V. D. Gligor, and M. Yung, Eds., ACM, pp. 789–800.
[4] Kamara, S., Mohassel, P., Raykova, M., and Sadeghian, S. S. Scaling private set intersection to billionelement sets. In Financial Cryptography and Data Security - 18th International Conference, FC 2014, Christ Church, Barbados, March 3-7, 2014, Revised Selected Papers (2014), N. Christin and R. Safavi-Naini, Eds., vol. 8437 of Lecture Notes in Computer Science, Springer, pp. 195–215.
[5] Kolesnikov, V., Kumaresan, R., Rosulek, M., and Trieu, N. Efficient batched oblivious prf with applications to private set intersection. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security (2016), ACM, pp. 818–829.
[6] Meadows, C. A more efficient cryptographic matchmaking protocol for use in the absence of a continuously available third party. In A More Efficient Cryptographic Matchmaking Protocol for Use in the Absence of a Continuously Available Third Party (1986), IEEE, pp. 134–134.
[7] Pinkas, B., Schneider, T., and Zohner, M. Scalable private set intersection based on ot extension. ACM Transactions on Privacy and Security (TOPS) 21, 2 (2018), 7.
[8] Rindal, P., and Rosulek, M. Improved private set intersection against malicious adversaries. In Advances in Cryptology - EUROCRYPT 2017 - 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Paris, France, April 30 - May 4, 2017, Proceedings, Part I (2017), J. Coron and J. B. Nielsen, Eds., vol. 10210 of Lecture Notes in Computer Science, pp. 235–259.
[9] Rindal, P., and Rosulek, M. Malicious-secure private set intersection via dual execution. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security (2017), ACM, pp. 1229–1242.
声明：本文来自百度安全实验室，版权归作者所有。文章内容仅代表作者独立观点，不代表安全内参立场，转载目的在于传递更多信息。如有侵权，请联系 anquanneican@163.com。
