Cryptology ePrint Archive: Report 2018/156

A New Approach to Black-Box Concurrent Secure Computation

Sanjam Garg and Susumu Kiyoshima and Omkant Pandey

Abstract: We consider the task of constructing concurrently composable protocols for general secure computation by making only black-box use of underlying cryptographic primitives. Existing approaches for this task first construct a black-box version of CCA-secure commitments which provide a strong form of concurrent security to the committed value(s). This strong form of security is then crucially used to construct higher level protocols such as concurrently secure OT/coin-tossing (and eventually all functionalities).

This work explores a fresh approach. We first aim to construct a concurrently-secure OT protocol whose concurrent security is proven directly using concurrent simulation techniques; in particular, it does not rely on the usual ``non-polynomial oracles'' of CCA-secure commitments. The notion of concurrent security we target is super-polynomial simulation (SPS). We show that such an OT protocol can be constructed from polynomial hardness assumptions in a black-box manner, and within a constant number of rounds. In fact, we only require the existence of (constant round) semi-honest OT and standard collision-resistant hash functions.

Next, we show that such an OT protocol is sufficient to obtain SPS-secure (concurrent) multiparty computation (MPC) for general functionalities. This transformation does not require any additional assumptions; it also maintains the black-box nature as well as the constant round feature of the original OT protocol. Prior to our work, the only known black-box construction of constant-round concurrently composable MPC required stronger assumptions; namely, verifiable perfectly binding homomorphic commitment schemes and PKE with oblivious public-key generation.

Category / Keywords: black-box construction, concurrent security, multi-party computation, oblivious transfer

Original Publication (with major differences): IACR-EUROCRYPT-2018

Date: received 8 Feb 2018, last revised 27 Apr 2018

Contact author: sanjamg at berkeley edu, kiyoshima susumu@lab ntt co jp, omkant@cs stonybrook edu

Available format(s): PDF | BibTeX Citation

Note: A bug in the proof was fixed. (Concretely, the simulator was modified so that it aborts the simulation when it detects failures, and the analysis of the simulator was modified accordingly.)

Version: 20180427:070919 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]