如果各方可以輸出隨機比特，那麼 Cleve 的 1/r 下界關於拋硬幣協議的偏差如何成立？

我正在閱讀 Richard Cleve 1984 年關於硬幣翻轉協議的論文，他說，在各方可能過早中止並且誠實方被迫輸出一點的情況下，那麼誠實方可能會被迫至少有 1/ r 其中 r 是輪數。

最近，Moran、Naor、Segev 表明這個界限是漸近緊的。

雖然我大致理解了 Cleve 的證明，但我不理解當對方中止時一方輸出的選擇位是確定性的前提。既然是PPT，而且對方中止時會收到通知，那老實人就不能隨便扔個硬幣就輸出嗎？

在多方協議中，如果每個誠實方都只是輸出一個隨機位，那麼他們很可能不會都輸出相同的位，並且協議會不正確。

有了兩方，腐敗的一方仍然可以偏向輸出。假設當實際協議輸出為 1 時，腐敗方在最後一輪中止。如果發生中止，誠實方會輸出一個隨機位。然後我們有兩種情況，每種情況都發生 $ 1/2 $ 可能性：

• 中止，隨機輸出 $ b \leftarrow {0,1} $
• 不中止，輸出 $ b=0 $

顯然輸出 0 的機率是 $ 3/4 $ ，所以還是有偏差的。

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