Paper 2020/116

Separating Two-Round Secure Computation from Oblivious Transfer

Benny Applebaum, Zvika Brakerski, Sanjam Garg, Yuval Ishai, and Akshayaram Srinivasan

Abstract

We consider the question of minimizing the round complexity of protocols for secure multiparty computation (MPC) with security against an arbitrary number of semi-honest parties. Very recently, Garg and Srinivasan (Eurocrypt 2018) and Benhamouda and Lin (Eurocrypt 2018) constructed such 2-round MPC protocols from minimal assumptions. This was done by showing *a round preserving reduction* to the task of secure *2-party* computation of the oblivious transfer functionality (OT). These constructions made a novel non-black-box use of the underlying OT protocol. The question remained whether this can be done by only making black-box use of 2-round OT. This is of theoretical and potentially also practical value as black-box use of primitives tends to lead to more efficient constructions. Our main result proves that such a black-box construction is impossible, namely that non-black-box use of OT is necessary. As a corollary, a similar separation holds when starting with any 2-party functionality other than OT. As a secondary contribution, we prove several additional results that further clarify the landscape of black-box MPC with minimal interaction. In particular, we complement the separation from 2-party functionalities by presenting a complete 4-party functionality, give evidence for the difficulty of ruling out a complete 3-party functionality and for the difficulty of ruling out black-box constructions of 3-round MPC from 2-round OT, and separate a relaxed ``non-compact'' variant of 2-party *secret sharing* from 2-round OT.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. MAJOR revision.ITCS 2020
Keywords
secure multiparty computationblack-box reductionsoblivious transfer
Contact author(s)
zvika brakerski @ weizmann ac il
History
2020-02-06: received
Short URL
https://ia.cr/2020/116
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/116,
      author = {Benny Applebaum and Zvika Brakerski and Sanjam Garg and Yuval Ishai and Akshayaram Srinivasan},
      title = {Separating Two-Round Secure Computation from Oblivious Transfer},
      howpublished = {Cryptology ePrint Archive, Paper 2020/116},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/116}},
      url = {https://eprint.iacr.org/2020/116}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.