Paper 2015/797

What Security Can We Achieve within 4 Rounds?

Carmit Hazay and Muthuramakrishnan Venkitasubramaniam

Abstract

Katz and Ostrovsky (Crypto 2004) proved that five rounds are necessary for stand-alone general black-box constructions of secure two-party protocols and at least four rounds are necessary if only one party needs to receive the output. Recently, Ostrovsky, Richelson and Scafuro (Crypto 2015) proved optimality of this result by showing how to realize stand-alone, secure two-party computation under general assumptions (with black-box proof of security) in four rounds where only one party receives the output, and an extension to five rounds where both parties receive the output. In this paper we study the question of what security is achievable for stand-alone two-party protocols within four rounds and show the following results: 1. A 4-round two-party protocol for coin-tossing that achieves 1/p-security (i.e. simulation fails with probability at most 1/p+negl), in the presence of malicious corruptions. 2. A 4-round two-party protocol for general functionalities where both parties receive the output, that achieves 1/p-security and privacy in the presence of malicious adversaries corrupting one of the parties, and full security in the presence of non-aborting malicious adversaries corrupting the other party. 3. A 3-round oblivious-transfer protocol that achieves 1/p-security against arbitrary malicious senders, while simultaneously guaranteeing a meaningful notion of privacy against malicious corruptions of either party. 4. Finally, we show that the simulation-based security guarantees for our 3-round protocols are optimal by proving that 1/p-simulation security is impossible to achieve against both parties in three rounds or less when requiring some minimal guarantees on the privacy of their inputs.

Note: The revised version of October 17,2015 includes a new protocol for oblivious transfer that achieves the strongest security notion achievable in three rounds, namely, it provides full privacy against both parties and 1/p security against a malicious sender. It also includes a new result that proves optimality of this new construction by providing a matching lower bound.