Alice 如何讓 Bob 在私有映射中查找值
我認為這個問題類似於私有集合交集，但在以下方面有所不同：
Alice 有一個廣泛的從說 id 到名稱的映射
id1 -> 約翰·多伊
id2 -> 簡·多伊
id3 -> 埃德加·坡
Bob 有一個 id 的候選名單
id1（愛麗絲知道這個人的名字）
id3（愛麗絲知道這個人的名字）
id4（愛麗絲不知道這個人的名字）
Bob 和 Alice 都不想彼此共享他們所有的數據資產。然而，Alice 已同意分享 Bob 知道其 id 的人的姓名。另一方面，Bob 不希望 Alice 知道他有哪個 id。
是否有任何已知的僅涉及兩方的安全協議？（不受信任的第 3 方等）
許多（大多數？）領先的 PSI 協議可以輕鬆適應以提供此功能。它有時被稱為“具有關聯數據的 PSI”或“具有數據傳輸的 PSI”。例如，您可以在以下內容中明確描述 PSI 的這種變體：
埃米利亞諾·德·克里斯託法羅和吉恩·圖迪克。具有線性複雜性的實用私有集合交叉協議。金融密碼學 2010。
甚至許多沒有明確提及“關聯數據”的協議也可以輕鬆修改以提供它。我確信以下論文（這是最快的 2 方半誠實 PSI）將支持它：
Benny Pinkas、Thomas Schneider、Gil Segev、Michael Zohner：定相：使用基於排列的散列的私有集合交集。使用 2015 年。
Vladimir Kolesnikov、Ranjit Kumaresan、Mike Rosulek、Ni Trieu：高效批量不經意 PRF 與私有集合交叉點的應用。 CCS 2016。
這些協議使用 PSI 的“遺忘 PRF”範式，其工作原理大致如下：
- 各方執行一個不經意的 PRF，其中 Alice 學習（描述）一個隨機函式 $ F $ 鮑勃學會了 $ F(y) $ 對於每個 $ y $ 在他的集合中。
- Alice 可以計算和發送 $ F(x) $ 對於每個 $ x $ 在他的集合中。現在 Bob 可以與他的集合進行比較 $ F $ -值並辨識交叉點。對於值 $ x $ Alice 有但 Bob 沒有，對應的 $ F(x) $ 值對 Bob 來說是隨機的，因此不會洩露任何相關資訊 $ x $ .
這些協議中有相當多的其他算法/組合的東西，但最終在某種程度上，協議正在做我上面描述的事情。
要將相關數據添加到此協議大綱，您只需使用 $ F(x) $ 值作為加密相關數據的密鑰。像這樣的東西：
- 對於每一個 $ y $ , 鮑勃有 $ F(y) $ 並且（如果不夠長）用 PRG 擴展它以獲得兩個值 $ tag_y $ 和 $ k_y $ .
- 對於每一個 $ x $ , Alice 同樣展開 $ F(x) $ 進入 $ tag_x $ 和 $ k_x $ . 她發 $ (tag_x, \mathsf{Enc}(k_x, data )) $ ， 在哪裡 $ data $ 是與鍵關聯的記錄/數據 $ x $ .
- Bob 可以查找以下形式的元組 $ (\tau, c) $ 在哪裡 $ \tau $ 是他認為的標籤 $ tag_y $ . 然後他可以解密 $ c $ 用對應的鍵 $ k_y $ 獲取與相關的數據 $ y $ .