【隐私计算笔谈】MPC 系列专题(十):安全多方计算下的集合运算

作者 | 胡震恺 崔泓睿 郁昱

集合运算

集合可以通俗地描述为确定的一堆东西。如有一个集合𝐴,一个元素𝑐要么属于集合𝐴,记做𝑐∈𝐴;要么不属于集合𝐴,记做𝑐∉𝐴,元素𝑐不能既属于集合𝐴又不属于𝐴。

集合的并集是对两个集合中的所有元素进行合并,并集运算的符号为∪;集合的交集是取这两个集合中的公共元素,交集运算的符号为∩。假设有两个集合𝐴={1,2,3,4} , 𝐵={1,4,7,9}。集合𝐴和𝐵中的公共元素为 1,4。若集合𝐴和集合𝐵进行并集运算,则结果为𝐶=𝐴∪𝐵 = {1,2,3,4,7,9};

【隐私计算笔谈】MPC 系列专题(十):安全多方计算下的集合运算

若集合𝐴和集合𝐵进行交集运算,则结果为𝐶={1,4}。

【隐私计算笔谈】MPC 系列专题(十):安全多方计算下的集合运算

隐私保护集合交

安全多方计算的目标是在不泄露各个参与者隐私信息的前提下完成目标函数的计算。隐私保护集合交运算(Private Set Intersection,PSI)可以看成是以参与者各自的隐私信息为集合,目标函数所实现的功能为集合交的安全多方计算。

隐私保护集合交的应用有通讯录匹配,如现在很多手机应用可以通过手机通讯录查找同样使用这个软件的好友,如聊天软件、具有社交属性的游戏等,用户肯定不希望自己的通讯录中的所有联系人都被软件所得知,软件则掌握有所有注册用户的手机号。

因此可以通过隐私保护集合交,计算软件注册用户手机号集合和用户自己的通讯录的交集,来寻找到同样使用该软件的好友,又不会泄露各自所掌握的手机号信息。

【隐私计算笔谈】MPC 系列专题(十):安全多方计算下的集合运算

本次要介绍的隐私保护集合交协议是 Pinkas-Schneider-Segev-Zohner (PSSZ) ,其基于不经意伪随机数函数 OPRF (Oblivious Pseudo-random Function)来构造 PSI。

首先介绍一下布谷鸟哈希(Cuckoo Hashing),布谷鸟哈希需要𝑏个普通箱子和 1 个贮存区,以及𝑛个元素,将这𝑏个空箱用𝐵(1),…,𝐵(𝑏) 表示。还需要三个哈希函数,记为ℎ1(𝑥),ℎ2(𝑥),ℎ3(𝑥),这三个哈希函数是将一个比特串映射到 1,2,…,𝑏之间。

【隐私计算笔谈】MPC 系列专题(十):安全多方计算下的集合运算

首先对这𝑏个空箱进行初始化,之后使用哈希函数ℎ1(𝑥),ℎ2(𝑥),ℎ3(𝑥) 计算元素𝑥的哈希值,检查𝐵(ℎ1(𝑥)),𝐵(ℎ2(𝑥)),𝐵(ℎ3(𝑥)) 这三个箱子是否是空箱子, 如果这三个箱子中至少有一个箱子是空箱子,就把𝑥放到这个空箱子中。

如果这三个箱子都已经有元素放入了,就随机选择𝐵(ℎ1(𝑥)),𝐵(ℎ2(𝑥)),𝐵(ℎ3(𝑥)) 这三个箱子中的一个𝐵(ℎ𝑖(𝑥)),𝑖∈{1,2,3},用𝑥替换箱子𝐵(ℎ𝑖(𝑥)) 里面原来装的元素𝑥′。

【隐私计算笔谈】MPC 系列专题(十):安全多方计算下的集合运算

接着计算𝑥′的哈希值并检查箱子𝐵(ℎ1(𝑥′)),𝐵(ℎ2(𝑥′)), 𝐵(ℎ3(𝑥′)) 中是否都有空箱子,有一个空箱子则把𝑥放入其中,否则在𝐵(ℎ1(𝑥′)),𝐵(ℎ2(𝑥′)), 𝐵(ℎ3(𝑥′)) 中随机选择一个替换其中的元素 , 如此开始迭代。需要预先设定一个最大迭代次数𝑘,如果迭代次数超过了𝑘就把最后被替换出来的元素放入到贮存区,贮存区最多可放入𝑠个元素,箱子最多可放入 1 个元素。

两个参与者 Alice 的输入集合为𝑋,Bob 的输入集合为𝑌,集合𝑋和集合𝑌中都只有𝑛个元素。两人首先为布谷鸟哈希选择三个哈希函数ℎ1(𝑥),ℎ2(𝑥),ℎ3(𝑥)。设置的箱子数量为 1.2𝑛,贮存区的大小为𝑠。

Bob 对其的集合𝑌中的每个元素执行布谷鸟哈希。执行完毕之后,Bob 的每个箱子中最多只有一个元素,这是箱子的大小限制的,贮存区最多有𝑠个元素。由于箱子的数量为 1.2𝑛,集合𝑌中只有 n 个元素,因此此时必定有箱子是空的。

之后 Bob 产生随机元素,用随机元素填满所有的箱子和贮存区,使得每个箱子里都有一个元素,贮存区中有𝑠个元素。

不经意伪随机数函数 OPRF 可以通过𝑘𝑖将输入映射成一个伪随机数,任意给一个随机数𝑟1 和一个由输入映射成的伪随机数𝑟2,攻击者无法区分出输入映射成的是𝑟1 还是𝑟2。所需要使用的 OPRF 函数双方已经事先商议好了。

Bob 在用随机元素填满所有的箱子和贮存区后,和 Alice 间进行 1.2𝑛+𝑠次的 OPRF。用𝑦𝑖表示 Bob 第𝑖个箱子中的元素,用𝑦1.2𝑛+𝑗表示贮存区中的第𝑗个元素。

因此在 1.2𝑛+𝑠次的 OPRF 结束后,Bob 会掌握𝐹(𝑘𝑖,𝑦𝑖), 𝑖∈[1,1.2𝑛+𝑠]。

Alice 则可以根据任意的𝑖计算:

𝐻={𝐹(𝑘ℎz(𝑥𝑖),𝑥𝑖)|𝑥𝑖∈𝑋,𝑧∈{1,2,3}},𝑆={𝐹(𝑘1.2𝑛+𝑗,𝑥1.2𝑛+𝑗)|𝑥1.2𝑛+𝑗∈𝑋,𝑗∈ {1,…,𝑠}}

并打乱𝐻和𝑆中的数据顺序。Alice 将𝐻和𝑆发送给 Bob,Bob 将𝐻和𝑆中的值与他自己在箱子和贮存区中的𝐹(𝑘𝑖,𝑦𝑖), 𝑖∈[1,1.2𝑛+𝑠] 进行对比,如果 Bob 的𝑦𝑖对应的 OPRF 值𝐹(𝑘𝑖,𝑦𝑖) 在𝐻或者𝑆中,那么就说明元素𝑦𝑖属于 Alice 和 Bob 的集合交集。

Alice 的集合𝑋中的每个元素𝑥𝑖都被𝐹(𝑘ℎz(𝑥𝑖),𝑥𝑖) 映射成了一个伪随机数,若 Bob 的集合𝑌中有和 Alice 集合相同的元素,假设𝑦_m_=𝑥𝑛,那么有𝐹(𝑘ℎz(𝑥𝑖),𝑦𝑖)= 𝐹(𝑘ℎz(𝑥𝑖),𝑥𝑖),因此 Bob 能够通过 Alice 发来的𝐻和𝑆,在其中找到二者集合的交集元素,而无法知道 Alice 掌握的集合本身。

关注 Rosetta,一起玩转隐私 AI

github 链接:

https://github.com/LatticeX-Foundation/Rosetta

加入 Rosetta 社群 | 玩转隐私计算

【隐私计算笔谈】MPC 系列专题(十):安全多方计算下的集合运算

扫描上方二维码,即可加入社群

【隐私计算笔谈】MPC 系列专题(十):安全多方计算下的集合运算

推荐阅读

点击下方文字即可跳转

▶孙立林:隐私计算+区块链缔造数据融合全新基础设施

▶基于 Rosetta 框架的项目「Compute-to-data」荣膺万向区块链黑客马拉松一等奖

▶PlatONE 联盟链平台通过中国电子技术标准化研究院相关功能评测 通过用例达 93 项

Tips:关注“矩阵元”,回复“区块链”,免费获取全网最全的区块链入门资料。

【隐私计算笔谈】MPC 系列专题(十):安全多方计算下的集合运算

为了数据的流动

关注矩阵元 了解隐私计算

【隐私计算笔谈】MPC 系列专题(十):安全多方计算下的集合运算

–长按二维码 识别关注–

【隐私计算笔谈】MPC 系列专题(十):安全多方计算下的集合运算

戳阅读原文,走进矩阵元。

来源链接:mp.weixin.qq.com

分享到新浪微博 微信分享 扫码分享
分享到 Facebook
分享到 Twitter

该内容来自于互联网公开内容,非区块链原创内容,如若转载,请注明出处:https://htzkw.com/archives/27902

联系我们

aliyinhang@gmail.com