Paper 2017/942

On Secure Two-Party Computation in Three Rounds

Prabhanjan Ananth and Abhishek Jain


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.

Available format(s)
Publication info
A major revision of an IACR publication in TCC 2017
secure computationround complexity
Contact author(s)
prabhanjan va @ gmail com
abhishek @ cs jhu edu
2017-09-27: revised
2017-09-27: received
See all versions
Short URL
Creative Commons Attribution


      author = {Prabhanjan Ananth and Abhishek Jain},
      title = {On Secure Two-Party Computation in Three Rounds},
      howpublished = {Cryptology ePrint Archive, Paper 2017/942},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.