共计 2178 个字符，预计需要花费 6 分钟才能阅读完成。
汇合运算
汇合能够艰深地形容为确定的一堆货色。如有一个汇合𝐴，一个元素𝑐要么属于汇合𝐴，记做𝑐∈𝐴；要么不属于汇合𝐴，记做𝑐∉𝐴，元素𝑐不能既属于汇合𝐴又不属于𝐴。
汇合的并集是对两个汇合中的所有元素进行合并，并集运算的符号为∪；汇合的交加是取这两个汇合中的公共元素，交加运算的符号为∩。假如有两个汇合𝐴={1,2,3,4} , 𝐵={1,4,7,9}。汇合𝐴和𝐵中的公共元素为 1,4。若汇合𝐴和汇合𝐵进行并集运算，则后果为𝐶=𝐴∪𝐵 = {1,2,3,4,7,9}；
若汇合𝐴和汇合𝐵进行交加运算，则后果为𝐶={1,4}。
隐衷爱护汇合交
平安多方计算的指标是在不泄露各个参与者隐衷信息的前提下实现指标函数的计算。隐衷爱护汇合交运算（Private Set Intersection，PSI）能够看成是以参与者各自的隐衷信息为汇合，指标函数所实现的性能为汇合交的平安多方计算。
隐衷爱护汇合交的利用有通讯录匹配，如当初很多手机利用能够通过手机通讯录查找同样应用这个软件的好友，如聊天软件、具备社交属性的游戏等，用户必定不心愿本人的通讯录中的所有联系人都被软件所得悉，软件则把握有所有注册用户的手机号。
因而能够通过隐衷爱护汇合交，计算软件注册用户手机号汇合和用户本人的通讯录的交加，来寻找到同样应用该软件的好友，又不会泄露各自所把握的手机号信息。
本次要介绍的隐衷爱护汇合交协定是 Pinkas-Schneider-Segev-Zohner (PSSZ)，其基于不经意伪随机数函数 OPRF（Oblivious Pseudo-random Function）来结构 PSI。
首先介绍一下布谷鸟哈希（Cuckoo Hashing），布谷鸟哈希须要𝑏个一般箱子和 1 个储存区，以及𝑛个元素，将这𝑏个空箱用𝐵(1),…,𝐵(𝑏) 示意。还须要三个哈希函数，记为 \(ℎ_1(𝑥),ℎ_2(𝑥),ℎ_3(𝑥) \)，这三个哈希函数是将一个比特串映射到 1,2,…,𝑏之间。
首先对这𝑏个空箱进行初始化，之后应用哈希函数 \(ℎ_1(𝑥),ℎ_2(𝑥),ℎ_3(𝑥) \) 计算元素𝑥的哈希值，查看 \(𝐵(ℎ_1(𝑥)),𝐵(ℎ_2(𝑥)),𝐵(ℎ_3(𝑥)) \) 这三个箱子是否是空箱子，如果这三个箱子中至多有一个箱子是空箱子，就把𝑥放到这个空箱子中。
如果这三个箱子都曾经有元素放入了，就随机抉择 \(𝐵(ℎ_1(𝑥)),𝐵(ℎ_2(𝑥)),𝐵(ℎ_3(𝑥)) \) 这三个箱子中的一个 \(𝐵(ℎ_𝑖(𝑥)) \),𝑖∈{1,2,3}，用𝑥替换箱子 \(𝐵(ℎ_𝑖(𝑥)) \) 外面原来装的元素𝑥′。
接着计算𝑥′的哈希值并查看箱子 \(𝐵(ℎ_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 则能够依据任意的𝑖计算：
并打乱𝐻和𝑆中的数据程序。Alice 将𝐻和𝑆发送给 Bob，Bob 将𝐻和𝑆中的值与他本人在箱子和储存区中的 \(𝐹(𝑘_𝑖,𝑦_𝑖), 𝑖∈[1,1.2𝑛+𝑠] \) 进行比照，如果 Bob 的 \(𝑦_𝑖 \) 对应的 OPRF 值 \(𝐹(𝑘_𝑖,𝑦_𝑖) \) 在𝐻或者𝑆中，那么就阐明元素 \(𝑦_𝑖 \) 属于 Alice 和 Bob 的汇合交加。
Alice 的汇合𝑋中的每个元素 \(𝑥_𝑖 \) 都被 \(𝐹(𝑘_{ℎz(𝑥𝑖)},𝑥_𝑖) \) 映射成了一个伪随机数，若 Bob 的汇合𝑌中有和 Alice 汇合雷同的元素，假如 \(𝑦_m=𝑥_𝑛 \)，那么有 \(𝐹(𝑘_{ℎz(𝑥𝑖)},𝑦_𝑖)= 𝐹(𝑘_{ℎz(𝑥𝑖)},𝑥_𝑖) \)，因而 Bob 可能通过 Alice 发来的𝐻和𝑆，在其中找到二者汇合的交加元素，而无奈晓得 Alice 把握的汇合自身。
