eprint.iacr.org will be offline for approximately an hour for routine maintenance again at 10pm UTC on Wednesday, April 17.

Paper 2013/499

Limits on the Power of Cryptographic Cheap Talk

Pavel Hubacek, Jesper Buus Nielsen, and Alon Rosen


We revisit the question of whether cryptographic protocols can replace correlated equilibria mediators in two-player strategic games. This problem was first addressed by Dodis, Halevi and Rabin (CRYPTO 2000), who suggested replacing the mediator with a secure protocol and proved that their solution is stable in the Nash equilibrium (NE) sense, provided that the players are computationally bounded. We show that there exist two-player games for which no cryptographic protocol can implement the mediator in a sequentially rational way; that is, without introducing empty threats. This explains why all solutions so far were either sequentially unstable, or were restricted to a limited class of correlated equilibria (specifically, those that do not dominate any NE, and hence playing them does not offer a clear advantage over playing any NE). In the context of computational NE, we classify necessary and sufficient cryptographic assumptions for implementing a mediator that allows to achieve a given utility profile of a correlated equilibrium. The picture that emerges is somewhat different than the one arising in semi-honest secure two-party computation. Specifically, while in the latter case every functionality is either “complete" (i.e., implies Oblivious Transfer) or “trivial" (i.e., can be securely computed unconditionally), in the former there exist some “intermediate" utility profiles whose implementation is equivalent to the existence of one-way functions.

Note: This is the full version of the paper in CRYPTO 2013.

Available format(s)
Publication info
A major revision of an IACR publication in CRYPTO 2013
correlated equilibriumcheap talksecure two-party computationsequential rationalityoblivious transferone-way functions
Contact author(s)
hubacek @ cs au dk
2013-08-15: received
Short URL
Creative Commons Attribution


      author = {Pavel Hubacek and Jesper Buus Nielsen and Alon Rosen},
      title = {Limits on the Power of Cryptographic Cheap Talk},
      howpublished = {Cryptology ePrint Archive, Paper 2013/499},
      year = {2013},
      note = {\url{https://eprint.iacr.org/2013/499}},
      url = {https://eprint.iacr.org/2013/499}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.