基於 Diffie-Hellman 的 Private 集合交集協議無法通過仿真證明？
鑑於流行的 Private Set Intersection (PSI) 協議首先在
$$ 1 $$:
- 愛麗絲隨機選擇 $ a $ , 並發送 $ {H(x_i)^{a}\bmod p}| (i=1,…m) $ 給鮑勃。
- Bob 隨機選擇 $ b $ , 並發送 $ {H(y_i)^{b}\bmod p}| (i=1,…n) $ 給愛麗絲。
- Alice 計算並發送 $ {H(y_i)^{ba}\bmod p}| (i=1,…n) $ 給鮑勃。
- Bob 計算並發送 $ {H(x_i)^{ab}\bmod p}| (i=1,…m) $ 給愛麗絲。
- 每一方在本地計算交叉點。
**問題1：**如果（機會很小）存在 $ x_1 $ 和 $ x_2 $ 那 $ H(x_1)=H(x_2)^2\bmod p $ , 然後 Bob 可以發現它，因為 $ H(x_1)^a=(H(x_2)^a)^2\bmod p $ . Bob 肯定無法模擬這些資訊。這是否意味著該協議違反了半誠實的安全性？
我和朋友討論過這個問題，有人說這不違反半誠實的安全性，因為有機會 $ H(x_1)=H(x_2)^2\bmod p $ 可以忽略不計。但我認為確實如此，因為在定義 4.1 中。模擬證明教程
$$ 2 $$，模擬應該總是成功的，並且不應該依賴於輸入 $ {x,y} $ . **問題2：**在PSI協議（圖3）中
$$ 3 $$， 他們使用 $ H(H(x_i)+H(x_i)^{a}) $ 代替 $ H(x_i)^{a} $ （請注意，如果他們使用協議仍然是正確的 $ H(x_i)^{a} $ ），這似乎加強了我的觀點（天真的 DH-PSI 協議是不可證明的），因為 $ H(H(x_i)+H(x_i)^{a}) $ 比模擬更容易 $ H(x_i)^{a} $ . 我的理解正確嗎？ 謝謝。
- Huberman BA、Franklin M、Hogg T. 增強電子社區的隱私和信任$$ C $$// ACM 電子商務會議。ACM，1999：78-86
- Lindell Y，如何模擬它，https://eprint.iacr.org/2016/046.pdf
- 海因里希 A、霍利克 M、施耐德 T 等人。PrivateDrop：Apple AirDrop 的實用隱私保護認證，USENIX’SEC 21
如果（機會很小）存在 $ x_1 $ 和 $ x_2 $ 那 $ H(x_1) = H(x_2)^2 $ ，然後 Bob 可以發現它……模擬應該總是成功，並且不應該依賴於輸入 $ {x,y} $ .
我同意你朋友的觀點，即這種觀察並沒有違反半誠實的安全性。
在半誠實模型中，輸入與隨機預言無關。換句話說，輸入是先固定的，然後 $ H $ 被採樣。環境無法訪問隨機預言機（在本地隨機預言機模型中），因此它為誠實方選擇的輸入不依賴於隨機預言機。所以事件 $ H(x_1) = H(x_2)^2 $ 不依賴於 $ x_1, x_2 $ . 所有輸入的可能性都可以忽略不計，因此模擬器可以安全地忽略這種情況。
在 PSI 協議（圖 3）中
$$ 3 $$,
我不確定你的問題是什麼。在
$$ 3 $$他們需要一個惡意安全的 PSI 協議，而經典的 DH-PSI 協議則不需要。所以他們使用更複雜的 Jarecki & Liu 協議。 更大的問題似乎是關於經典的 DH-PSI 是否“無法模擬”，大概是指對抗惡意對手。我同意。試想一下雙方各有 1 件物品的情況。考慮一個損壞的 Alice 查詢隨機預言機的情況 $ x_0 $ 和 $ x_1 $ , 擲硬幣 $ b $ , 並發送 $ H(x_b)^a $ 對於隨機指數 $ a $ . 隨機指數 $ a $ 使模擬器的視圖（隨機oracle查詢 $ x_0, x_1 $ 和協議消息 $ H(x_b)^a $ ) 完全獨立於 $ b $ . 但模擬器必須猜 $ b $ 為了正確提取。