集合運算和關係運算計算機二級（隱私計算筆談MPC系列專題）

2023-05-30 20:24:49

集合運算

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

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