Paper 2020/494

Improved Black-Box Constructions of Composable Secure Computation

Rohit Chatterjee, Xiao Liang, and Omkant Pandey


We close the gap between black-box and non-black-box constructions of $\mathit{composable}$ secure multiparty computation in the plain model under the $\mathit{minimal}$ assumption of semi-honest oblivious transfer. The notion of protocol composition we target is $\mathit{angel\text{-}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 $\mathit{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_{\mathsf{OT}},\widetilde{O}(\log n))$ rounds where $R_{\mathsf{OT}}$ is the round-complexity of the semi-honest oblivious transfer. However, currently, the best known $\mathit{black\text{-}box}$ constructions under the same assumption require $\max(R_{\mathsf{OT}},\widetilde{O}(\log^2 n))$ rounds. If $R_{\mathsf{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_{\mathsf{OT}},\widetilde{O}(\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.

Note: Full version version of the original publication.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Major revision. The 47th International Colloquium on Automata, Languages and Programming (ICALP 2020)
Secure Multi-Party ComputationBlack-BoxComposableNon-Malleable
Contact author(s)
rochatterjee @ cs stonybrook edu
liang1 @ cs stonybrook edu
omkant @ cs stonybrook edu
2020-04-28: received
Short URL
Creative Commons Attribution


      author = {Rohit Chatterjee and Xiao Liang and Omkant Pandey},
      title = {Improved Black-Box Constructions of Composable Secure Computation},
      howpublished = {Cryptology ePrint Archive, Paper 2020/494},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.