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.