隐私集合交集计算：PSI协议在社交网络的应用

"该资源是一份关于隐私集合交集(Private Set Intersection, PSI)计算技术的报告，由代小康在2017年12月15日编写。报告介绍了PSI的基本概念、应用场景以及与安全多方计算的关系，并列举了国外相关研究进展。" 隐私集合交集(PSI)是一种保护隐私的技术，它允许两个或多个参与者在不泄露各自输入集合之外的任何信息的情况下，计算他们共享元素的集合交集。PSI协议在保护个人隐私方面具有重要意义，特别是在社交网络中，用户可能希望知道与他们有共同联系人但又不暴露自己的全部社交图谱。 在报告中，简单需求场景描述了社交网站如Facebook和Myspace如何保存用户的关系图。PSI协议可以应用于这种场景，例如，用户1和用户2可能想要知道他们是否有共同的朋友，但不希望透露各自的整个朋友列表。通过执行PSI协议，用户1和用户2可以得知他们的朋友集合的交集（例如，D和C），而无需共享他们的完整列表。 PSI协议通常涉及两个参与方，即客户端C和服务器端S。客户端C持有输入集合X，服务器端S持有输入集合Y。协议的目标是让C得知X和Y的交集Z，但C和S都无法获知对方的全部输入。这个过程确保了数据的隐私性，因为除了交集部分，其他信息对双方都是保密的。 PSI与安全多方计算问题密切相关，后者是一个协议，使得多个参与者可以在不泄露各自输入的情况下计算一个公共函数。安全多方计算可以包括各种操作，如最大值、最小值、平均值等。为了实现这样的计算，有一种常见的方法是使用姚氏混乱电路（garble circuit）。 报告还提到了一些关于PSI的国外研究进展，指出从2004年开始，学术界一直在努力提高PSI协议的效率和安全性，尤其是在对抗恶意攻击者时。这些研究展示了该领域的持续发展和改进，旨在提供更高效、更安全的隐私保护解决方案。 该资源提供的PSI技术知识涵盖了定义、应用、相关问题以及研究动态，对于理解隐私保护技术在现代数据交换中的重要性具有很高的价值。