[GMW87] How to play ANY mental game

Authors: Oded Goldreich, Silvio Micali, Avi Wigderson | Venue: STOC 1987 | Source

Abstract

We present a polynomial-time algorithm that, given as a input the description of a game with \textit{incomplete information and any number of players}, produces a protocol for playing the game that leaks no partial information, provided the majority of the players is honest. Our algorithm automatically solves all the multi-party protocol problems addressed in complexity-based cryptography during the last 10 years. It actually is \textit{a completeness theorem} for the class of distributed protocols with honest majority. Such completeness theorem is optimal in the sense that, if the majority of the players is not honest, some protocol problems have no efficient solution [C].

BibTeX

Copy

@inproceedings{GMW87,
  author    = {Oded Goldreich and Silvio Micali and Avi Wigderson},
  title     = {How to Play {ANY} Mental Game or A Completeness Theorem for Protocols with Honest Majority},
  booktitle = {Proceedings of the 19th Annual ACM Symposium on Theory of Computing (STOC 1987)},
  pages     = {218--229},
  year      = {1987}
}