集合運算

集合可以通俗地描述為确定的一堆東西。如有一個集合，一個元素要麼屬于集合，記做∈；要麼不屬于集合，記做∉，元素不能既屬于集合又不屬于。

集合的并集是對兩個集合中的所有元素進行合并，并集運算的符号為∪；集合的交集是取這兩個集合中的公共元素，交集運算的符号為∩。假設有兩個集合={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掌握的集合本身。

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!