社會主義百萬富翁變體，只有一 方學習x=yX=是x=y?
在社會主義百萬富翁協議中，愛麗絲選擇了一些 $ x $ Bob 選擇了一些 $ y $ , 並且雙方都知道是否 $ x=y $ 不學習對方的選擇值。然而，在一場成功的比賽中，雙方確實會了解對方的價值——這與他們自己的價值相同。是否存在只有一方學習的變體協議（或欺騙現有協議的方式） $ x=y $ 而對方什麼都沒學到？
我的特殊情況是這樣的：
- Bob 有一小部分人邀請他參加他的生日聚會。
- Bob 很高興讓人們通過 Socialist Millionaires 交換逐項查詢他的整個列表，以查看列表中是否包含特定人。但是，他不想批發出整個清單。
- 愛麗絲暗戀查理，想知道查理是否被邀請參加聚會。她可以通過讓鮑勃參與社會主義百萬富翁交換鮑勃列表中的每一項來了解答案。
- 然而，她不希望Bob 知道她對 Charlie 的邀請感興趣。如果 Charlie 在 Bob 的列表中，Bob 將看到他和 Alice 參與了匹配交換，以獲取他的 Charlie 條目。
Alice 是否可以在 Bob 不知道列表中的任何特定項目是否匹配的情況下學習“Charlie”與 Bob 列表中的每個項目的相等性？
換句話說，我認為這可以通過全同態加密來完成，例如：
- Bob 用 Alice 的公鑰加密他列表中的每個項目
- 愛麗絲發送她對“查理”的請求也用她的公鑰加密
- Bob 對每個加密列表項與 Alice 的加密查詢進行同態相等比較（即，Bob 執行 $ map $ 基於每個項目的同態相等比較，將加密列表轉換為加密布爾列表）
- Bob 發回一個同態加密布爾值列表，描述每個比較的匹配狀態
- 愛麗絲用她的私鑰解密鮑勃的回复
這個案例滿足了我的要求（我認為？） Bob 什麼都學不到，因為他既不能解密 Alice 的查詢，也不能解密他自己的同態相等比較的結果。
有沒有辦法使用零知識證明交換獲得類似的保證？
協議由輪流發送消息的各方組成。因此，一方自然會先於另一方學習輸出（此規則僅存在極少數例外）。這意味著在您發現的幾乎所有協議中（尤其是在半誠實的設置中），您都會看到（1）最後一個協議消息實際上只不過是學習者輸出向其對應方揭示輸出的一方（因此您可以排除此消息）或（2）協議已被描述，因此只有一方獲得輸出。在諸如 Wikipedia 文章之類的文章中，將 MPC 協議描述為“雙方都獲得輸出”通常更簡單，但在幕後通常存在單方面的輸出。
（在您引用的維基百科文章中，該協議的編寫方式掩蓋了互動模式。各方之間的最後一次通信在步驟 7 中“ $ \langle Q_a Q_b^{-1} | \alpha,\beta\rangle $ ”。但是這一步是 Diffie-Hellman 的抽象，它由來自每一方的消息組成。只需讓一方忽略此消息，他/她將是唯一能夠學習輸出的人。）
私人集合交叉協議（PSI——社會主義百萬富翁的概括）也不例外。在我們的論文中：
Vladimir Kolesnikov、Ranjit Kumaresan、Mike Rosulek、Ni Trieu：高效批量不經意 PRF 與私有集合交叉點的應用。 CCS 2016。
（以及我知道的所有其他 PSI 論文）我們描述了協議，以便只有一方獲得輸出。
該協議的建構塊是一種稱為“私人成員資格測試”的東西，其中發件人有一組 $ S $ 物品中，接收者有物品 $ v $ ，並且只有接收者知道是否 $ v \in S $ . 這聽起來正是您正在尋找的。
這個私人會員測試建構塊可以追溯到這項工作（也許更早）：
Benny Pinkas、Thomas Schneider、Michael Zohner：基於 OT 擴展的更快的私有集合相交。使用 2014 年。
這兩篇論文都經過優化，可以提供許多私有成員測試建構塊原語的實例，因為這是 PSI 所需要的。如果您真的只想要一個私人成員資格測試實例，那麼可能沒有什麼比基於經典 Diffie-Hellman 的 PSI 更簡單的了（如果您只需要半誠實的安全性，同態加密就過分了）。我在下面描述它，專門針對愛麗絲只有一件物品的情況。
- 愛麗絲（誰有一個項目 $ v $ ) 選擇隨機指數 $ \alpha $ 並發送 $ H(v)^\alpha $ . 這裡 $ H $ 是一個隨機預言機。
- Bob（他有一組物品 $ S $ ) 選擇隨機指數 $ \beta $ 並發送 $ (H(v)^\alpha)^\beta $ 也 $ H(s)^\beta $ 對於每個 $ s \in S $ .
- 愛麗絲可以計算 $ (H(s)^\beta)^\alpha $ 並檢查這些值是否等於 $ (H(v)^\alpha)^\beta $ . 這會發生當且僅當 $ v \in S $ （除非發生可忽略不計的碰撞 $ H $ ).