Secure multi-party computation

From CryptoDox, The Online Encyclopedia on Cryptography and Information Security

In cryptography, secure multi-party computation is a problem that was initially suggested by Andrew C. Yao in a 1982 paper ^[1]. In that publication, the millionaire problem was introduced: Alice and Bob are two millionaires who want to find out which is richer without revealing the precise amount of their wealth. Yao proposed a solution allowing Alice and Bob to satisfy their curiosity while respecting the constraints.

This problem and result gave way to a generalization called multi-party computation (MPC) protocols. In a MPC, we have a given number of participants p1, p2, ..., pN, each having a private data, respectively d1, d2, ..., dN. The participants want to compute the value of a public function F on N variables at the point (d1, d2, ..., dN). A MPC protocol is dubbed secure if no participant can learn more from the description of the public function and the result of the global calculation than what he/she can learn from his/her own entry - under particular conditions depending on the model used.

Like many cryptographic protocols, the security of an MPC protocol can rely on different assumptions:

• It can be computational (i.e. based on some mathematical problem, like factoring) or unconditional (usually with some probability of error which can be made arbitrarily small).
• The model in which the scheme is described might assume that participants use a synchronized network (a message sent at a "tick" always arrives at the next "tick"), that a secure and reliable broadcast channel exists, that a secure communication channel exists between every pair of participants (an adversary cannot read, modify or generate messages in the channel), etc.
• The centrally controlled adversary considered can be passive (only allowed to read the data of a certain number of participants) or active (can corrupt the execution protocol or a certain number of participants).
• An adversary can be static (chooses its victims before the start of the multi-party computation) or dynamic (can chose its victims during the course of execution of the multiparty computation). Attaining security against a dynamic adversary is often much harder than security against a static adversary.
• An adversary can be defined as a threshold structure (meaning that it can corrupt or simply read the memory of a number of participants up to some threshold), or be defined as a more complex structure (it can affect certain predefined subsets of participants, modeling different possible collusions). These structures are commonly referred to as adversary structures. The opposite set consisting of the sets of honest parties that can still execute a computational task is related to the concept of access structures.

An important primitive in MPC is oblivious transfer.

Unconditionally or Information Theoretic Secure multi-party computations are closely related to the problem of secret sharing, and more specifically verifiable secret sharing (VSS); every secure MPC protocol that protects against active adversaries uses VSS.

Secure MPC provides solutions to various real-life problems such as distributed voting, private bidding and auctions, sharing of signature or decryption functions, private information retrieval, etc.

Two-Party Computation

The sub-problem of MPC that has received special attention by researchers because of its close relation to many cryptographic tasks is secure two-party computation (2PC). This area of research is concerned with the question: 'Can two party computation be achieved more efficiently and under weaker security assumptions than general MPC?'

References

1. ↑ Andrew Chi-Chih Yao: Protocols for Secure Computations (Extended Abstract) FOCS 1982: 160-164

External links

• Helger Lipmaa's links about multiparty computation
• Nick Szabo, "The God Protocols"
• Secure distributed CSP (DisCSP) solvers — a web-application with an applet-interpreter to design and run your own full-fledged secure multiparty computation (based on the SMC declarative language). Uses secure arithmetic circuit evaluation and mix-nets.
• The Fairplay Project — Includes a software package for secure two-party computation, where the function is defined using a high-level function description language, and evaluated using Yao's protocol for secure evaluation of boolean circuits.