作者：京东科技 孙晓军
摘要
隐私集合求交（PSI）是安全多方计算（MPC）中的一种密码学技术，它允许参与计算的双方，在不获取对方额外信息（除交集外的其它信息）的基础上，计算出双方数据的交集。隐私集合求交在数据共享，广告转化率，联系人发现等领域有着广泛的应用空间。本文对隐私集合求交的各项实现技术做了介绍和对比，对隐私集合求交的原理进行了分析，并进一步阐述了隐私集合求交目前面临的挑战和发展前景。
【关键词】：隐私集合求交，安全多方计算，不经意传输
1 引言
隐私集合求交（PSI）是安全多方计算（MPC）中的一种密码学技术，它允许参与计算的双方，在不获取对方额外信息（除交集外的其它信息）的基础上，计算出双方数据的交集。随着大数据，人工智能，云计算等技术的兴起，企业和个人对隐私数据的保护越来越重视。隐私集合求交，作为安全多方计算中的关键技术，在近年来的理论研究也得到了长足的发展。
在数字经济的众多安全威胁中，数据泄露已成为全球范围高发的安全事件之一，且这个趋势仍在持续。
- 2018年，Facebook因向第三方公司恶意泄露其用户信息被判罚数十亿美元
- 2019年，字节跳动因收集未成年人信息被罚款总计约1亿美元
- 2020年，中国电信2亿用户信息被贩卖，相关人员被判刑并处以罚款
- 2021年，亚马逊因违反数据隐私法规被处罚8.88亿美元
在这些数据安全问题中，有人为原因的故意泄露，也有技术缺陷导致的数据泄露。数据隐私问题，直接影响着企业的利益和信用，甚至因此导致企业倒闭。
随着中国在信息化和数字化的持续发展，大量具有敏感性和私密性的个人和企业信息在互联网上传播。如何安全地利用这些信息为企业和个人提供便捷的服务，同时又能保障信息不在传输过程中被泄露，对数字经济的健康发展，有着非常重要的作用和意义。
2021年6月10日，十三届人大常委会第二十九次会议通过了《数据安全法》
2021年8月20日，十三届人大常委会第三十次会议表决通过《*个人信息保护法》。
可以预见，对个人和企业隐私数据的保护，会被越来越多的企业和个人重视。我们通过对隐私集合求交的现状和发展的综述，重点介绍隐私集合求交的技术原理，为建立企业和个人对隐私数据保护的重视和信任，提供理论依据，并对隐私集合求交的发展前景进行分析，推进隐私计算的基础研究和商业应用发展。
2 基础原语
2.1 安全模型
安全模型又被称为对手模型或敌手模型，被用来衡量一个协议的安全等级。基于模型的安全假设，通常把安全模型分为诚实（honest），半诚实（semi-honest）和恶意（malicious）三种。
- 诚实型对手会完全按照密码学的协议执行，并且不会主动尝试获取额外的信息。
- 半诚实型对手会完全按照密码学的协议执行，但会尽可能尝试从收到的信息中获取额外的信息。
- 恶意模型不会严格按协议执行，他们可以做任何事情来达到获取额外信息的目的。
迄今为止，隐私集合求交的协议，大多基于对手模型是半诚实模型的前提下进行的研究。对抗恶意模型的协议，虽然提供了更好的安全保障，但通常具有较为低下的执行效率[8]。虽然半诚实模型不能对协议的双方提供完全的安全保护，但基于半诚实模型的协议的研究，可以为对抗恶意模型的协议，提供技术储备。并且基于对手模型为半诚实模型的协议，可以通过配合诸如随机预言，惩罚性措施等多种技术手段，来达到接近恶意模型下的协议的效果。
2.2 秘密共享
秘密共享（Secret Sharing，SS）是将一份原始秘密信息，拆分成多份。再把多份数据，分给不同的用户持有。其中的任何一份数据，都不能够完全恢复原始的秘密信息。只有达到指定数量的用户，集合他们手中持有的秘密，经过计算才能得出原始的秘密信息。秘密共享的关键在于秘密的拆分方式和恢复方法。秘密共享已经成为密码学中的一个重要分支，是信息安全和数据保密中的重要手段，被广泛应用于电子支付，密钥托管和隐私保护领域。
2.3 同态加密
同态加密（Homomorphic Encryption，HE）是将数据加密后，对加密数据进行运算处理，之后对数据进行解密，解密结果等同于数据未进行加密，并进行同样的运算处理。目前，同态加密支持的运算主要为加法运算和乘法运算。按照其支持的运算程度，同态机密分为半同态加密（Partially Homomorphic Encryption, PHE）和全同态加密（Fully Homomorphic Encryption, FHE）。半同态加密在数据加密后只持加法运算或乘法运算中的一种，根据其支持的运算的不同，又称为加法同态加密或乘法同态加密。半同态加密由于机制相对简单，相对于全同态加密技术，拥有着更好的性能。全同态加密对加密后的数据支持任意次数的加法和乘法运算。
3 隐私集合求交的主要技术方案
3.1 朴素哈希求交技术
图1 朴素哈希求交法