### 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.

Available format(s)
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
Short URL
https://ia.cr/2020/116

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.