Efficiency in Secure Multi-Party Computations

Status

This project started in September 2004 and ended in December 2008.

Researchers

• Prof. Dr. Ueli Maurer
• Zuzana Beerliova
• Dr. Martin Hirt
• Vassilis Zikas

Research Problem and Background

Cooperation among parties that do not necessarily trust each other is a common problem in business and government administration contexts and will become more important in the emerging information economy. Examples include business negotiations, collective decision making (e.g. voting), auctioning, contract signing, or the joint computation of statistical data.

The topic of this project is secure cooperation in a distributed environment among parties that neither trust each other nor have a common party they all trust.

Secure multi-party computation (MPC) is a crucial technique in this context as it allows the simulation of a trusted party. However, known protocols for MPC are either highly inefficient, especially in terms of the communication complexity, or they are targeted to very specific problems (like voting). This projects aims at devising new models and protocols, bridging the gap from theory to practice.

Objectives and Plan

• Study the various communication models and adversary models for MPC and relate them to each other.
• Propose techniques for reducing communication costs of MPC protocols, for example based on the optimistic execution of protocols, the elimination of cheating parties, etc.
• Devise models with less theoretical security but little security degradation in practice. Goal: real-life security under realistic assumptions.
• Develop efficient protocols with ``best-possible'' security.
• Develop a better understanding of the primitives used in MPC.

Summary of the Results

Multi-party computation (MPC) enables a set of n mutually distrusting players to perform some computation on their private inputs, such that the correctness of the output as well as the privacy of the honest players' inputs is guaranteed even in the presence of an adversary corrupting up to t of the players and making them misbehave arbitrarily.

In this project, we focused on the efficiency of multi-party computation protocols, and presented the following contributions:

• The main efficiency bottleneck in MPC is the computation of the multiplication gates. However, since recently, for t<n/3 multiplication can be reduced to non-robust generation of correct sharings of secret random values. We present a novel technique which allows to perfectly and very efficiently generate such random sharings. Based on this technique, we construct a perfectly secure MPC protocol for t<n/3, communicating O(n kappa) bits per multiplication (where kappa denotes the bit-length of a value).
• An efficient way of limiting the number of times when the adversary can disturb (and slow down) the computation is player elimination -- every time an inconsistency is detected, a pair of players, at least one of them corrupted, is localized and eliminated. However, honest players can get eliminated as well, which causes several limitations of this technique. We generalize and extend the player elimination-technique, by finding other means (than elimination) of preventing localized players from disturbing the computation ever again. Our new technique, called dispute control, allows to construct efficient MPC protocols in settings where player elimination is not applicable: We present an actively secure MPC protocol that provides optimal security (unconditional security against a faulty minority) and communicates only O(n^2 kappa) bits per multiplication.
• Byzantine agreement (BA) is an MPC primitive which allows the players to agree on a particular value. It is used as a building block in any distributed protocols, and hence its efficiency is of particular importance. Known information-theoretically secure BA protocols with optimal resilience are very involved and inefficient -- the most efficient known BA protocol requires O(n^{17} kappa) bits of communication. We propose a new, conceptually simpler BA protocol communicating O(n^5 kappa) bits per BA.
• Lastly, we concentrate on MPC in asynchronous networks, where there is no upper bound on message delay. Known MPC protocols for the asynchronous setting suffer from two main disadvantages: they tend to have substantially higher communication complexity, and they do not allow to take the inputs of all honest players. We propose a solution to both these problems. We present a perfectly secure asynchronous MPC protocol that communicates only O(n^3 kappa) bits per multiplication. Furthermore, we extend the protocol for a hybrid communication model, allowing all players to give input if the very first round of the communication is synchronous, and taking at least n-t inputs in a fully asynchronous setting.

All four mentioned contributions are optimal in all security parameters, i.e., achieve statistical security where t<n/2, and achieve perfect security where t<n/3 (respectively t<n/4 in the asynchronous world).

Papers and Conference Talks

• Zuzana Beerliova-Trubiniova and Martin Hirt
  Efficient Multi-Party Computation with Dispute Control
  Theory of Cryptography -TCC '2006, Lecture Notes in Computer Science, Springer-Verlag, vol. 3876, pp. 305-328, Mar 2006
  The paper was presented at the third Theory of Cryptography Conference (TCC 2006), March 4-7 2006, Columbia University New York, NY USA.

• Zuzana Beerliova-Trubiniova and Martin Hirt
  Simple and Efficient Perfectly-Secure Asynchronous MPC
  Advances in Cryptology - ASIACRYPT 2007, Lecture Notes in Computer Science, Springer-Verlag, vol. 4833, pp. 376-392, 2007
  The paper was presented at ASIACRYPT 2007, December 2 - 6 2007, Kuching, Sarawak, MALAYSIA.

• Zuzana Beerliova-Trubiniova, Martin Hirt, and Micha Riser
  Efficient Byzantine Agreement with Faulty Minority
  Advances in Cryptology - ASIACRYPT 2007, Lecture Notes in Computer Science, Springer-Verlag, vol. 4833, pp. 393 - 409, 2007
  The paper was presented at ASIACRYPT 2007, December 2 - 6 2007, Kuching, Sarawak, MALAYSIA.

• Zuzana Beerliova-Trubiniova and Martin Hirt
  Perfectly-Secure MPC with Linear Communication Complexity
  Theory of Cryptography - TCC 2008, Lecture Notes in Computer Science, Springer-Verlag, vol. 4948, pp. 213-230, Mar 2008
  The paper was presented at the fifth Theory of Cryptography Conference (TCC 2008), March 19-21 2008, New York University, NY, USA.

• Zuzana Beerliova-Trubiniova, Matthias Fitzi, Martin Hirt, Ueli Maurer, and Vassilis Zikas
  MPC vs. SFE: Perfect Security in a Unified Corruption Model
  Theory of Cryptography - TCC 2008, Lecture Notes in Computer Science, Springer-Verlag, vol. 4948, pp. 231-250, Mar 2008.
  The paper was presented at the fifth Theory of Cryptography Conference (TCC 2008), March 19-21 2008, New York University, NY, USA.