這是閱讀論文“通過電話翻轉硬幣 - 解決不可能問題的協議”時提出的問題。

硬幣無偏的事實是基於這樣一個事實：如果 n 是兩個素數的乘積，那麼同餘應該正好有四個解 $ x^2 = f^2 \pmod n $ .

如果愛麗絲是惡意的並且故意想要將結果偏向於 $ n $ 是可因式分解的。在這種情況下，她可以使 $ n $ 由幾個素數（比方說，5）合成，那麼會有 $ 2^5 = 32 $ 解決方案，選擇解決方案很可能會導致 $ n $ 結果是可分解的？

請注意，協議的步驟 II 標題為“ALICE TESTS n”，其中包括 Alice 驗證 Bob 是否正確選擇了 n 的方法。這齣現在論文的第三頁。

$ n $ 似乎是由 Bob 或受信任的第三方挑選的：

正如 Lindell 已經提到的，n 也是由對方測試的。

選擇

這是使用不可延展承諾的替代協議：

• 愛麗絲和鮑勃承諾隨機 $ r_a, r_b \leftarrow {0,1} $
• Bob另外承諾結果 $ c $ 他們預測拋硬幣有
• 一切都被揭露了，如果鮑勃獲勝 $ r_a \oplus r_b = c $

如果任何一方是惡意的，他們就無法對結果產生有意義的影響，因為另一方的隨機性被添加到最終的硬幣翻轉中。

如果每條消息都經過簽名（連同一些成績單雜湊），您可能還可以向第三方（法院）證明執行的結果。

優化

猜測 $ c $ 可以優化掉：因為 $ r_a \oplus r_b $ 是均勻分佈的，而 Bob 不知道，猜測沒有意義。Bob 總能猜出一個固定值。

此外，正如 Lindell 在評論中提到的，Bob 不需要承諾他們的價值。

完整協議

為了完整起見，這裡有一個完整的協議：

• $ B \to A $ : 隨機數 $ n_B $
• $ A \to B $ : $ {B | n_A | n_B | \mathrm{Commit}(r_a)}_{sk_A} $
• $ B \to A $ : $ {A | n_A | n_B | r_b}_{sk_B} $
• $ A \to B $ : $ {B | n_A | n_B | r_a}_{sk_A} $

在哪裡 $ {x}{sk} $ 表示 $ x | \mathrm{Sign}{sk}(x) $ , 明文及其在簽名密鑰下的簽名 $ sk $ .

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