philh comments on Paper review: A Cryptographic Solution to a Game Theoretic Problem

[philh]

Note: it seems the paper itself is linked from your original blog, but not on LW? So for the benefit of LW readers, it’s: Dodis, Y., Halevi, S., & Rabin, T. (2000, August). A cryptographic solution to a game theoretic problem. In Annual International Cryptology Conference (pp. 112-130). Springer, Berlin, Heidelberg.

By using the techniques mentioned above, two players can then execute the following protocol:

I had trouble following this, but I think I get it. To add some maybe-helpful clarifications:

1. At the beginning of the protocol, the Preparer randomly permutes the list, encrypts it element-wise and sends the resulting list to the Chooser.

Ecrypting it elementwise means encrypting the components of the pairs separately, not just the list element separately. So if the list starts as $\left[\right(c_1,d_1),(c_2,d_2),(c_3,d_3\left)\right]$, it becomes $\left[\right(f\left(c_1\right),f\left(d_1\right)),(f\left(c_2\right),f\left(d_2\right)),(f\left(c_3\right),f\left(d_3\right)]$. The encryption is random, such that even if $c_1=c_2$, the encryptions $f\left(c_1\right)\ne f\left(c_2\right)$. That way you can’t look at the frequencies in the encrypted list.

1. The Chooser picks a random pair of ciphertexts (c, d) from the permuted list.

Here the Chooser picks one random list element, which is a pair of cyphertexts.

It then blinds c with 0 (i.e. makes a random encryption of the same plaintext), blinds d with a random blinding factor β, and sends the resulting pair of ciphertexts (e, f) back to the Preparer.

The blinding with 0 here is necessary so the Preparer won’t be able to recognize $c$, which would tell her what $d$ is.

[victorsintnicolaas]

Thanks for the additions, will note the original paper in future posts!