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.ICALP.2020.28
URN: urn:nbn:de:0030-drops-124351
Go to the corresponding LIPIcs Volume Portal

Chatterjee, Rohit ; Liang, Xiao ; Pandey, Omkant

Improved Black-Box Constructions of Composable Secure Computation

LIPIcs-ICALP-2020-28.pdf (0.6 MB)


We close the gap between black-box and non-black-box constructions of composable secure multiparty computation in the plain model under the minimal assumption of semi-honest oblivious transfer. The notion of protocol composition we target is angel-based security, or more precisely, security with super-polynomial helpers. In this notion, both the simulator and the adversary are given access to an oracle called an angel that can perform some predefined super-polynomial time task. Angel-based security maintains the attractive properties of the universal composition framework while providing meaningful security guarantees in complex environments without having to trust anyone.
Angel-based security can be achieved using non-black-box constructions in max(R_OT,Õ(log n)) rounds where R_OT is the round-complexity of semi-honest oblivious transfer. However, current best known black-box constructions under the same assumption require max(R_OT,Õ(log² n)) rounds. If R_OT is a constant, the gap between non-black-box and black-box constructions can be a multiplicative factor log n. We close this gap by presenting a max(R_OT,Õ(log n)) round black-box construction. We achieve this result by constructing constant-round 1-1 CCA-secure commitments assuming only black-box access to one-way functions.

BibTeX - Entry

  author =	{Rohit Chatterjee and Xiao Liang and Omkant Pandey},
  title =	{{Improved Black-Box Constructions of Composable Secure Computation}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{28:1--28:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Artur Czumaj and Anuj Dawar and Emanuela Merelli},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-124351},
  doi =		{10.4230/LIPIcs.ICALP.2020.28},
  annote =	{Keywords: Secure Multi-Party Computation, Black-Box, Composable, Non-Malleable}

Keywords: Secure Multi-Party Computation, Black-Box, Composable, Non-Malleable
Collection: 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Issue Date: 2020
Date of publication: 29.06.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI