1
$\begingroup$

Consider the following game between party 1 and party 2. Party 1 is honest; i.e. it follows the game exactly:

Assume that party 1 flips a fair coin $b$, encrypts it to $c$, and sends $c$ to party 2. Party 2 returns a value b'. Finally, party 1 reveals b by decrypting c.

Party 2 wins if b'=b, and loses otherwise. Assume that the encryption is not perfect; therefore $c$ reveals partial information about $b$, such that party 2 learns that there's a 60% chance that $b=0$. What strategy maximizes the winning chance of party 2?

I think the problem can be symbolically denoted as follows:

  1. $\Pr[b=0] = \Pr[b=1] = 0.5$
  2. $\Pr[b=0 \mid c] = 1-\Pr[b=1 \mid c]= 0.6$

and we want to choose \Pr[b'=0 \mid c] such that \Pr[b'=b \mid c] is maximized.

PS: The encryption used above is in fact a commitment scheme, but let's not care about that.

  • 0
    @Sadeq: you didn't say that party 2 got to choose $b'$ at will, but that is how I took it. When you ask for a strategy, that is implied. Given the 60% chance that $b=0$, and other strategy (unless you have other information) will have lower success.2011-06-23

0 Answers 0