Paper 2018/156

A New Approach to Black-Box Concurrent Secure Computation

Sanjam Garg, Susumu Kiyoshima, and Omkant Pandey


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.

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.)

Available format(s)
Publication info
A major revision of an IACR publication in EUROCRYPT 2018
black-box constructionconcurrent securitymulti-party computationoblivious transfer
Contact author(s)
sanjamg @ berkeley edu
kiyoshima susumu @ lab ntt co jp
omkant @ cs stonybrook edu
2018-04-27: last of 2 revisions
2018-02-11: received
See all versions
Short URL
Creative Commons Attribution


      author = {Sanjam Garg and Susumu Kiyoshima and Omkant Pandey},
      title = {A New Approach to Black-Box  Concurrent Secure Computation},
      howpublished = {Cryptology ePrint Archive, Paper 2018/156},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.