The round complexity of secure protocols

By Donald Beaver, Silvio Micali, Phillip Rogaway. 1990

Assume we have a network of three or more players, each player in possession of some private input. The players want to compute some function of these private inputs, but in a way which protects the privacy of each participant's contribution. Not all of the players can be trusted to do as they are instructed. The resources the players are given to accomplish their goal are communication--the ability to privately send messages to one another, or to broadcast messages to the community as a whole--and local computation. Many insightful protocols have been proposed for solving this problem of multiparty secure function evaluation. Building on Yao's protocol for the case of two players (Ya86), Goldreich, Micali and Wigderson (GMW87) offered the first general protocol for this problem, and they provided the paradigm on which a large body of successive work was based. Despite enormous progress, research on secure function evaluation has suffered from some serious shortcomings. First, though many protocols have been devised for solving the problem, what, exactly, these protocols accomplish has not been fully understood. In fact, no rigorously specified and generally accepted definitions have been proposed in this field. Second, protocols for multiparty secure function evaluation could be extremely inefficient, the main cause being that they required an unbounded (and usually large) number of communication rounds. We address both of these points, carefully crafting definitions which satisfactorily deal with the myriad of issues lurking here, and offering a new protocol for multiparty secure function evaluation--one which categorically improves the complexity requirements for this task. The new protocol completely divorces the computational complexity of the function being collaboratively computed from the round complexity of the protocol that evaluates it. Using this approach, we show that a rigorously-specified and extremely strong notion of secure function evaluation can be achieved by a protocol which requires only a fixed constant number of rounds of interaction. This result assumes only the existence of a one-way function and that the majority of the participants to the protocol behave correctly. (Copies available exclusively from MIT Libraries, Rm. 14-0551, Cambridge, MA 02139-4307. Ph. 617-253-5668; Fax 617-253-1690.)

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Prio: Private, Robust, and Scalable Computation of Aggregate Statistics (2017, background): “In theory, secure multi-party computation (MPC) protocols [11, 15, 68, 90, 123] allow a set of servers, with some”
Secure Multiparty Computation for Privacy-Preserving Data Mining (2009, background): “There exists a construction, due to Beaver, Micali, and Rogaway (5), which runs in a constant number of rounds.”
Foundations of garbled circuits (2012, methodology): “Our solution via type bits (the “point-and-permute” technique, which dates to Rogaway [51]) is well known.”
Generalizing the SPDZ Compiler For Other Protocols (2018, methodology): “Specifically, we integrated the honest-majority multiparty protocol of [24] for arithmetic circuits over a field, the three-party honest-majority protocol of [3, 4] for arithmetic circuits over the ring Z2n for any n, and the BMR protocol [6, 25] for constant-round multiparty computation for Boolean”
Secret charing vs. encryption-based techniques for privacy preserving data mining (2007, background): “Today we know that any computation which can be done in polynomial time by one party can be done securely by multiple parties[5].”
Random oracles are practical: a paradigm for designing efficient protocols (1993, background): “In another paper 29 the same authors use hash functions viewed as random oracles to give new secret key exchange schemes.”
Secure Two-Party Computation is Practical (2009, methodology): “FairplayMP, an extension of Fairplay to the case of more than two parties using a modified version of the protocol of Beaver et al. [3] has recently been released [4].”
SoK: General Purpose Compilers for Secure Multi-Party Computation (2019, methodology): “Fairplay was subsequently extended to allow for true multi-party computation in FairplayMP [14], using a modified version of the BMR protocol [9].”
Secure multiparty computation of approximations (2001, background): “Theorem 2.3 can also be generalized (with a larger, but still constant, number of rounds) to the case where the adversary is active [Lindell 2003] and to computations involving more than two parties [Beaver et al. 1990; Katz et al. 2003; Pass 2004].”
Cryptographic techniques for privacy-preserving data mining (2002, background): “REFERENCES [1] D. Beaver, S. Micali and P. Rogaway, The round complexity of secure protocols, Proc. of 22nd ACM Symposium on Theory of Computing (STOC), pp. 503-513, 1990.”
ABY2.0: Improved Mixed-Protocol Secure Two-Party Computation (2020, methodology): “The low-latency protocols are built using Yao’s garbled circuits (GC) [11, 72, 105, 106] and result in constant-round solutions.”
More Efficient Constant-Round Multi-Party Computation from BMR and SHE (2016, methodology): “Our protocol is based on the BMR approach [3].”
Non-interactive cryptocomputing for NC/sup 1/ (1999, methodology): “While employing basic new techniques, our method improves on previous results: Solutions which reduced interaction in multi-party secure circuit evaluation in the information theoretic model were shown in [2] for NC(1) circuits, whereas for computational security [4] showed how any polynomial size c”
Fast and Secure Three-party Computation: The Garbled Circuit Approach (2015, background): “The more general multiparty and constant-round variant of Yao’s garbled circuit was also studied in both the semi-honest setting [BMR90], and the malicious setting [DI05, IKP10].”
Secure multiparty protocols and zero-knowledge proof systems tolerating a faulty minority (2004, methodology): “Our approach is more general and provides a simpler approach than notions of fault-oracles proposed first as a definition of privacy by Galil et al. [18] and later extended to cover correctness as well, independently by Kilian et al. [30], [ 12 ], [26] and by Beaver [5].”