安全多方计算与隐私集合交集:协议与应用

需积分: 9 14 下载量 84 浏览量 更新于2024-08-08 收藏 948KB PDF 举报
"这篇文档主要讨论了安全多方计算与隐私集合交集计算这两个概念,以及它们在实际场景中的应用。安全多方计算是一种协议,允许多个参与者在不透露各自输入的情况下协同计算一个共同的函数,而隐私集合交集计算(PSI)则是用于保护隐私的情况下找出两个或更多集合的交集。文中提到了姚氏混乱电路作为解决这些问题的一种方法,并引用了多项关于此主题的研究论文。" 在网络安全和隐私保护领域,安全多方计算和隐私集合交集计算是非常重要的工具。安全多方计算(SMC)的概念源于密码学,它允许多个参与方在不泄露各自私密信息的情况下,共同计算一个预定的函数。这个协议的核心在于确保即使在有恶意参与者的情况下,除了最终的计算结果,其他任何参与者的输入数据都不能被其他参与者得知。在SMC中,参与者可以是1到n个,每个都有自己的输入,例如1到n的a_i,而输出是根据这些输入计算出的函数f的结果,如最大值、最小值、平均值和最大公约数等。姚氏混乱电路(Garbled Circuit)是一种实现SMC的方法,通过加密电路的方式使得每个参与者只能在其输入相关的情况下解密部分信息。 隐私集合交集计算(PSI)是SMC的一个具体应用场景。PSI协议通常涉及两个参与者,如客户端C和服务器端S,分别拥有私有的集合X和Y。目标是找到这两集合的交集Z,即X和Y的公共元素,而无需双方暴露各自的全部集合。在社交网络的场景下,PSI可以用于找出两个用户的朋友圈交集,同时保护各自的全部好友列表。例如,用户1(C)的朋友是{A, B, C, D},用户2(S)的朋友是{D, E, F},执行PSI后,用户1仅得知共享的朋友D,而不知道其他用户2的朋友。 自2004年以来,学术界对安全多方计算和隐私集合交集计算问题的关注度持续增长。多篇研究论文提出了更高效、更安全的解决方案,例如在恶意模型下具有线性复杂度的PSI协议,以及在有恶意对手存在时仍能保证安全性的集合操作协议。这些研究不断推动着这两个领域的理论发展和实际应用。