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

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}$.

• The answer is yes. $\;\;\;\;$ Set $\:k=0\:$, $\:$ $\:\phi()=0\:$, $\:$ and $\;\; \gamma \: = \: k\mapsto \frac1{1+2^k} \;\;$. $\;\;\;\;$ Since $0$ is always $\hspace{.3 in}$ within $\frac1{2+0}$ of $\frac12$, your conditions hold. $\;\;\;\;$ It would be much more interesting to ask if there $\hspace{.3 in}$ exists a PPT-uniform family of circuits $\:\langle \phi_0,\phi_1,\phi_2,\phi_3,...\rangle\:$ satisfying your conditions. – user6973 Oct 25 '12 at 2:16
• Now the answer is no. $\;\;$ Since $\gamma$ is negligible, there exists $k$ such that $\: \gamma(k) < \frac13 \:$. $\;\;$ Have $k_{\hspace{.015 in}0}$ be $\hspace{.02 in}$ the least such $k$. $\;\;$ Consider the game in which players X and Y take turns assigning the least $\hspace{.2 in}$ of their variables in $\phi_k$ that they did not already assign, with player 1 winning if the output is 1 $\hspace{.1 in}$ and player 2 winning if the output is 0. $\:$ Since that game is perfect information, (continued ...) – user6973 Oct 25 '12 at 18:34
• (... continued) one of the players has a winning strategy. $\;\;$ Consider the adversary which, if $\: k = k_{\hspace{.015 in}0} \:$ and the adversary has the role of the player with the winning strategy, then the adversary uses that strategy, otherwise the adversary always plays 0. $\;\;$ That adversary runs in polynomial time, but when $\: k = k_{\hspace{.015 in}0} \:$ it biases the bit by $\frac12$, which is, by construction, more than $\gamma(k_{\hspace{.015 in}0})$. – user6973 Oct 25 '12 at 18:37
• It would be much more interesting to ask if for all PPT adversaries, the bias $\hspace{1.5 in}$ produced by that adversary is negligible. $\:$ – user6973 Oct 25 '12 at 18:39
• Bellare seems to address the situation for non-uniform adversaries, though. So disregard that subtlety. The first one still holds though -- you can fix one negligible function for all adversaries, provided that you only require their bias to eventually (rather than always) be less than that bound. – mikero Oct 27 '12 at 2:46

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.