面向隐私保护的集合交集计算综述

　　摘要 随着物联网和大数据技术的发展, 在计算机和手机上出现了大量分布式应用程序. 然而现有的分布式数据处理方式已不能很好地满足用户对隐私保护的需求. 隐私集合交集计算(private set intersection, PSI)协议作为一项典型的面向隐私保护的分布式集合计算技术, 允许各参与方输入其私有集合, 共同计算集合的交集, 且不泄露除交集以外的任何信息. PSI 协议作为安全多方计算的一种重要应用, 已被广泛应用于隐私计算领域, 具有重要的理论和实践意义. 首先介绍 PSI 协议的基本密码技术、敌手模型、安全证明、编程框架等基础知识;其次系统总结了构造传统 PSI 协议的设计框架: 基于公钥加密体制的框架、基于混淆电路的框架、基于不经意传输的框架;随后介绍 PSI 协议核心的隐私集合元素比较技术/工具: 不经意伪随机函数、不经意多项式评估、布隆过滤器等;进一步地详细阐述了适应新型应用场景的 PSI 方案: 基于云辅助的 PSI、非平衡型 PSI、基于阈值的 PSI 和多方 PSI;最后总结并展望面向隐私保护的集合交集计算中亟待解决问题和发展方向.

　　关键词 隐私集合求交; 安全多方计算; 隐私保护; 不经意传输; 混淆电路

　　魏立斐; 刘纪海; 张蕾; 王勤; 贺崇德， 计算机研究与发展 发表时间：2021-11-18

　　随着互联网大数据时代的到来, 人们通过对大量分布的数据进行挖掘得到其潜在价值，从而更好地服务于人们, 如用户爱好推荐系统、广告精准营销等. 然而, 在挖掘数据潜在价值的过程中, 也会产生个人隐私数据泄露等问题, 如英国咨询公司剑桥分析公司在未经 Facebook 用户同意的情况下获取数百万用户的个人数据. 因此, 实现数据可用不可见, 解决数据协同计算和挖掘过程中的数据安全和隐私保护问题就显得迫在眉睫. 相关国家和组织也出台保护隐私数据的法令法规, 如《中华人民共和国密码法》《中华人民共和国数据安全法》《中华人民共和国个人信息保护法》和欧盟《通用数据保护条例》都强调对数据的治理和隐私保护. 数据隐私保护已成为学术界和工业界关注的热点问题.

　　隐私数据保护最早源于安全多方计算(secure multiparty computation, MPC), 由姚期智[1]借百万富翁问题提出, 指各计算参与方无法得到除计算结果外的任何其他信息, 解决互不信任的数据持有者如何对隐私数据进行计算的问题 . 隐私集合交集 (private set intersection, PSI)是安全多方计算中的热点问题, 允许在分布式场景下各自持有隐私集合的参与方联合计算出集合交集而不泄露除交集以外的任何隐私信息. 在隐私保护的场景中, PSI 协议具有重要意义, 如新冠接触者追踪[2]、隐私通讯录查找[3]、在线广告实际效果计算[4]、基因序列匹配检测[5]等.

　　传统的 PSI 协议针对 2 个参与方设计, Meadows [6]基于公钥加密和利用 Diffie-Hellman 密钥交换的乘法同态性质提出了第 1 个 PSI 协议. 随后, 由 Huberman 等人[7]对 Meadows[6]的方案做出了完整描述. 2004 年由 Freedman 等人[8]借助不经意多项式求值和同态加密构造了第 1 个安全 PSI 协议. 2017 年 Shen 等人[9]对安全多方计算框架下的 PSI 协议进行了简要总结. 之后涌现了大量 PSI 的研究成果, 一大批新技术手段和构造框架被提出. 除了传统的安全多方计算理论中的混淆电路(garbled circuit, GC)、不经意传输(oblivious transfer, OT)、秘密共享(secret sharing, SS)、同态加密(homomorphic encryption, HE) 等技术外, 不经意伪随机函数(oblivious pseudorandom function, OPRF) 、不经意多项式求值 (oblivious polynomial evaluation, OPE)、布隆过滤器 (Bloom filter, BF)等集合元素比较技术的应用, 使得 PSI 的效率得到了很大的提高.

　　1 定义与基础知识

　　1.1 基础协议

　　秘密共享技术是许多安全多方计算协议的核心. 如何构建秘密分配算法和秘密重构算法是秘密共享方案的重点. Shamir[10]提出的(k,n)秘密共享方案基于多项式插值构建秘密分配算法和秘密重构算法, 通过控制多项式的未知系数实现阈值门限. Blakley[11]秘密共享方案基于线性几何投影实现. Jia 等人[12]秘密共享方案基于中国剩余定理实现. 除了上述特定环境下的门限秘密共享方案外, 研究者们还设计了安全多方计算环境下的(n,n)秘密共享方案, 可直接在比特碎片上进行相应的计算.

　　1.2 敌手模型

　　敌手模型由 2 个主要方面构成: 允许敌手的行为方式和腐败策略. 根据敌手是否指示参与方行事可分为半诚实模型、增强半诚实模型、恶意模型. 半诚实模型: 即使被敌手腐败的参与方也会诚实地执行协议, 但在执行过程中会主动收集相关信息, 并试图利用这些信息学习协议中的保密信息. 增强半诚实模型: 在半诚实模型基础上, 允许敌手更改起始输入, 但在其它输入上诚实的执行协议. 恶意模型: 允许敌手控制的参与方根据敌手的指示执行协议, 偏离原本协议.

　　1.3 安全性证明方法

　　理想/真实模拟范式[35]是安全多方计算协议最常用的 1 种证明方法, 通过模拟具有安全保证的理想模型与现实 PSI 协议比较, 间接证明其安全性. 通过定义理想模型相关的安全目标, 避免协议设计过程中安全目标的不完整性. 理想模型由完全受信任的三方计算功能函数, 并将结果返回给参与方. 真实模型通过 PSI 协议将功能函数拆分为多个消息函数并在参与方之间相互交流完成计算. 最后理想模型的视图与真实模型的视图达到不可区分来证明 PSI 协议的安全性.

　　1.4 编程框架

　　借助 MPC 通用编译器, 改善 PSI 现有技术, 减轻设计自定义协议的负担, 帮助研究人员快速建立协议实验. 本文从支持输入语言、参与方数量、敌手模型和所支持的协议进行简要总结如表 1 所示, 具体详情可参考文献[36].

　　2 隐私集合交集的设计框架

　　2.1 基于公钥加密体制的设计框架

　　隐私集合求交早期思想直接对元素进行加密, 然后在密文上进行相应的比较操作. 其最常用的技术是同态加密, 发送方加密集合发送给接收方. 接收方利用同态加密的性质对密文进行计算, 并将计算结果发给发送方, 发送方利用私钥对其解密并得到集合交集. 基于公钥加密的安全性假设主要分为 3 类: 1) 基于 DH(Diffie-Hellman) 假设. Meadows [6]基于离散对数困难问题实现 DH 密钥交换协议并以此实现 PSI 功能, Huberman 等人[7]发现基于椭圆曲线密码的 PSI 相较于基于离散对数密码的 PSI 具有更高的安全性和高效性. 2) 基于 RSA 假设. Cristofaro 等人[42]基于整数分解困难问题的 RSA 盲签名技术实现半诚实 PSI 协议, 文献[43]分析基于离散对数密码的 PSI 协议比基于整数分解密码的 PSI 协议更加高效. 3) 基于同态加密. Freedman 等人[8]将元素表示为多项式的根, 利用 Paillier 同态加密技术加密多项式系数和零知识证明实现两方恶意攻击安全的 PSI 协议, 2016 年 Freedman 等人[44]使用 ElGamal 加密加快计算效率和布谷鸟 Hash 技术降低计算复杂度. Kissner 等人[45] 采用不同的多项式表示方法将计算开销下降到与参与人数呈线性关系. Hazay 等人[46]构建一个具有门限解密的加法同态加密方案实现多方半诚实 PSI 协议 . Abadi 等人[47]提出基于点-值对的 d 次多项式表示集合方法, 通过 Paillier 加密方案完成, 将乘法复杂度从 O(d 2 )下降到 O(d). Jarecki 等人[48]使用加法同态加密和零知识证明来实现伪随机函数(pseudo-random function, PRF). Dou 等人[49]基于有理数编码和三角形面积计算公式并结合 Paillier 加密实现有理数上的 PSI 协议. 基于公钥加密的 PSI 协议一般具有较小的通信轮数, 适用于具有较强计算能力的模型, 但通信带宽和时间复杂度是实际应用中一个很大的瓶颈障碍.

　　2.2 基于混淆电路的设计框架

　　混淆电路可将任意函数转化为布尔电路, 再进行通用的安全计算. 早期基于通用电路的设计方案 DPSZ[50]描述了基于算术电路实现集合求交问题: 电路生成者通过对称密钥对电路门进行加密, 再生成混淆电路并将混淆电路发送给电路评估者; 电路评估者对混淆电路对应线路进行解密得到交集, 且得不到电路中其他线路的任何信息. 其构造的复杂度随电路深度的增加而增加. 本文主要讨论专用的电路 PSI 协议, 即在预处理阶段减少电路的比较次数和电路的深度, 电路阶段只进行元素的相等性测试以实现通用的 PSI 协议, 并可在电路 PSI 协议的基础上执行对称函数(交集基数、交集和、阈值-交集). 混淆电路有两种抵抗半诚实敌手的电路 Yao[1]协议和 GMW[27]协议. Huang 等人[51]对元素进行特定排序, 通过 Yao 电路合并后进行相邻元素的相等性测试, 构造出排序比较乱序电路实现半诚实安全的 PSI 协议. Pinkas 等人[52-54]和 Chandran 等人[55]基于 GMW 电路和 Hash 存储结构进行隐私集合的成员测试构造出 OPRF 电路实现半诚实安全 PSI 协议. 上述方案通过 Hash 技术降低比较次数, 通过隐私成员测试协议降低电路等值比较的深度, 使得电路 PSI 越来越高效. 然而, 此类协议需要额外的密钥计算过程和通信, 如参与方需要密钥协商等.

　　2.3 基于不经意传输的设计框架

　　化集合元素产生隐私保护效果. 构造思想: 首先将集合元素通过特定数据结构存储, 然后双方为每一个桶运行 OT 协议: 发送方使用随机值盲化集合元素并将盲化结果发送给接收方, 接收方在本地执行相等性测试得到隐私集合交集. 由于需要使用大量的 OT, 传统 OT 协议限制了 PSI 协议的安全性和效率性, 通过 OT 扩展技术(oblivious transfer extension, OTE)可有效解决该瓶颈. OTE 依据设计思想可分为 2 类: 一类是基于矩阵变换的思想利用少量公钥 OT 实现大量 OT 实例的 IKNP-OT. 依据抵御敌手行为能力可分为半诚实安全模型 OT 协议[20]和恶意安全模型 OT 协议[56] . 文献[58]基于布隆过滤器和 IKNP03- OT[20]构造出半诚实 PSI 协议. Pinkas 等人[43]将文献 [58]中 OT 协议换为 ALSZ13-OT[22]使接收方到发送方的通信量减少一半. 文献[59-60]将文献[58]中 OT 协议换为 KSO15-OT[56]并结合 Cut-and-Choose 技术, 以确保 Dong 协议中的发送方输入不能明显多于其 BF 中 1 的数量, 实现恶意攻击安全的 PSI 协议. 文献 [61]对文献[59]的 k-out-of-n OT 参数进行改进提供了更好的安全保证. Kolesnikov 等人[62-63]、Pinkas 等人 [64]、Chase 等人[65]分别基于 1-out-of-n KK13-OT[21] 和伪随机函数构造出单点 OPRF、不经意可编程伪随 机 函 数 (oblivious programmable pseudorandom function, OPPRF) 、多点 OPRF(multi-point OPRF, mOPRF)、带权多点 OPRF 实现具有半诚实安全的 PSI 协议. Pinkas 等人[66]基于 OOS17-OT 协议[57]构造具有恶意安全的 PSI 协议. 另一类是基于子向量不经意线性评估实现具有更低的通信效率但计算复杂度增加的 Silent-OT. Rindal 等人[67]基于半诚实安全的 Schoppmann 等人[24]协议和恶意安全的 Weng 等人[25] 协议分别构造出半诚实安全和恶意安全的 PSI 协议. 基于 OT 的 PSI 协议一般具有较低通信和计算量, 本文依据设计思想、功能和安全模型对现有 PSI 协议进行分类如表 2 所示：

　　3 隐私集合元素比较技术/工具

　　3.1 不经意伪随机函数

　　利用 OPRF 设计 PSI 协议是一种常见的思想. OPRF 允许接收方输入