How to Solve any Multi-Party Protocol Problem

Webpage for a paper by Oded Goldreich, Silvio Micali and Avi Wigderson


Material available on-line


Assuming the existence of trapdoor permutations, one can construct protocols for securely computing any desirable multi-party functionality. This result either require a majority of honest players or allow dishonest players to suspend the execution (while being detected as bad). In the former case, the protocol can tolerate adversarial behaviour of any minority, and no minority can learn from the execution more than it can learn from its own inputs and the value of the function. In the latter case, the only additional damage that the adversary (which controls half or more of the parties) can obtain is prevent the honest parties from obtaining the output value (but the adversary's decision is oblivious of the inputs of the honest parties). Loosely speaking, in both cases, the protocol simulates a trusted party in an environment in which no party can be trusted.

The above result uses zero-knowledge proofs for any NP-statement as well as additional ideas.


Back to Oded Goldreich's homepage.