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 14 Feb 2018

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

Available format(s): PDF | BibTeX Citation

Note: This is a preliminary full version.

Version: 20180214:082337 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]