Report

Teaser, summary, work performed and final results

Periodic Reporting for period 2 - IMPaCT (Implementing Multi-Party Computation Technology)

Teaser

Multi-party computation (MPC) deals with the problem of jointly computing a function with input obtained from a set of distinct (possibly mutually distrusting) parties. It has a long story in the cryptographic literature, with the origins being found way back in the early...

Summary

Multi-party computation (MPC) deals with the problem of jointly computing a function with input obtained from a set of distinct (possibly mutually distrusting) parties. It has a long story in the cryptographic literature, with the origins being found way back in the early 1980s, with the work of Yao [Yao]. The basic scenario is that a group of parties wish to compute a given function on their private inputs. For example, suppose we have three parties Alice, Bob and Charlie. Alice has input x, Bob has input y and Charlie has input z. They want to compute the value of the function F(x,y,z) = max(x,y,z). To do so the parties engage in a protocol, by exchanging messages, and thus obtain the output of the desired function. The goal is that the output of the protocol is just the value of the function. All that the parties can learn is what they can learn from the output and their own input. So in the above example, if the output is z, then Charlie learns that his z is the maximum value, whereas Alice and Bob learn (if x, y and z are distinct), that their input is not equal to the maximum, and that the maximum held is equal to z. The basic scenario can be easily generalised to where the parties have several inputs and outputs, and the function outputs different values to different parties.

The goal of IMPaCT is to turn Multi-Party Computation (MPC) from the current stage of development, in which we are beginning to obtain practical feasibility results, to a stage in which we have fully practical systems. It has long been acknowledged that MPC has the potential to provide a transformative change in the way security solutions are enabled. As it presently stands this is currently only possible in some applications. Limited deployments are beginning to emerge; examples include a distributed database by Cybernetica (Estonia), a auction system by Partisia (Denmark), a threat mitigation system by Unbound Tech (Israel) and a datasystem by SAP (Germany). However, in turning MPC into a fully practical technology a number of key scientific challenges need to be solved; many of which have not yet even been considered in the theoretical literature. The IMPaCT project aims to address this scientific gap, bridge it, and so provide the tools for a future road-map in which MPC can be deployed as a widespread tool; as ubiquitous as encryption and digital signatures are today.

One can now claim that the practical feasibility of MPC has been established. The next task is to scale up the potential application areas, as well as the performance and data throughput of MPC systems. At the same time we need to be able to scientifically assess the performance of such systems without needing to deploy them; we need to understand how to improve performance for important practical problem; we need to be able to deal with more realistic run time environments such as asynchronous networks; we need to quantify the additional security obtained from utilizing MPC; and we need to examine how different (less stringent) adversary structures can enable a step change in performance. Thus whilst feasibility is established a lot of basic research still needs to be done.

Our scientific approach will be to investigate new MPC protocols and techniques which take into account practical constraints and issues which would arise in future application scenarios. Our work, despite being scientifically rigorous and driven from deep theoretical insight, will be grounded in practical considerations. All systems and protocols proposed will be prototyped so as to ensure that practical real world issues are taken into account. In addition we will use our extensive industrial linkages to ensure a two way dialogue between potential users and the developers of MPC technology; thus helping to embed future impact of the work in IMPaCT.

Work performed

\"
A major component of the work so far has been the development of the SCALE-MAMBA open source MPC system. We use this system to benchmark and validate a number of our results. This system derive from the earlier SPDZ system we developed at the University of Bristol. However, using work in IMPaCT this has been expanded to a number of other types of MPC protocol. In particular this has been used to develop our techniques related to different access structures, and in addition to look at combining different types of MPC application.

The system has been incorporated into a secure database system called Jana by some collaborators in the United States, and the Jana system has been demonstrated in a number of application domains relevant to the US governments activity in \"\"Evidenced based policy making\"\". We have also had a number of companies interested in using our system to investigate possible commercial application around MPC. These companies have come from around the globe including China, France, Japan, Switzerland and the United States.
\"

Final results

We expect our work to continue along the lines in the original proposal, and also to broaden out to take into account the changing technical landscape. A main thrust in the coming year will be to integrate a number of different MPC engines within the SCALE-MAMBA system and allow the system to (semi) automatically choose which methodology is more effective in a given stage in the computation. This should provide a considerable performance boost, enabling wider applicability.