What Security Can We Achieve In 4-Rounds?

In this paper we study the question of what security is achievable for stand-alone two-party computa-tion in four rounds. Our starting point point is the Katz-Ostrovsky lower bound [KO04] which determines that the exact round complexity of achieving secure two-party computation with black-box simulation is five. To get around this lower bound we consider two relaxations of the standard simulation-based security definition, where each relaxation implies a different security guarantee. Specifically, we analyze our four-round protocols in the presence of malicious non-aborting adver-saries (i.e. which do not abort prematurely) for which we obtain full simulation security and malicious aborting adversaries for which we obtain 1/p security (which implies that the simulation fails with proba-bility at most 1/p+negl) while guaranteeing full privacy against both parties. We realize the coin-tossing and oblivious transfer functionalities under these relaxations, and present protocols with different secu-rity guarantees. We also provide a tight characterization of when 1/p security is achievable where full privacy is expected