Imposibility of bias-resistant coin tossing (Cleve'86) and its connection to modern notion of fairness in Secure Multiparty Computation

Question

In modern Secure Multi-party Computation (SMPC) protocols (informally) the notion of Fairness and Guaranteed Output Delivery (GOD) is defined as follows:

Fairness: If the adversary gets the output of the protocol, every honest party should get the output as well.

GOD: Honest parties should always get the output independent of adversarial behavior.

As I understand the seminal paper of Cleve'86, it proves that bias-resistant two party coin tossing protocol is not possible in honest minority setting. In particular, Cleve86 shows that if the honest party decides to output when the adversary aborts, then there exists an adversarial strategy where the output will not be equivalent to the output of the ideal coin tossing protocol.

What bothers me is that several paper cites Cleve86 and state that it is not possible to have fair (modern notion of fairness) protocol in 2PC. I am not able to connect Cleve86 result to current notion of fairness we talk about it Secure MPC protocols. Specifically, Cleve86 do not say anything about whether the adversary (whenever it aborts) gets any information about the output of the protocol or not.

Consider a protocol where honest party do not produce an output whenever the adversary decides to abort. Is this protocol not fair (with modern notion of fairness)? In my understanding, Cleve86 result is not applicable to this scenario.

Answer 1

First, I'll discuss Cleve's result really quickly, as there's a natural generalization of it which may be useful for your understanding.

Let $X\sim\mathcal{D}$ be some random variable. A common notion in sampling random variables is rejection sampling. You have some predicate (function which returns true or false) $\phi$, and you want to sample $X\sim\mathcal{D}$ such that $\phi(X)$ holds. This is to say that you want to sample $X\sim\mathcal{D}$ from the conditional distribution $X\sim\mathcal{D}\mid \phi(X) = \mathsf{true}$. You can do this by continuing to sample $X\sim\mathcal{D}$ until you get one where $\phi(X)$ holds. This takes roughly $1/\Pr_{X\sim\mathcal{D}}[\phi(X) = \mathsf{true}]$ samples (so predicates that hold with low probability require "more samples", as you'd expect).

Cleve's result is just noting that an adversary can do this in an interactive protocol via aborting the computation. Say you have an interactive protocol where each round a single person talks (you can let them broadcast things if you want), and there are $k$ rounds. Then in the $(k-1)$th round, there's a single participant (call them $P$) who will not hear anything from other participants during the rest of protocol. They already know what their result will be.

To show that fair coinflipping is impossible, you just need to argue that $P$ can rejection-sample on their output value until it is whatever they want it to be, so they can fix the mutually-shared random variable (at the end of the computation) to be whatever they want (but the lower-probability the result they want to occur is, the more aborts they need to do).

To show that fair computation is impossible, you just need to argue that $P$ already knows their value, and via aborting the protocol can withhold relevant information from the other parties in the protocol.

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.

Answer 2

We can extend Cleve86 to contemporary notion of Fairness,

1. A Fair protocol in two party setting implies GOD. Why? I will let you think about it.
2. Cleve86 shows GOD is not possible in two party setting with malicious adversary.
3. (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.