Parallel Reducibility for Information-Theoretically Secure Computation

Parallel Reducibility for Information-Theoretically Secure Computation

Yevgeniy Dodis and Silvio Micali.



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

[ postscript ] [ back to Yevgeniy Dodis' research interests ]