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 homomorphic secret sharing from 2-round OT.
BibTeX - Entry
@InProceedings{applebaum_et_al:LIPIcs:2020:11756,
author = {Benny Applebaum and Zvika Brakerski and Sanjam Garg and Yuval Ishai and Akshayaram Srinivasan},
title = {{Separating Two-Round Secure Computation From Oblivious Transfer}},
booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
pages = {71:1--71:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-134-4},
ISSN = {1868-8969},
year = {2020},
volume = {151},
editor = {Thomas Vidick},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/11756},
URN = {urn:nbn:de:0030-drops-117560},
doi = {10.4230/LIPIcs.ITCS.2020.71},
annote = {Keywords: Oracle Separation, Oblivious Transfer, Secure Multiparty Computation}
}
Keywords: |
|
Oracle Separation, Oblivious Transfer, Secure Multiparty Computation |
Collection: |
|
11th Innovations in Theoretical Computer Science Conference (ITCS 2020) |
Issue Date: |
|
2020 |
Date of publication: |
|
06.01.2020 |