Institute of Theoretical Informatics

Practical Secure Multi-Party Computation


The research area of secure multi-party computation has its origin in Yao's millionaire problem [Yao86]:

How can two mutually distrusting millionaires find out which of them is richer without revealing any further information to each other about the concrete value of their property?

In abstract terms, there are two parties (Alice and Bob); Alice knows a secret number x, Bob knows a secret number y, and they want to calculate which of the two numbers is greater. However, Bob is not supposed to learn anything more about x except the information whether x<y or x≥y, and analogously Alice is not supposed to learn anything more about y.

The generalization of this problem is quite obvious: Instead of the information whether x<y or x≥y, an arbitrary function f(x,y) is computed and more than two parties can participate in the computation (the function f must of course have many arguments). The security requirement in this general case is that no party P, even if it behaves arbitrarily maliciously, learns nothing about the secret input of the other parties, which cannot be calculated directly from the input of P and the public function result f(x,y,...).

In the literature there are different techniques and approaches for secure multi-party calculations, which are based on different security assumptions; e.g. that a majority of the participating parties honestly adhere to all prescribed procedures, or that a public key infrastructure is already initially in place.

Our research

We investigate the intersection between protocols that can be efficiently executed in practice and protocols that are provably secure in a model of interest to theorists. Protocols in the Universal Composability (UC) Framework are of particular interest to us, since they generally have the reputation of being inefficient due to their strong security guarantees. However, protocols in other frameworks are also considered.

In addition to tailor-made protocols for a specific problem, we are also interested in which basic modules can be used to perform general calculations as efficiently as possible.

Our teaching