下面的私有集合交集協議有問題嗎
假設愛麗絲有以下集合： $ {A_1,A_2,\ldots,An} $
Bob 有以下集合： $ {B_1,B_2,\ldots,B_m} $
愛麗絲創建一個密鑰 $ a $ 鮑勃創造了一把鑰匙 $ b $
這些密鑰應該是可交換的（例如：使用 RSA）
Alice 用 $ a $ 去創造 $ {A_{1’},A_{2’}, \ldots,A_{n’}} $
同樣 Bob 使 $ {B_{1’},B_{2’},\ldots,B_{m’}} $ 和 $ b $
Alice 將她的集合發送給 Bob，Bob 將他的集合發送給 Alice。
愛麗絲加密每個元素 $ {B_{1’},B_{2’},\ldots,B_{m’}} $ 有一個做 $ {B_{1"},B_{2"},\ldots,B_{m"}} $ 同樣 Bob 使 $ {A_{1"},A_{2"},\ldots,A_{n"}} $
現在 Alice 發送 $ {B_{1"},B_{2"},\ldots,B_{m"}} $ 給 Bob 和 Bob 發送 $ {A_{1"},A_{2"},\ldots,A_{n"}} $ 給愛麗絲。
因為鑰匙通勤，如果 $ Bi=Aj $ 對於一些 $ i $ 和 $ j $ ， 然後 $ Bi" = Aj" $
因此，Alice 和 Bob 都可以辨識出他們有哪些共同點。
此外，該協議只需要對每個元素進行兩次加密和通信，因此它具有 $ O(n+m) $ 執行。
我無法在任何地方找到這個協議，它看起來很簡單，所以我認為它一定有問題。
這與可以追溯到以下工作的眾所周知的協議非常相似。
凱瑟琳梅多斯。在沒有持續可用的第三方的情況下使用的更有效的加密匹配協議。在 IEEE 安全和隱私研討會上。1986年
Bernardo A. Huberman、Matt Franklin 和 Tad Hogg。增強電子社區的隱私和信任。在 ACM 電子商務會議上。1999
它使用交換性質，即 $ (x^a)^b = (x^b)^a $ . 此 PSI 協議通常與以下修改一起使用：
- 通常使用 Diffie-Hellman 循環組而不是 RSA。這允許您發送緊湊的橢圓曲線元素（例如，256 位）而不是 RSA 組元素（例如，2048 位）。Diffie-Hellman 組清楚地為您提供了該協議所需的交換屬性。
此外，RSA 僅在使用相同模數時是可交換的。在這種情況下，誰選擇模數？可能任何一方都不應該知道因式分解。 2. 對原始項目求冪是不安全的。相反，它們應該首先在隨機預言下進行散列。
考慮 Alice 是否持有物品 $ x, x^2, x^3, \ldots $ 而鮑勃只持有物品 $ x $ . 然後鮑勃最終會學會 $ x^{ab}, (x^2)^{ab}, (x^3)^{ab}, \ldots $ . 他會認 $ x^{ab} $ 因為他有物品 $ x $ （這是我們所期望的）。但他也可以將其他值辨識為 $ (x^{ab})^2, (x^{ab})^3, \ldots $ , 並得出結論 $ x^2, x^3, \ldots $ 愛麗絲堅持。顯然這是對隱私的侵犯。
各方應計算 $ H(x)^{ab}, H(x^2)^{ab}, H(x^3)^{ab}, \ldots $ ， 在哪裡 $ H $ 是一個隨機預言機。 $ H $ 打破項目之間的代數關係，因此知道 $ H(x)^{ab} $ 不能幫助你預測 $ H(x^2)^{ab} $ . 3. RSA 假設和 CDH 假設為您提供以下屬性：“給定 $ H(x_1)^{ab}, \ldots, H(x_n)^{ab} $ 對於隨機/秘密 $ a $ , 很難計算 $ H(x^)^{ab} $ 為了 $ x^ \not\in{x_1, \ldots, x_n} $ ." 這對於 PSI 協議的安全性來說還不夠。我們實際上需要 $ H(x^*)^{ab} $ 被偽隨機給定 $ H(x_1)^{ab}, \ldots, H(x_n)^{ab} $ （不僅難以計算）。這可以通過假設 DDH 而不是 CDH 來實現，或者通過應用額外的隨機預言機來實現，以便 Alice 發送表單的值 $ H’(H(x)^{ab}) $ .