Practical Secure Multi-Party Computation

Description

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 anything 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

We offer the lecture "Cryptographic Protocols" every summer semester. In addition to building blocks such as commitments, zero-knowledge proofs, and oblivious transfer protocols, it introduces in particular different approaches to achieve secure multiparty computation and discusses their security. We assume basic knowledge in cryptography as taught in the lecture "Theoretical Foundations of Cryptography", which is offered every winter semester.

We also irregularly offer the lecture "Cryptographic Voting Schemes". Based on the use case of the election of parties or persons, the requirements for cryptographic voting schemes are discussed and protocols tailored to this use case are presented and analyzed. Initial knowledge of signatures, commitments, hash functions, zero-knowledge proofs and public-key encryption is assumed. We recommend the lecture "Theoretical Foundations of Cryptography", which is offered annually in the winter semester.

References:

[Yao86] Andrew Chi-Chih Yao: How to Generate and Exchange Secrets (Extended Abstract). FOCS 1986: 162-167