Is there a Boolean formula that is resistant to bias from a polytime adversary?

Question

I am studying Coin Flipping protocols in cryptography, and the complexity of problems related to this.

Here, a question has come to my mind: Does there exist a public coin, coin flipping protocol?. Usual coin flipping protocols (as invented by Manuel Blum) involve that one party hides its random value by a bit commitment, and later makes it public. The coin-function is then just an XOR of the two bits.

Is it possible to drop the bit commitment part, and instead put the "hardness" into the coin function (i.e. something much harder than XOR)?

In other words:

Does there exists a PPT uniform family of circuits $\phi(x_1,\ldots, x_k, y_1 \ldots, y_k)$ for $k\in \mathbb N$, such that there for any PPT adversary $\mathcal A$ exists a negligible function $\gamma(k)$, such that the family of circuits (under certain computational assumptions) have the following properties:

• $\Pr[\phi(U_X,U_Y) = 1] = \frac{1}{2}$, where $U_X, U_Y$ are uniform distributions on $\{0,1\}^k$

• Consider the function as the output of the following protocol: Alice decides the $x_i$ bits, and Bob decides the $y_i$ bits, and Alice wants $\phi$ to be 1 and Bob wants 0, and the bits have to be published in order $(x_1, y_1, x_2, y_2 , \ldots, x_k, y_k)$. $\phi$ should be resistant to more than negligible bias, when applying $\mathcal A$ against opponent that choses its bits uniformly. In other words:

  • When the variables are chosen in the following manner: Let $x_1$ be chosen by $\mathcal A$. Let $y_1$ be chosen uniformly. Let $x_2$ be chosen by $\mathcal A$ using the knowledge of $(x_1,y_1)$. Let $y_2$ be chosen uniformly, and so on. Then the expected outcome of $\phi$ should be within $\gamma(k)$ of $\frac{1}{2}$

  • The same should hold where the $x$'s are uniform and $y$'s are chosen by $\mathcal A$

As a remark, one can see that the truth of this statement: $ \exists x_1 \forall y_1 \ldots \exists x_k \forall y_k : \phi(x_1, \ldots, x_k, y_1, \ldots, y_k)$ correspond to the fact, that there exists a strategy for Party 1 to bias completely by $\frac{1}{2}$.

Answer 1

There does not exist such a family of circuits. Assume to the contrary that $\{\phi_k\}_{k \in \mathbb N}$ was such a family.

We will now show the strategy that achieves bias at least $\frac{1}{20k}$ for $k$ big enough, by referring to Impagliazzo's Theorem 4.7.2 on page 71 of http://cseweb.ucsd.edu/~russell/format.ps :

Let $\mathcal A$ be the strategy that:

1) Picks a bit string uniformly from $x \in \{0,1\}^k$, and picks a number $ i \in \{0,\ldots,2k-1\}$ uniformly. Now, $i = 2j+b$, for $b \in \{0,1\}$ for an unique $j$ and $b$.

2) $\mathcal A$ should send the first $j$ messages in correspondance with the first $j$ coordinates of $x$.

3) If $b=0$ Then $\mathcal A$ should wait for answer from the other party. Otherwise, it should just proceed:

4) $\mathcal A$ picks a new bit string $(x'_{j+1}, \ldots x'_k) \in \{ 0,1 \}^{k-j}$ uniformly, and then calculate 2 estimates of the Expected value of $\phi$, calculated by making polynomially many uniform samples from $\{0,1\}^{k-j-b}$ corresponding to the remaining conversation of the honest party:

• $E_1$ : Estimate of expected value where preceding conversation is fixed, and $(x_{j+1}, \ldots x_k)$ is fixed.

• $E_2$ : Estimate of expected value where preceding conversation is fixed, and $(x'_{j+1}, \ldots x'_k)$ is fixed.

5) The bit string corresponding to the highest expected value, is used for the rest of the conversation.

If assuming perfect estimation of expected value, we achieve at least $\frac{1}{16k}$ bias, and since there is some (exponentially decreasing error) caused by the estimation (which can be bounded by additive Chernoff-Hoeffding bound), we just say a bias of at least $\frac{1}{20k}$ for $k$ big enough.

For now, I will just refer to Impagliazzo's proof for the analysis. It is not the easiest proof to read, if one is not used to his style of writing, but it is correct, and I can explain specific details, if anybody have interest.