集合运算和关系运算计算机二级（隐私计算笔谈MPC系列专题）

集合运算

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

集合的并集是对两个集合中的所有元素进行合并，并集运算的符号为∪；集合的交集是取这两个集合中的公共元素，交集运算的符号为∩。假设有两个集合={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,…,之间。

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

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

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

两个参与者Alice的输入集合为，Bob的输入集合为，集合和集合中都只有个元素。两人首先为布谷鸟哈希选择三个哈希函数。设置的箱子数量为1.2，贮存区的大小为。

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

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

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

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

因此在1.2 次的OPRF结束后，Bob会掌握。

Alice则可以根据任意的计算：

并打乱和中的数据顺序。Alice将和发送给Bob，Bob将和中的值与他自己在箱子和贮存区中的进行对比，如果Bob的对应的OPRF值在或者中，那么就说明元素属于Alice和Bob的集合交集。

Alice的集合中的每个元素都被映射成了一个伪随机数，若Bob的集合中有和Alice集合相同的元素，假设，那么有，因此Bob能够通过Alice发来的和，在其中找到二者集合的交集元素，而无法知道Alice掌握的集合本身。