Report

Teaser, summary, work performed and final results

Periodic Reporting for period 2 - MPCPRO (Better MPC Protocols in Theory and in Practice)

Teaser

The classical formulation of the Multiparty Computation (MPC) problem considers n players. Each player holds some private input data, and the goal is to design a protocol that the players can execute to compute some output that depends on all n inputs. This should be done in...

Summary

The classical formulation of the Multiparty Computation (MPC) problem considers n players. Each player holds some private input data, and the goal is to design a protocol that the players can execute to compute some output that depends on all n inputs. This should be done in such a way that we can make sure the result is correct, and that the result is the only new information that is released, i.e., we want to keep the inputs as confidential as possible. A simple example of this the voting problem: each player secretly votes yes or no, and we want to find the total number of yes (and no) votes without revealing how each individual player voted.

It is an important goal for MPC protocols to maintain correctness and privacy even if some of the players collude - in order to learn more than they are supposed to, or make the result be incorrect. Such a collusion could also result from an external adversary breaking into some of the computers that form the system. After this point, the corrupted machines follow a common strategy dictated by the adversary. MPC protocols are known that allows us in principle to carry out any computation securely, using various cryptographic techniques, and this opens the door to a very large number of potential applications. Examples include:

1) auctions or procurement where players input bids and we want to find the winning bid - without compromising the privacy of the loosing players.
2) Confidential benchmarking where several companies in the same line of business want to compare their performance - without revealing data on their own business to the competitors.
3) Secure data mining where the goal is to extract statistics from several databases that hold personal information - without breaking privacy regulations by giving a single party access to all the data.

As illustrated by the examples, MPC can be seen as an enabling technology that allows us to build systems that could otherwise not be used for lack of privacy guarantees. Moreover, this type of distributed systems, where data can only be stolen by breaking into almost all the machines, seems to be one of the only viable defences against organised hacking and hostile intelligence services.

However, we still have a long way to go before secure computation can be used in large-scale applications: despite a very rapid improvement of the efficiency of MPC over the last 15 years, the performance of the best MPC protocol is currently roughly comparable to that of the Intel 80386 processor from the 90-ties. While further improvement is desirable, we do not understand very well the limitations on how efficient MPC can be. Another notable issue is that the theory of MPC has in some respects been unable to keep up with the rapid development, in particular with respect to our theoretical measures for efficiency of protocols.

To address these challenges, the MPCPRO project consist of three sub-projects: 1) Implementation of protocols and a new theory for their performance, 2) Development of new and more efficient MPC protocols, and 3) Lower bounds for performance of MPC.

Work performed

During the first half of the project, work has been performed on all three sub-projects. We give here some concrete and important examples of published work from the project.

• Ivan Damgård, Kasper Damgård, Kurt Nielsen, Peter Sebastian Nordholt, Tomas Toft: Confidential Benchmarking Based on Multiparty Computation. Proceedings of Financial Cryptography 2016.

This result falls in sub-project 1. The well-known SPDZ protocol is implemented and optimized for use in confidential benchmarking, where the idea is that a bank customer can be scored w.r.t. credit worthiness based on a large database containing data on his peers. The database learns nothing on the customer and the bank learns nothing except the score of the customer. This gets around legislation that would prevent the bank from getting access to the database and the database from learning the identity of the customer. It is shown that linear programming can be done inside MPC to solve the problem efficiently enough for practical use.

• Ivan Damgård, Jesper Buus Nielsen, Rafail Ostrovsky, Adi Rosén: Unconditionally Secure Computation with Reduced Interaction. Proceedings of EUROCRYPT 2016.

This result falls in subproject 3. Lower bounds are shown on the number of messages than must be sent in order for n parties to evaluate a non-trivial function of an input bit from each party (such as the AND), where everyone learns the result, where t parties are semi-honestly corrupt, and where unconditional security is required. Also matching upper bounds are shown for the case where t=1. In particular, for 3 parties to compute the AND of three bits with 1 corruption, 6 messages are necessary and sufficient.

• Ivan Damgård, Jesper Buus Nielsen, Antigoni Polychroniadou, Michael A. Raskin: On the Communication Required for Unconditionally Secure Multiplication. Proceedings of CRYPTO 2016.

This result falls in subproject 3. The concept of a gate-by-gate protocol is defined, a notion which includes all known protocols that have unconditional security and are efficient in the circuit size of the desired computation. Lower bounds are shown on the performance of gate-by-gate protocols implying that existing protocols are essentially optimal in this class w.r.t. to communication and rounds. As a result, we conclude that we need completely new ideas to improve on the known performance of unconditionally secure MPC.

• Ivan Damgård, Jesper Buus Nielsen, Michael Nielsen, Samuel Ranellucci: The TinyTable Protocol for 2-Party Secure Computation, or: Gate-Scrambling revisited. Proceedings of CRYPTO 2017.

This result falls in sub-projects 1 and 2. A new approach to secure computation of Boolean circuits in the preprocessing model is presented, based on precomputation of a table for each gate in the circuit. This is by far the simplest protocol in this model so far, and we obtain an implementation of secure computation of AES encryption that has the fastest amortized performance so far. We also obtain the best known asymptotic complexity for secure computation of general Boolean circuits.

Final results

In the first half of the project we have advanced state of the art very significantly in sub-project 3. We have shown that the current approach to information theoretic MPC has fundamental limitations, and that hence the best known solutions are essentially the best we can hope for using the known design pattern. Since this design pattern is used by every known efficient solution, we need to think about something fundamentally different. In this respect, the lower bounds we have shown give some hints as to how we can improve: they assume certain properties from the protocol in question, and we should hence look for protocols that do not have these properties, and hence might be faster than predicted by our bounds. We plan to investigate this in the last half of the project.
In terms of design and implementation of MPC protocols (sub-projects 1 and 2) we have also advanced state of the art significantly, for instance by setting a new world record for speed of secure AES computation. We will of course continue on this track, as it seems clear that the potential for MPC protocols that are faster in practice is far from exhausted.