汇合运算

汇合能够艰深地形容为确定的一堆货色。如有一个汇合，一个元素要么属于汇合，记做∈；要么不属于汇合，记做∉，元素不能既属于汇合又不属于。

汇合的并集是对两个汇合中的所有元素进行合并，并集运算的符号为∪；汇合的交加是取这两个汇合中的公共元素，交加运算的符号为∩。假如有两个汇合={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把握的汇合自身。