隐私集合求交（Private Set Intersection，PSI）技术的发展、挑战与未来 （二）
隐私集合求交作为隐私计算领域一个重要应用，因其高效性与实用性显著，在近期得到了广泛的关注。本文将从隐私集合求交的概念、应用场景、起源、演化及未来发展等各个方面系统的介绍这一技术，以便隐私计算从业人员或对隐私计算富有兴趣的业界人员全面、深入的了解隐私集合求交技术，共同推动隐私计算技术的快速落地，为数据要素的安全流通与价值发掘保驾护航。”
上一篇文章详细介绍了PSI的相关概念、应用场景以及先前存在的不安全方案，本次文章将继续介绍安全PSI方案的发展历程和各类典型代表方案，供隐私计算从业人员参考。
2.2 安全的PSI方案
2.2.1 基于公钥加密的方案
基于公钥加密的方案可以追溯到1986年[2]，是学术界最早提出的PSI方案，主要包括基于Diffie-Hellmann密钥协商的PSI方案[2]和基于RSA盲签名的PSI方案[3]。下面简要介绍DH-PSI协议的基本原理：
图4 DH-PSI协议的基本原理概述
在此协议中，随机数a由A方生成，随机数b由B方生成，A、B双方都无法得知对方生成的随机数。在step 3，A可以根据B反馈的结果来比较x和y的哈希值是否相同，而根据离散对数困难问题，A和B都无法根据已知信息来推算出对方的随机数（A无法推算出 b，B无法推算出 a)和哈希值。基于公钥加密的PSI方案不需要使用辅助服务器就可以运行，但是公钥加密运算普遍需要昂贵的模幂等大数运算操作，计算开销较大。
-
优点：不需要辅助服务器
-
缺点：公钥加密的计算开销较大
-
那么，有没有计算高效的解决方案？
2.2.2 基于OT的方案
不经意传输（Oblivious Transfer, OT）是安全多方计算的基石。虽然OT本身也是基于公钥加密体制实现，但是OT扩展协议[4,5]的提出允许我们执行少量的基础OT（基于公钥的OT）后通过轻量级的对称加密来快速构造大量的OT协议实例，这使基于OT的PSI方案[6-8]变得十分高效。下面我们简述经典OT-PSI方案的基本原理：
图5 OT-PSI协议的基本原理概述
在此协议中，A方生成随机数w，B方生成随机数r0。A方通过OT协议根据w从B方选择加密密钥，密钥为q。随后，A方可以使用q加密本方的输入x，B方可以用A方发来的密文与本方的密文比较是否相同，若密文相同则明文相同。注意在Step 2，双方需要执行lambda次OT来协商用于B中一个元素求交的密钥，对于大规模数据，此开销是不可接受的，因此需使用OT扩展协议对此过程进行批量加速。另外，还有一些其他的优化手段，如使用hash压缩数据并对齐数据位置等。得益于OT扩展协议和其他优化手段，OT-PSI方案的计算开销较小，但是由于OT本身的特性，此类方案的通信开销较大。
-
优点：只需要少量公约加密，大部分操作使用对称加密完成
-
缺点：通信开销相对较大
基于OT的方案假设双方集合的大小是几乎相同的，即使在小集合交大集合的场景下，通信与计算开销也随着大集合的大小变化，有没有随着小集合大小变化的方案？
2.2.3 基于HE的方案
在双方集合大小相差很大的情况下，理想情况是将求交运算集中在一方进行，此时只需要传输与小集合相关的运算结果，通信开销较小。结合这种方案通信复杂度低的优点，Chen等人提出使用基于同态加密构造的 PSI 协议 [9]，其协议的基本思想如下：
图6 基于HE的PSI基础协议（来自文献[10]）
此协议应用相同元素的差为0的原理进行交集判断，使用HE算法来完成密文求差操作。为了防止差不为0的元素值泄露，每一次求差操作后会乘一个随机数r。为了提高协议的实际性能，Chen等人使用了一些优化方法。包括PSI领域的hash、切分技术，还使用了HE领域的批处理、分窗、模数转换技术。需要注意的是，每个技术都涉及到相应参数的配置方法，文献[11]中仔细考量各个参数的设置方法，寻找最优的参数组合，以达到最佳性能。
-
优点：通信开销小，计算开销随较小集合线性增长，随较大集合log型增长
-
缺点：相比基于OT的方案计算开销依旧较大
2.2.4 基于GC的方案
理论上讲，通用乱码电路(Garbled circuit，GC)可以完成任意的多方安全计算任务，同样也可以支持PSI。然而，虽然提出了一些基于GC的PSI方案[10]，但这些方案在计算开销和通信开销方面均没有明显优势。除了简单的求交需求，往往还需要在交集的结果上直接进行一些运算，此时，我们希望PSI的结果为可供进行安全计算的状态（一般为秘密共享态）。面向此类需求，基于乱码电路(Garbled circuit，GC)的方案是较好选择。Pinkas等人设计了允许计算的基于GC的PSI协议[11,12]，此类协议的每一个交集内元素会带有一个“负载”（payload），可以用来计算交集的一些函数。然而，基于GC方案的性能与其他类型的方案相比仍有较大差距，随着数据规模的增加，电路深度不断增加，导致电路规模快速膨胀，通信、计算、内存开销都随之膨胀。
-
优点：可以求交后完成运算
-
缺点：通信开销和计算开销都较大、内存开销大
3 挑战与未来
PSI方案的设计的关键点在于功能性、安全性、性能三方面的最佳权衡，由于性能是在保证安全性和功能性前提下永恒的追求，我们这里主要讨论安全性和功能性挑战。
3.1 安全性
在安全性方面，半诚实模型下的PSI协议已经过广泛的研究，由于信任双方对协议的诚实遵守，半诚实模型下的主要工作在于进一步提高性能和功能性。
由于PSI协议的求交结果般都首先由一方获得并同步给另一方，为了方便描述，此处我们定义首先获得求交结果的一方为结果方，另一方为数据方。
恶意模型主要存在以下两个问题：
（1）大多数高效的PSI使用cuckoo hash作为数据结构，那么数据方的每一个元素都必须发送其n个对应位置(假设cuckoo hash使用n个hash)的伪随机函数值给结果方，若数据方恶意少发送数据，则求交结果会缺失。
（2）求交结果一半都存在于一方（结果方），然后同步给另一方，如果此时恶意的结果方隐瞒一些结果集，那么数据方将无法获得完整求交结果。
在恶意模型中，协议需要使用额外的手段来防止上述攻击的可能，因此恶意模型下安全的协议的复杂程度和开销往往远大于半诚实模型下安全的协议，如何设计性能接近半诚实方案的恶意PSI方案仍旧是一个挑战。另外，这也引发我们的进一步思考，即恶意模型下PSI是否有必要，是否可以通过多方安全计算技术以外的手段来避免恶意模型的发生？例如，设置足够严厉的处罚措施，并设立不定期抽查机制来防止恶意行为的发生。
3.2 功能性
除了传统的平衡PSI，即双方集合大小相似，只需要得到交集的PSI，还有两种功能性PSI需要进一步研究：
3.2.1 Unbalanced PSI
Unbalanced PSI指一方集合很大，一方集合很小的求交情况。直觉上，由于一方的集合大小显著减少，求交性能应该有明显的提升，然而为了保障PSI的安全性，当前的unbalanced PSI方案相比于balanced PSI方案性能优势不是十分明显，如何进一步提高unbalanced PSI方案的性能仍旧是一个挑战。
3.2.2 PSI with computation
在交集上运算也是一大现实需求，可以直接应用在多方联合统计和数据分析等场景。然而现有的基于GC的方案在通信、计算、内存开销方面均不是最优解。如何设计高性能的PSI with computation方案是一挑战性问题。
4 总结
经过近40年的发展，PSI技术逐步趋向成熟，在隐私保护的实名认证、联合风控、数据探查等领域具有良好的应用前景。本文明确了PSI的相关概念、辨析了PSI和PIR在功能性和隐私性上的异同、综述了PSI的几种主流技术并对其优缺点进行了盘点。总而言之，基于公钥的PSI技术虽然通信开销较小但计算开销较大，较适合小规模数据集；基于OT的方案面向大规模数据具有最佳的运行性能，但其通信开销较大，总体运行时间受网络带宽限制；基于HE的方案对通信和计算开销进行了平衡且更适合不平衡的集合求交问题，然而与基于OT的方案相比其计算开销仍旧较大；基于GC的方案可以支持“求交后计算”的操作，但其通信开销和计算开销都较大、内存开销也很巨大。综上所述，各类PSI方案至今仍存在各自明显的优劣势，在实际应用中需要根据功能需求、计算资源和通信资源进行权衡，设计最佳解决方案。此外，PSI的理论研究仍需继续，在性能方面，需要找到计算开销与通信开销的最佳平衡；在安全性上，需要进一步研究如何高效的避免参与方的恶意行为；在功能性上，需要对Unbalanced PSI和PSI with computation方案进行进一步研究。期望工业界与学术界共同努力，推动PSI技术理论与应用的发展，获得更丰富的查询功能、更强大的安全保障和更高效的运行性能。
参考文献：
[1] Kamara S, Mohassel P, Raykova M, et al. Scaling private set intersection to billion-element sets[C]//International Conference on Financial Cryptography and Data Security. Springer, Berlin, Heidelberg, 2014: 195-215.
[2] Meadows C. A more efficient cryptographic matchmaking protocol for use in the absence of a continuously available third party[C]//1986 IEEE Symposium on Security and Privacy. IEEE, 1986: 134-134.
[3] Cristofaro, E. D., and Tsudik, G. Practical private set intersection protocols with linear complexity.
In Sion [52], pp. 143–159
[4] Ishai Y, Kilian J, Nissim K, et al. Extending oblivious transfers efficiently[C]//Annual International Cryptology Conference. Springer, Berlin, Heidelberg, 2003: 145-161.
[5] Asharov G, Lindell Y, Schneider T, et al. More efficient oblivious transfer and extensions for faster secure computation[C]//Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security. 2013: 535-548.
[6] Pinkas B, Schneider T, Zohner M. Faster private set intersection based on OT extension[C]//Proceedings of the 23rd USENIX Security Symposium. 2014: 797-812
[7] Kolesnikov V, Kumaresan R, Rosulek M, et al. Efficient batched oblivious PRF with applications to private set intersection[C]//Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. 2016: 818-829.
[8] Pinkas B, Schneider T, Segev G, et al. Phasing: Private set intersection using permutation-based hashing[C]//24th USENIX Security Symposium. 2015: 515-530.
[9] Chen H, Laine K, Rindal P. Fast private set intersection from homomorphic encryption[C]//Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. 2017: 1243-1255.
[10] Huang Y, Evans D, Katz J. Private set intersection: Are garbled circuits better than custom protocols?[C]//NDSS. 2012.
[11] Pinkas B, Schneider T, Tkachenko O, et al. Efficient circuit-based PSI with linear communication[C]//Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, Cham, 2019: 122-153.
[12] Pinkas B, Schneider T, Weinert C, et al. Efficient circuit-based PSI via cuckoo hashing[C]//Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, Cham, 2018: 125-157.
