CIS: Multiparty Computation

Cryptography and Information Security Group Research Project: Multiparty Computation

Multiparty computation allows a group of players to perform a given task as correctly and as privately as if a trusted third party has performed the computation on players behalf. In fundamental papers by Goldreich, Micali and Wigderson [GMW87] and Ben-Or, Goldwasser and Wigderson [BGW88] it was shown that any probabilistic (polynomial-time) function can be securely computed in the computational and in the information-theoretic settings. Ever since, many important papers have been produced and a lot of research is still going on in this fundamental area. In particular, the following issues are of critical importance: ability to compose secure protocols (e.g., sequential/parallel/concurrent reducibility), round and communication complexity, the network structure (e.g., existence of private channels, broadcast), adversary structure that can be tolerated (e.g., thereshold adversaries), types of adversary (e.g., active/passive/fail, adaptive/non-adaptive) and some others. As it is a big challenge to collect all the papers accumulated over time in the group, this page is going to grow with both the future as well as the past papers.

Recent Papers:

Yevgeniy Dodis and Silvio Micali.

"Parallel Reducibility for Information-Theoretically Secure Computation".

Abstract: Secure Function Evaluation (SFE) protocols are very hard to design, and reducibility has been recognized as a highly desirable property of SFE protocols. Informally speaking, reducibility (a.k.a. modular composition) is the automatic ability to break up the design of a complex SFE protocols into several simpler, individually secure components. Despite much effort, only the most basic type of reducibility, sequential reducibility (where only a single sub-protocol can be run at a time), has been considered and proven to hold for a specific class of SFE protocols. Unfortunately, sequential reducibility does not allow one to save on the number of rounds (often the most expensive resource in a distributed setting), and achieving more general notions is not easy (indeed, certain SFE notions provably enjoy sequential reducibility, but fail to enjoy more general ones).

In this paper, for information-theoretic SFE protocols, we

Formalize the notion of parallel reducibility, where sub-protocols can be run at the same time;
Clarify that there are two distinct forms of parallel reducibility:
- Concurrent reducibility, which applies when the order of the sub-protocol calls is not important (and reduces the round complexity dramatically as compared to sequential reducibility); and
- Synchronous reducibility, which applies when the sub-protocols must be executed simultaneously (and allows modular design in settings where sequential reducibility does not even apply).
Show that a large class of SFE protocols (i.e., those satisfying the modified definition of Micali-Rogaway) provably enjoy (both forms of) parallel reducibility.

Back to CIS Home Page