抗偏拋硬幣的不可能性 (Cleve'86) 及其與安全多方計算中現代公平概念的聯繫
在現代安全多方計算 (SMPC) 協議中（非正式地），公平和保證輸出傳遞(GOD) 的概念定義如下：
公平性：如果對手得到了協議的輸出，那麼每個誠實的一方也應該得到輸出。
上帝：誠實的各方應該始終獲得獨立於對抗行為的輸出。
據我了解 Cleve'86 的開創性論文，它證明了在誠實的少數派環境中，抗偏見的兩方拋硬幣協議是不可能的。特別是，Cleve86 表明，如果誠實方決定在對手中止時輸出，則存在一種對抗策略，其輸出將不等於理想拋硬幣協議的輸出。
令我困擾的是，有幾篇論文引用了Cleve86並指出在 2PC 中不可能有公平（現代的公平概念）協議。我無法將 Cleve86 結果與我們談論的目前公平概念聯繫起來 安全 MPC 協議。具體來說，Cleve86 沒有說明對手（無論何時中止）是否獲得有關協議輸出的任何資訊。
考慮一個協議，只要對手決定中止，誠實的一方就不會產生輸出。這個協議不公平嗎（現代的公平概念）？據我了解，Cleve86 結果不適用於這種情況。
首先，我將很快討論 Cleve 的結果，因為它有一個自然的概括，可能對您的理解有用。
讓 $ X\sim\mathcal{D} $ 是一些隨機變數。抽樣隨機變數的一個常見概念是拒絕抽樣。你有一些謂詞（返回真或假的函式） $ \phi $ ，並且您想要採樣 $ X\sim\mathcal{D} $ 這樣 $ \phi(X) $ 持有。這就是說你要採樣 $ X\sim\mathcal{D} $ 從條件分佈 $ X\sim\mathcal{D}\mid \phi(X) = \mathsf{true} $ . 您可以通過繼續採樣來做到這一點 $ X\sim\mathcal{D} $ 直到你得到一個 $ \phi(X) $ 持有。這大約需要 $ 1/\Pr_{X\sim\mathcal{D}}[\phi(X) = \mathsf{true}] $ 樣本（因此，如您所料，以低機率成立的謂詞需要“更多樣本”）。
Cleve 的結果只是注意到對手可以通過中止計算在互動式協議中做到這一點。假設您有一個互動式協議，其中每一輪都有一個人講話（如果您願意，您可以讓他們廣播內容），並且有 $ k $ 回合。然後在 $ (k-1) $ 第一輪，只有一個參與者（打電話給他們 $ P $ )在其餘協議期間*不會聽到其他參與者的任何消息。*他們已經知道他們的結果會是什麼。
為了證明公平的硬幣翻轉是不可能的，你只需要證明 $ P $ 可以拒絕對他們的輸出值進行採樣，直到它是他們想要的任何值，所以他們可以將相互共享的隨機變數（在計算結束時）固定為他們想要的任何值（但他們得到的結果的機率越低）想要發生的是，他們需要做的中止越多）。
為了證明公平計算是不可能的，你只需要證明 $ P $ 已經知道它們的價值，並且通過中止協議可以向協議中的其他方隱瞞相關資訊。
So the two results (impossibility of unbiased randomness generation in interactive protocols, and impossibility of fair computations) come from slightly different arguments, but both of them rely on the existence of one person who is “done with the computation but still needs to talk to other people so they can finish the computation”, which is intrinsic to interactive protocols of this form.
We can extend Cleve86 to contemporary notion of Fairness,
- A Fair protocol in two party setting implies GOD. Why? I will let you think about it.
- Cleve86 shows GOD is not possible in two party setting with malicious adversary.
- (1) and (2) implies it is not possible to do honest minority fair coin tossing with 2 party.
PS: I have concluded this after discussing with my collaborators. Thanks to them.