Multiparty-Computation

Alice 如何讓 Bob 在私有映射中查找值

  • July 19, 2018

我認為這個問題類似於私有集合交集,但在以下方面有所不同:

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”範式,其工作原理大致如下:

  1. 各方執行一個不經意的 PRF,其中 Alice 學習(描述)一個隨機函式 $ F $ 鮑勃學會了 $ F(y) $ 對於每個 $ y $ 在他的集合中。
  2. 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 $ .

引用自:https://crypto.stackexchange.com/questions/60918