PSI 協議僅揭示兩組交集的一個元素

所以讓愛麗絲有一組整數，說， $ A = {a_1,\dots, a_n} $ ，類似地，Bob 有一組整數 $ B={b_1,\dots, b_n} $ .

是否有任何協議允許 Alice 和 Bob 從交集中隨機學習一個元素， $ A\cap B $ ? 我知道很少有私有集合交集算法，但它們都揭示了整個交集。

事實上，一種可能性是使用實現 PSI 電路 + 過濾器電路的通用亂碼電路協議，這樣來自 PSI 的結果（交集）被過濾，並且在交集的末尾只輸出一個隨機選擇的元素協議。但是，我不能說太多，除非這是可行的。

下面是一個為您的目的定制的協議，假設 $ |A\cap B| $ 可以被洩露和半誠實的對手。可以進一步優化。

您需要 3 個建構塊：

1. 具有數據傳輸協議的 PSI（請參閱下面的參考資料$$ 1,2, 3 $$）。具有數據傳輸協議的 PSI 是一種 PSI 協議，這樣在執行結束時，Bob 什麼也得不到，而 Alice 得到每個元素 $ a_i $ 在她的集合中，一個數據 $ d_i $ . 如果我們只想要 PSI，那麼如果 $ a_i $ 不在路口 $ d_i $ 是一個隨機字元串，否則如果 $ a_i $ 在路口 $ d_i $ 是 $ a_i $ 本身。這樣在執行協議後，Alice 就得到了交集。我們將使用的技巧依賴於這樣一個事實，即完全有可能讓 $ d_i $ 傳達其他資訊，而不僅僅是設置元素。
2. 語義安全的加密方案 $ (\mathcal{G},\mathcal{E},\mathcal{D}) $ 其中密文可以有效地重新隨機化。這裡 $ \mathcal{G},\mathcal{E},\mathcal{D} $ 是密鑰生成、加密、解密算法。一個例子是Paillier。對於任何密文 $ \mathcal{E}{pk}(m) $ ，可以通過生成新的加密 0 來重新隨機化它， $ \mathcal{E}{pk}(0) $ , 並利用同態性質得到一個新的密文 $ \mathcal{E}{pk}(m)*\mathcal{E}{pk}(0) = \mathcal{E}{pk}(m+0)= \mathcal{E}{pk}(m) $ . 新的 ciphertxt 加密相同的明文，但看起來完全不同。
3. 一種語義安全的對稱分組密碼 $ (G,E,D) $ .

在協議中，Alice 有一個集合 $ A $ , Bob 有一個集合 $ B $ . Bob 還生成了一個密鑰對 $ (pk,sk)=\mathcal{G}(\lambda) $ ( $ \lambda $ 是一個安全參數）。鮑勃給 $ pk $ 給愛麗絲。然後他們執行以下操作：

1. Bob 生成隨機密鑰 $ k_1=G(\lambda) $ ，然後使用分組密碼加密他的所有元素 $ E_{k_1}(b_1),\ldots,E_{k_1}(b_n) $ .
2. Bob 和 Alice 使用數據傳輸協議執行 PSI，這樣 Alice 使用她的集合作為輸入，Bob 使用他的每個元素 $ b_i $ , 發送數據載荷 $ (\mathcal{E}{pk}(1),E{k_1}(b_i)) $ , – 注意每個 $ \mathcal{E}_{pk}(1) $ 必須使用新鮮的隨機性生成。
3. 愛麗絲總共將收到 $ n $ 形式的數據片段 $ (c_1^i,c_2^i) $ . 如果 Alice 有一個元素 $ a_i =b_j $ （IE $ a_i =b_j $ 是在路口），愛麗絲將收到有效載荷 $ (\mathcal{E}{pk}(1),E{k_1}(b_j)) $ , 否則，Alice 將收到一條隨機數據，可以解析為 $ (\mathcal{E}{pk}(r_1),E{k_1}(r_2)) $ 在哪裡 $ r_1,r_2 $ 是隨機的。然而，Alice 無法判斷每個 $ (c_1^i,c_2^i) $ 她收到的是“好”或隨機的，因為它是一對密文。
4. Alice 生成一個新密鑰 $ k_2=G(\lambda) $ . 對於每個 $ (c_1^i,c_2^i) $ 對，Alice 重新隨機化 $ c_1^i $ 得到一個新的密文 $ (c^i_1)’ $ , 並加密 $ c_2^i $ 要得到 $ (c^i_2)’=E_{k_2}(c_2^i) $ . 愛麗絲把所有對 $ ((c^i_1)’,(c^i_2)’) $ 在一組 $ A’ $ , 隨機排列 $ A’ $ ，然後發送 $ A’ $ 給鮑勃。
5. Bob 生成一個新密鑰 $ k_3=G(\lambda) $ . 對於每個元素 $ ((c^i_1)’,(c^i_2)’) $ 在 $ A’ $ , 解密 $ (c^i_1)’ $ , 如果結果 $ \mathcal{D}{sk}((c^i_1)’)=1 $ , 放 $ E{k3}((c^i_2)’) $ 在一組 $ B’ $ . 處理完所有對後，置換 $ B’ $ 並且寄出 $ B’ $ 給愛麗絲。（如果 $ B’ $ 是空的，然後停止，因為交叉路口是空的）。
6. Alice 隨機選擇一個元素 $ e \in B’ $ , 發送 $ e $ 給鮑勃。Bob 解密並發送 $ e’ =D_{k_3}(e) $ 給愛麗絲。Alice 解密並發送 $ e’’= D_{k_2}(e’) $ 給鮑勃。Bob 解密並發送 $ e’’’=D_{k_1}(e’’) $ 給愛麗絲。現在 $ e’’’=D_{k_1}(D_{k_2}(D_{k_3}(E_{k_3}(E_{k_2}(E_{k_1}(b_l)))))) $ 是一個隨機元素 $ A\cap B $ .

1 Efficient Private Matching and Set Intersection, Michael J. Freedman, Kobbi Nissim, Benny Pinkas, EUROCRYPT 2004（連結）

2具有線性計算和頻寬複雜性的實用私有集相交協議，Emiliano De Cristofaro 和 Gene Tsudik，FC2010（連結）

3當私有集交集遇上大數據：一種高效且可擴展的協議，董常玉，陳立群，文子凱，CCS 2013（連結）

引用自：https://crypto.stackexchange.com/questions/61011