云辅助隐私集合求交（Server-Aided PSI）协议介绍

本文作者：神谱科技（小海Cryptology）

背景

隐私集合求交（Private Set Intersection，PSI）是安全多方计算的一个特定问题，允许参与方输入私有集合，共同计算私有集合交集且不泄露除交集以外的任何信息。

隐私集合求交基数（PSI Cardinality，PSI-CA）是PSI问题的变体，允许参与方输入私有集合，共同计算集合的交集大小且不泄漏除交集大小以外的任何信息。

PSI（隐私联系人查找、新冠接触者追踪、联邦学习样本对齐）和PSI-CA（COVID-19 heatmap、相关规则学习）具有广泛的应用场景，在学术界和工业界广受欢迎。

图1 PSI(左)和PSI-CA(右)示意图

本文首先介绍云辅助隐私集合求交的需求和场景、然后介绍不同场景的解决方案。

云辅助隐私集合求交需求

传统PSI协议中无论两方或多方参与求交时，都涉及参与方之间大量的交互和计算以保证参与方在不泄露私有集合信息的前提下获得所有参与方的集合交集。然而，现实生活中大量存储资源有限、计算资源缺乏的终端设备和移动设备有大规模数据PSI需求但无法承担大规模数据PSI的性能要求。

随着云计算应用的兴起，各种云计算平台拥有大量的存储资源和计算资源并以一种按需服务的方式向用户提供，产生了基于云辅助的PSI协议，借助于第三方云计算平台解决终端设备无法承担PSI协议产生的通信开销和计算开销问题。

图2 云计算平台

云辅助隐私集合求交场景

Server-Aided PSI高层次协议描述如图3所示：

1. 云计算平台作为不可信第三方服务提供商使用；
   
2. 各参与方将私有数据通过一系列加密或盲化处理(如同态加密、伪随机函数、密码安全hash函数、噪声因子等)后上传到云计算平台；
3. 云计算平台在密文上完成集合交集(集合交集基数)计算，并返回结果。

图3 Server-Aided PSI示意图[1][4]

相较于传统PSI协议仅关心数据加密后的交互安全性，云辅助PSI不仅要考虑数据加密后的交互安全性还需考虑云计算平台合谋安全性。

图4 Server-Aided PSI场景示意图

本文依据隐私集合求交的方式将现有Server-Aided PSI协议分为两类场景，如图4所示：

（1）云计算平台和用户交互式完成隐私集合求交计算：

• 例如两个具有一定计算能力的服务商之间需要计算集合交集，通过加入一个不可信的云计算平台提供重新编码功能帮助服务器仅通过伪随机函数实现PSI协议的安全性。(图4左)
• 例如设备受限的客户端 C 将计算外包给云计算平台H与有一定计算能力的服务商 S 之间计算集合交集。(图4中)

（2）隐私集合求交计算完全委托给云计算平台：

• 例如参与方均为设备受限的客户端无法支撑百万数据的存储和计算，参与方均将数据外包给云计算平台，云计算平台存储和计算交集再将结果返回参与方。(图4右)

云辅助隐私集合求交协议

云辅助-交互式委托计算协议一：

文献[3]提出了一种云计算平台仅提供重新编码功能，帮助参与方仅通过伪随机函数实现安全的PSI协议。与现有PSI协议的安全性需要公钥加密和对称密钥加密提供相比，提高了计算效率和降低通信开销。协议描述如图5所示：

图5 文献[3]协议示意图

Server-Aided PSI具体步骤如下：

1. 服务器1随机选择两个密钥  作为伪随机函数(Pseudorandom function,PRF)  的密钥。发送  给云计算平台,发送  给服务器2。
2. 服务器2采用密钥  计算集合  的伪随机值  ，发送给云计算平台。云计算平台不知晓密钥  ,伪随机值  随机不可区分.
3. 云计算平台采用密钥  计算集合  的伪随机值  ，将  发送给服务器2。服务器2不知晓密钥  ,伪随机值  随机不可区分.
4. 服务器1采用密钥  计算集合X的伪随机值得到  ，将  发送给服务器2.服务器2比较  和  得到交集结果。

Server-Aided PSI-CA：通过修改第(3)步，云计算平台重新洗牌集合  ，使得弱客户端不知晓集合  和  的对应关系，从而仅知晓交集的大小。

云辅助-交互式委托计算协议二：

文献[5]提出了一种云计算平台承担设备受限的客户端在PSI协议中的计算开销，与有一定计算能力的服务商 S 之间计算集合交集, 然后交集结果返回给弱客户端的场景。协议描述如图6所示：

图6 文献[5]协议示意图

Server-Aided PSI具体步骤如下：

1.  弱客户端随机选择短种子r,seed发送给强服务器，双方通过PRG得到相同的随机字符串。
2. 对于每一个  ，弱客户端采用随机种子seed生成随机数  ，盲化  发送给云计算平台。
3. 云计算平台和强服务器执行以BaRK-OPRF的OTE作为安全支撑框架的Otd-OPRF.强服务器输出密钥  .
4. 强服务器本地计算  的Otd-OPRF：  如果  和  相等则  和  相等。发送多项式  给云计算平台。
5. 云计算平台插值  得到与  相对应的随机值  并发给弱客户端。
6. 弱客户端比较      得到交集。

Server-Aided PSI-CA：通过修改第五步，仅通过云计算平台重新洗牌集合  {  }打乱元素的对应关系从而只能得到交集基数.

云辅助-非交互式委托计算协议一：

文献[6]实现了云计算平台的部分理想功能：计算交集的任务完全委托给云计算平台。该场景适用于所有参与方均为弱计算能力的参与方。协议描述如图7所示：

图7 文献[6]协议示意图

具体步骤如下：

1. 弱客户端随机选择一个密钥K发送给各弱客户端  ；
2. 弱客户端  采用密钥  加密集合  并进行混淆打乱得到  ；
3. 云计算平台计算交集  并返回给各方；
4.  弱客户端本地解密得到交集。

该协议仅提供一次性PSI计算，当添加或删除PSI协议中的弱客户端时，密钥K需要重新协商，数据需要重新加密与上传。

考虑云计算平台的恶意行为：防止云计算平台返回任意结果作为交集(例如仅返回部分交集元素、返回空交集、返回输入集(认为所有元素都是交集))，弱客户端可验证返回结果的完整性。如图8所示：

图8 文献[6]协议示意图

具体步骤如下：

1. 弱客户端之间协商不包含私有集合元素的三个集合  ；

2. 弱客户端加密集合  时同时加密  和  。  防止云计算平台返回空交集、  防止云计算平台返回输入集；

3. 弱客户端将  中的元素复制  份后再加密，防止云计算平台仅返回部分交集元素。

考虑恶意弱客户端提交一个错误的输入导致获得一个无效的输出，但恶意弱客户端获得有效的交集。如图9所示：

图9 文献[6]协议示意图

1. 将随机密钥  替换为两个随机密钥  和  对集合进行加密；
2. 云计算平台计算出交集结果后公开承诺交集结果，保证  在后续无法更改；
3. 弱客户端  发送  给云计算平台进行验证，若  和打开集一致，则云计算平台公开交集  。

云辅助-非交互式委托计算协议二：

文献[6]非交互式委托计算的PSI协议需假设云计算平台不与任何一方合谋且加密数据只能进行一次PSI操作。

文献[7][8]解决了上述问题，实现了云计算平台的全部理想功能：计算交集的任务完全委托给云计算平台、一旦数据集加密外包后即可进行无数次的PSI计算，无需对数据集再次加密和上传，同时弱客户端具有允许哪些弱客户端使用他们集合的决定。如图10所示：

图10 文献[8]协议示意图

以弱客户端A、B和云计算平台介绍该协议

初始化阶段：

云计算平台公开hash表参数：hash函数  、bin数量  、bin容量  ，伪随机函数  

数据外包阶段：

1. 弱客户端A、B分别采用朴素hash算法将集合  、  插入朴素hash表  .
2. 弱客户端A、B分别对朴素hash表    进行盲目：以弱客户端A为例对于hash表第j行选择同一个密钥  ，对第j行i列元素生成伪随机值  进行盲化   。将盲化值表示为向量  传输给云计算平台。

求交请求阶段：

1. 弱客户端A发送主密钥  和id  给弱客户端B
2. 若B同意，则B随机选取新密钥tk1,计算伪随机值  ,构造一个  阶伪随机多项式  ,盲化多项式得到  ,将向量q ⃗和  发送给云计算平台。

云计算平台求交阶段：

1. 云计算平台计算   .
2. 随机选取新密钥tk2,计算伪随机值  ,构造  计算  
3. 云发送向量  给弱客户端A

客户端结果检索阶段：

1. 计算  
2. 通过插值  到对应bin的多项式看是否为多项式的根判断是否为交集。

云辅助-非交互式委托计算协议三：

文献[7][8]非交互式委托计算的PSI协议中上传到云计算平台的数据均为静态数据不可更新。文献[9]保持文献[7][8]实现云计算平台全部理想功能外还实现了加密数据可更新的功能。如图11所示：

图11 文献[9]协议示意图

设置阶段：弱客户端依据朴素hash表算法构造朴素哈希表，并为每个bin生成一个多项式、BF和标签, 利用伪随机函数PRF盲化BF, 并随机排列桶、盲化BF和标签。客户端保留标签到桶的映射和排列, 向云发送置换的bin、BF和标签。

更新阶段：弱客户端利用哈希函数确定更改集合元素的所在bin, 计算bin的标签将其发送给云, 云将标签对应的bin和盲化BF发送给客户端, 客户端利用密钥恢复bin的内容对其进行重新编码然后将更新的bin和过滤器发送给云服务器。

PSI计算阶段：基于文献[7]的改进协议。

参考文献

[1] 申立艳,陈小军,时金桥,胡兰兰.隐私保护集合交集计算技术研究综述[J].计算机研究与发展,2017,54(10):2153-2169.

[2] 魏立斐,刘纪海,张蕾,王勤,贺崇德.面向隐私保护的集合交集计算综述[J/OL].计算机研究与发展:1-18[2022-06-21]. http://kns.cnki.net/kcms/detail/ 11.1777.TP.20211117.1534.002.html

[3] Trieu N, Yanai A, Gao J. Multiparty Private Set Intersection Cardinality and Its Applications[J]. Cryptology ePrint Archive, 2022.

[4]廖鹏程,陈小军,申立艳,时金桥.基于OT协议的外包隐私集合交集计算协议[J].信息技术与网络安全,2018,37(06):28-31.DOI:10.19358/j.issn.2096-5133.2018.06.005.

[5] 魏立斐,  王勤,  张蕾,  陈聪聪,  陈玉娇,  宁建廷.  半可信云服务器辅助的高效隐私交集计算协议.  软件学报. http://www.jos.org.cn/1000-9825/6397.htm

[6] Kamara S, Mohassel P, Raykova M, et al. Scaling private set intersection to billion-element sets[C]//International conference on financial cryptography and data security. Springer, Berlin, Heidelberg, 2014: 195-215.

[7] Abadi A, Terzis S, Metere R, et al. Efficient delegated private set intersection on outsourced private datasets[J]. IEEE Transactions on Dependable and Secure Computing, 2017, 16(4): 608-624.

[8] Kavousi A, Mohajeri J, Salmasizadeh M. Improved secure efficient delegated private set intersection[C]//2020 28th Iranian Conference on Electrical Engineering (ICEE). IEEE, 2020: 1-6.

[9] Abadi A, Terzis S, Dong C. Feather: lightweight multi-party updatable delegated private set intersection[J]. Cryptology ePrint Archive, 2020.

[10] 张恩,金刚刚.基于同态加密和Bloom过滤器的云外包多方隐私集合比较协议[J].计算机应用,2018,38(08):2256-2260.

来源：神谱科技   

END

往期推荐: