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

<p>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 <a href="http://cseweb.ucsd.edu/~russell/format.ps" rel="nofollow">http://cseweb.ucsd.edu/~russell/format.ps</a> : </p>

<p>Let $\mathcal A$ be the strategy that:</p>

<p>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$.</p>

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

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

<p>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:</p>

<ul>
<li><p>$E_1$ : Estimate of expected value where preceding conversation is fixed, and  $(x_{j+1}, \ldots x_k)$ is fixed.</p></li>
<li><p>$E_2$ : Estimate of expected value where preceding conversation is fixed, and  $(x'_{j+1}, \ldots x'_k)$ is fixed.</p></li>
</ul>

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

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2012-10-25T23:04:34.263Z
2012-10-25T23:45:23.600Z
2012-10-25T23:45:23.600Z
Søren Haagerup
<p>I am studying Coin Flipping protocols in cryptography, and the complexity of problems related to this.</p>

<p>Here, a question has come to my mind: <em>Does there exist a public coin, coin flipping protocol?</em>. 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.</p>

<p>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)?</p>

<p>In other words:</p>

<p><strong>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:</strong></p>

<ul>
<li>$\Pr[\phi(U_X,U_Y) = 1] = \frac{1}{2}$, where $U_X, U_Y$ are uniform distributions on $\{0,1\}^k$</li>
<li><p>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:</p>

<ul>
<li><p>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}$</p></li>
<li><p>The same should hold where the $x$'s are uniform and $y$'s are chosen by $\mathcal A$</p></li>
</ul></li>
</ul>

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

CC BY-SA 3.0
2012-10-25T02:09:04.413Z
I am starting to believe that this can be answered to the negative, since one will be able to apply the attack by Impagliazzo (http://cseweb.ucsd.edu/~russell/format.ps page 71) - I will look at this tomorrow, and write a detailed conclusion which might be of interest to others.
Søren Haagerup
CC BY-SA 3.0
2012-10-25T06:03:42.217Z
Comment -> answer, @RickyDemer ?
Suresh Venkat
CC BY-SA 3.0
2012-10-25T20:59:37.910Z
The negligible function $\gamma$ needs to be able to depend on the adversarial strategy. The correct definition should say: there is a circuit family $\phi$ whose nominal output distribution is unbiased, and for every PPT adversarial strategy $\mathcal{A}$ there is a negligible function $\mu$ such that $\phi(\mathcal{A},\mathcal{U}_k)$ has bias at most $\mu(k)$. This is the standard way to write a crypto definition, and it will rule out Ricky's attack from above.
mikero
CC BY-SA 3.0
2012-10-26T18:21:24.580Z
@mikero: According to this note, http://cseweb.ucsd.edu/~mihir/papers/negligible.ps the same negligible function used for all adversaries is equivalent to using different negligible functions for each adversary... Is there something I miss here?
Søren Haagerup
CC BY-SA 3.0
2012-10-27T02:38:59.710Z
@Søren: That is a nice result that I hadn't seen before. I think there are two subtleties here, though. First is that your initial definition said something like "There exists circuit family $\phi$ and negligible function $\gamma$ so that the bias achieved by all adversaries is *less than* $\gamma$" instead of saying "*eventually less than*'' as required for this Bellare result (this was then exploited by Ricky above). Second, if you consider non-uniform adversaries then the result of Bellare doesn't apply (you would need a limiting function for an *uncountable* set of negligible functions).
mikero
CC BY-SA 3.0
2012-10-27T02:46:26.363Z
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
CC BY-SA 3.0
2012-10-27T10:50:21.423Z
@mikero: Thank you for your answer - it is certainly important to note the "eventually less than" condition :-). Usually when working with negligible functions, the nice thing is the following: "The fact that "for every p(n), negligible(n) is eventually less than 1/p(n)" is hidden in the definition of negligible, so we can just use *sharp* inequality when calculating with negligible functions."  But for this nice property to hold, you actually need a new negligible function for every adversary - very important insight, so thanks again! :-)
Søren Haagerup
<cc.complexity-theory><cr.crypto-security>
Is there a Boolean formula that is resistant to bias from a polytime adversary?
Søren Haagerup
# Is there a Boolean formula that is resistant to bias from a polytime adversary?

(Asked by: username_0 on 2012-10-25)

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

**Tags:** cc.complexity-theory, cr.crypto-security

> **Comments:**
> **username_0**: I am starting to believe that this can be answered to the negative, since one will be able to apply the attack by Impagliazzo (http://cseweb.ucsd.edu/~russell/format.ps page 71) - I will look at this tomorrow, and write a detailed conclusion which might be of interest to others.  
> **username_1**: Comment -> answer, @RickyDemer ?  
> **username_2**: The negligible function $\gamma$ needs to be able to depend on the adversarial strategy. The correct definition should say: there is a circuit family $\phi$ whose nominal output distribution is unbiased, and for every PPT adversarial strategy $\mathcal{A}$ there is a negligible function $\mu$ such that $\phi(\mathcal{A},\mathcal{U}_k)$ has bias at most $\mu(k)$. This is the standard way to write a crypto definition, and it will rule out Ricky's attack from above.  
> **username_0**: @username_2: According to this note, http://cseweb.ucsd.edu/~mihir/papers/negligible.ps the same negligible function used for all adversaries is equivalent to using different negligible functions for each adversary... Is there something I miss here?  
> **username_2**: @Søren: That is a nice result that I hadn't seen before. I think there are two subtleties here, though. First is that your initial definition said something like "There exists circuit family $\phi$ and negligible function $\gamma$ so that the bias achieved by all adversaries is *less than* $\gamma$" instead of saying "*eventually less than*'' as required for this Bellare result (this was then exploited by Ricky above). Second, if you consider non-uniform adversaries then the result of Bellare doesn't apply (you would need a limiting function for an *uncountable* set of negligible functions).  
> **username_2**: 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.  
> **username_0**: @username_2: Thank you for your answer - it is certainly important to note the "eventually less than" condition :-). Usually when working with negligible functions, the nice thing is the following: "The fact that "for every p(n), negligible(n) is eventually less than 1/p(n)" is hidden in the definition of negligible, so we can just use *sharp* inequality when calculating with negligible functions."  But for this nice property to hold, you actually need a new negligible function for every adversary - very important insight, so thanks again! :-)  

---

## 1 answers

### Answer by username_0 on 2012-10-25. Score: 4 | Accepted answer

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.


---

