Cryptology ePrint Archive: Report 2020/494

Improved Black-Box Constructions of Composable Secure Computation

Rohit Chatterjee and Xiao Liang and Omkant Pandey

Abstract: 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.

Category / Keywords: cryptographic protocols / Secure Multi-Party Computation, Black-Box, Composable, Non-Malleable

Original Publication (with major differences): The 47th International Colloquium on Automata, Languages and Programming (ICALP 2020)

Date: received 27 Apr 2020

Contact author: rochatterjee at cs stonybrook edu,liang1@cs stonybrook edu,omkant@cs stonybrook edu

Available format(s): PDF | BibTeX Citation

Note: Full version version of the original publication.

Version: 20200428:121842 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]