2026-07-22T09:00:55Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11756 2024-03-06T10:48:38Z ddc:004 open_access

Separating Two-Round Secure Computation From Oblivious Transfer Applebaum, Benny Brakerski, Zvika Garg, Sanjam Ishai, Yuval Srinivasan, Akshayaram Oracle Separation Oblivious Transfer Secure Multiparty Computation 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Benny Applebaum and Zvika Brakerski and Sanjam Garg and Yuval Ishai and Akshayaram Srinivasan 2020 Is Part Of LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2020.71 urn:nbn:de:0030-drops-117560 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.71 eng https://creativecommons.org/licenses/by/3.0/legalcode