Constant-Round Maliciously Secure Two-Party Computation in the RAM Model

Carmit Hazay, Avishay Yanai

Sanjam Garg, Divya Gupta, Peihan Miao +1 more

Yehuda Lindell

Yehuda Lindell

Yehuda Lindell

Abstract. In this paper we show that any two-party functionality can be securely computed in a constant number of rounds, where security is obtained against malicious adversaries that may arbitrarily deviate from the protocol specification. This is in contrast to Yao’s constant-round protocol that ensures security only in the face of semi-honest adversaries, and to its malicious adversary version that requires a polynomial number of rounds. In order to obtain our result, we present a constant-round protocol for secure coin-tossing of polynomially many coins (in parallel). We then show how this protocol can be used in conjunction with other existing constructions in order to obtain a constant-round protocol for securely computing any two-party functionality. On the subject of coin-tossing, we also present a constant-round perfect coin-tossing protocol, where by “perfect ” we mean that the resulting coins are guaranteed to be statistically close to uniform (and not just pseudorandom). 1

Xiao Shaun Wang, Samuel Ranellucci, Jonathan I. Katz

We propose a simple and efficient framework for obtaining efficient constant-round protocols for maliciously secure two-party computation. Our framework uses a function-independent preprocessing phase to generate authenticated information for the two parties; this information is then used to construct a single "authenticated" garbled circuit which is transmitted and evaluated. We also show how to efficiently instantiate the preprocessing phase with a new, highly optimized version of the TinyOT protocol by Nielsen et al.