License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2020.71
URN: urn:nbn:de:0030-drops-117560
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/11756/
Applebaum, Benny ;
Brakerski, Zvika ;
Garg, Sanjam ;
Ishai, Yuval ;
Srinivasan, Akshayaram
Separating Two-Round Secure Computation From Oblivious Transfer
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 |
