兩個叛徒可以安全地向對方透露自己嗎？

假設 Alice 是叛徒，並且懷疑 Bob 也可能是叛徒。如果鮑勃是叛徒，她想和他一起合謀，如果不是，她不想透露她是叛徒。是否有 Alice 和 Bob 可以參與的協議表明他們是：

1. 兩個叛徒
2. 不是兩個叛徒

有了受信任的第三方，這很容易。Alice 和 Bob 都向 TTP 透露了他們的叛徒/非叛徒身份，如果兩人都是叛徒，TTP 會告訴他們，如果他們中只有一個或沒有叛徒，TTP 只會說他們不是叛徒。

但是，沒有受信任的第三方有辦法嗎？

我做了一些研究，發現這可能是公平交換的一個例子，因此如果沒有 TTP，技術上是不可能的。我能找到的關於公平交換的大部分資訊都超出了我的想像，我認為這種情況可能是獨一無二的，因為它涉及對可能相同的資訊的協議，協議相當於 AND 操作。當然還有那種“這麼簡單的問題，怎麼可能做不到”的感覺。所以我不得不問。

但是，沒有受信任的第三方有辦法嗎？

當然，更簡單的解決方案之一可能是使用Yao 的亂碼電路協議來計算與門。請注意，實際使用原始協議在這裡可以做到，因為現代加速僅對大量 AND 很重要，並且惡意安全也將有些無用，因為不誠實的一方可以撒謊並聲稱 1 來了解對方的輸入位。

所以這是基本協議：

設置階段（僅由 Bob 執行）：

1. 挑選 $ 6 $ 隨機 128 位密鑰並呼叫它們 $ k_A^0,k_A^1,k_B^0,k_B^1,k_\land^0,k_\land^1 $ .
2. 定義加密方案 $ E_{k,k’}(m)=(r,F_k(r|0)\oplus F_{k’}(r|0)\oplus m,F_k(r|1)\oplus F_{k’}(r|1)\oplus 0^{128}) $ 在哪裡 $ F_k(m) $ 是單個 AES-128 分組密碼加密呼叫和 $ r $ 是一個新隨機選擇的 127 位值。每當第三個條目與重新計算的 AES 評估的 XOR 未產生 128 個零時，相應的解密函式就會返回錯誤。
3. 計算“亂碼表”，即compute $ T_{11}=E_{k_A^1,k_B^1}(k_\land^1) $ 和 $ T_{xy} = E_{k_A^x,k_B^y}(k_\land^0) $ 為了 $ x,y\in{0,1} $ 和 $ x\land y=0 $ .
4. 隨機排列四個表項，呼叫結果 $ T_0,\ldots, T_3 $ ，例如使用由密碼RNG提供的Fisher-Yates shuffle 。
5. 計算 $ H_0=H(r|k^0_\land) $ 和 $ H_1=H(r|k^1_\land) $ 使用您最喜歡的加密雜湊函式，例如 SHA-256 和一些 128 位隨機字元串 $ r $ .
6. 發送 $ T_0,\ldots, T_3,H_0,H_1 $ 給愛麗絲。

輸入階段（兩者之間執行）：

1. 鮑勃發送 $ k^x_B $ 到愛麗絲那裡 $ x $ 是他的輸入位。
2. Bob 還選擇了一個隨機的 Diffie-Hellman 密鑰（例如，對於 P-256），稱之為 $ t $ 並發送公共元素 $ T=[t]G $ 給愛麗絲。
3. Alice 選擇了她自己的 Diffie-Hellman 密鑰，稱之為 $ k $ , 併計算 $ K_c=[k]G, K_{1-c}=T-K_c $ 為她的秘密協議輸入位 $ c $ 並發送過來 $ K_0 $ 給鮑勃。
4. Bob 計算 $ K_1=T-K_0 $ 並選擇兩個新的 DH 密鑰 $ r_0,r_1 $ 和 $ R_0=[r_0]G, R_1=[r_1]G $ 並發送給愛麗絲 $ E_0=(R_0,H([r_0]K_0)\oplus k_A^0), E_1=(R_1,H([r_1]K_1)\oplus k_A^1) $ 使用您最喜歡的雜湊函式，例如 SHA-256
5. 愛麗絲選擇 $ E_c=(L,R) $ 從兩個接收到的與她的輸入比特對應的密文中 $ c $ 併計算 $ k_A^c=R\oplus H([k]L) $

注意：最後 4 步是我改編自“Efficient Oblivious Transfer Protocols”（2001）中 ​​Naor 和 Pinkas 的不經意傳輸協議。

計算（由 Alice 執行）

Alice 現在嘗試解密亂碼表的所有 4 個條目 $ T_0,T_3 $ 使用 $ k_A^c $ 和 $ k_B^x $ . 只有一個解密應該成功恢復 $ k_\land $ .

輸出交換（在 Alice 和 Bob 之間執行）

1. 愛麗絲發送 $ k_\land $ 對於 Bob，Bob 現在通過將值與 $ k_\land^0 $ 和 $ k_\land^1 $
2. 鮑勃發送 $ r $ 給愛麗絲，愛麗絲也可以通過重新計算來恢復評估位 $ H_0,H_1 $ 並檢查哪個雜湊匹配。

引用自：https://crypto.stackexchange.com/questions/81460