私有集合交集，使用半可信伺服器
愛麗絲有一套 $ S $ 的話。鮑勃有一套 $ T $ 的話。他們想計算交點 $ S \cap T $ 他們的話，在半信任的第三方特倫特的幫助下。Trent 執行一個中央伺服器。伺服器通常是善意的，沒有惡意。但是，我們擔心伺服器受損的風險：黑客可能會侵入伺服器，下載伺服器上儲存的所有數據，甚至在有限的時間內控制伺服器。我們的主要安全目標是確保設法破壞伺服器的攻擊者無法學習該集合 $ S $ 或者 $ T $ . 此外，Alice 和 Bob 都不需要接收對方集合的副本（除了交集）。
我知道這個問題的超級簡單協議。Trent 選擇一個隨機對稱密鑰 $ k $ 對於偽隨機函式（PRF）。Alice 和 Bob 應用帶有密鑰的 PRF $ k $ 到他們的每一句話，並將結果上傳到 Trent 的伺服器。換句話說，Alice 計算集合 $ S^* = {F_k(s) : s \in S} $ 本地和上傳 $ S^* $ 到伺服器，Bob 上傳 $ T^* = {F_k(t) : t \in T} $ 到伺服器。現在伺服器可以幫助他們找到交集：伺服器計算 $ S^* \cap T^* $ 並將其發送給 Alice 和 Bob，這足以讓他們每個人恢復交集 $ S \cap T $ . 該協議是實用的，並且具有非常容易解釋的好處。它基本上是（鍵控）單向散列的一種應用。而且，只要鑰匙 $ k $ 不儲存在中央伺服器上，中央伺服器的妥協不會導致違反保密目標。
我的問題：這個超級簡單的協議是近似最優的嗎？或者是否有其他協議可以提供更好的安全性？我熟悉私有集合交集的所有復雜協議。它們中的任何一個都為這個特定設置提供任何安全優勢嗎？我最感興趣的是實際利益，而不是理論/基礎考慮。
這源於一個涉及數據匹配的現實問題（如果相關，多個州之間的選民登記名單匹配）。
您的簡單方法還不錯，但您可能會考慮以下修改：
- 首先，您不需要 PRF、任何形式的散列鍵或鍵和元素串聯的簡單散列就足夠了。基本上任何元素上的單向函式和某種鍵都可以解決問題，並且您可以優化速度。
- Trend 沒有選擇密鑰，但 Alice 和 Bob 進行了密鑰交換。Trend 根本不需要知道密鑰。這意味著他可以確定兩個元素是否相等，但不能獲取元素本身。使用鍵控散列，如果伺服器受到威脅，即使了解可能的元素也無濟於事。
- Alice 和 Bob 都將散列集發送到 Trend，最好已經排序以降低查找所有相等散列值的複雜性。
- Trend 將相等的雜湊值列表發送回給他們兩個。
- 在第二步中，您可以再次使用 Trend 或讓 Alice 和 bob 來確保它們確實具有相同的元素，而不僅僅是相同的雜湊值（不同的元素可能具有相同的雜湊值）。如果您使用 Trend，Alice 和 Bob 可以執行另一個密鑰交換，這次使用此密鑰使用對稱加密並將元素發送到 Trend。