隐私集合交集计算：从理论到实践

"这篇文档主要关注的是隐私集合交集(Private Set Intersection, PSI)这一信息安全领域的技术，通过列举多篇在国际知名密码学会议发表的相关论文，展示了该领域的发展历程和研究热度。" 在隐私保护计算领域，Private Set Intersection (PSI) 是一项关键的技术，它允许两个或多个参与者在不泄露各自集合中非交集元素的情况下，计算出他们集合的交集。这一技术在数据共享和隐私保护之间找到了平衡，尤其在诸如社交媒体、医疗研究和金融合作等场景中有着广泛的应用。 1. PSI 的定义与基本概念 PSI 协议涉及两个参与者，通常称为客户端（Client, C）和服务器端（Server, S）。每个参与者持有自己的私有集合，目标是仅计算两集合的交集，而不会暴露各自的全部信息。例如，客户端 C 可能拥有用户的朋友列表，而服务器端 S 拥有用户的联系人列表。通过 PSI 协议，C 和 S 可以发现共同的联系人，即交集，而无需暴露各自的完整列表。 2. 需求场景 以社交网络为例，用户可能希望知道哪些朋友也使用同一服务，但又不希望服务提供商了解其全部社交网络。在这种情况下，PSI 协议提供了一种安全的数据匹配方式，保护了用户的隐私。 3. 与安全多方计算的关系 PSI 是安全多方计算（Secure Multiparty Computation, MPC）的一个子问题。MPC 允许多个参与者共同计算一个函数，而每个参与者只能获取到函数的结果，无法获取其他参与者的原始输入。姚氏混乱电路（Garbled Circuit）是一种常用的实现MPC的方法，可以用于实现 PSI。 4. 国际研究进展 自2004年以来，国际学术界对 PSI 的关注度逐渐提高。以下是一些里程碑式的论文： - "Efficient Private Matching and Set" (EUROCRYPT 2004) 开始探讨高效且隐私保护的匹配和集合操作。 - "Privacy-preserving set operations" (CRYPTO 2005) 进一步研究了如何在保护隐私的同时进行集合操作。 - "Efficient robust private set intersection" (ACNS 2009) 提出了抵御恶意攻击的强健 PSI 解决方案。 - "Linear-Complexity Private Set Intersection Protocols Secure in Malicious Model" (ASIACRYPT 2010) 提供了在恶意模型下具有线性复杂度的 PSI 协议。 - "Efficient set operations in the presence of malicious adversaries" (PKC 2010) 研究了在存在恶意对手时的集合操作效率。 - "When Private Set Intersection Meets Big Data: An Efficient and Scalable Protocol" (CCS 2013) 探讨了如何在大数据场景下实现高效且可扩展的 PSI。 - "Faster private set intersection based on OT extension" (USENIX Security 2014) 介绍了基于 OT 扩展的更快 PSI 方法。 - "Improved private set intersection against malicious" (EUROCRYPT 2017) 提出了改进的针对恶意攻击的 PSI 技术。 这些研究展示了 PSI 领域不断发展的安全性和效率，为实际应用提供了坚实的基础。随着大数据和云计算的普及，PSI 技术的实用性和重要性将进一步增强。