Cryptology ePrint Archive: Report 2017/942

On Secure Two-Party Computation in Three Rounds

Prabhanjan Ananth and Abhishek Jain

Abstract: We revisit the exact round complexity of secure two-party computation. While four rounds are known to be sufficient for securely computing general functions that provide output to one party [Katz-Ostrovsky, CRYPTO'04], Goldreich-Krawczyk [SIAM J. Computing'96] proved that three rounds are insufficient for this task w.r.t. black-box simulation.

In this work, we study the feasibility of secure computation in three rounds using non-black-box simulation. Our main result is a three-round two-party computation protocol for general functions against adversaries with auxiliary inputs of bounded size. This result relies on a new two round input-extraction protocol based on succinct randomized encodings.

We also provide a partial answer to the question of achieving security against non-uniform adversaries. Assuming sub-exponentially secure iO and one-way functions, we rule out three-round protocols that achieve polynomial simulation-based security against the output party and exponential indistinguishability-based security against the other party.

Category / Keywords: secure computation, round complexity

Original Publication (with major differences): IACR-TCC-2017

Date: received 25 Sep 2017, last revised 27 Sep 2017

Contact author: prabhanjan va at gmail com, abhishek@cs jhu edu

Available format(s): PDF | BibTeX Citation

Version: 20170927:141031 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]