Paper 2016/818

Composable Adaptive Secure Protocols without Setup under Polytime Assumptions

Carmit Hazay and Muthuramakrishnan Venkitasubramaniam


All previous constructions of general multiparty computation protocols that are secure against adaptive corruptions in the concurrent setting either require some form of setup or non-standard assumptions. In this paper we provide the first general construction of secure multi-party computation protocol without any setup that guarantees composable security in the presence of an adaptive adversary based on standard polynomial-time assumptions. We prove security under the notion of ``UC with super-polynomial helpers'' introduced by Canetti et al. (FOCS 2010), which is closed under universal composition and implies ``super-polynomial-time simulation''. Moreover, our construction relies on the underlying cryptographic primitives in a black-box manner. Next, we revisit the zero-one law for two-party secure functions evaluation initiated by the work of Maji, Prabhakaran and Rosulek (CRYPTO 2010). According to this law, every two-party functionality is either trivial (meaning, such functionalities can be reduced to any other functionality) or complete (meaning, any other functionality can be reduced to these functionalities) in the Universal Composability (UC) framework. As our second contribution, assuming the existence of a simulatable public-key encryption scheme, we establish a zero-one law in the adaptive setting. Our result implies that every two-party non-reactive functionality is either trivial or complete in the UC framework in the presence of adaptive, malicious adversaries.

Available format(s)
Publication info
Published by the IACR in TCC 2016
UC SecurityAdaptive Secure ComputationCoin-TossingBlack-box constructionExtractable CommitmentsZero-One Law
Contact author(s)
carmit hazay @ biu ac il
2016-08-29: last of 2 revisions
2016-08-26: received
See all versions
Short URL
Creative Commons Attribution


      author = {Carmit Hazay and Muthuramakrishnan Venkitasubramaniam},
      title = {Composable Adaptive Secure Protocols without Setup under Polytime Assumptions},
      howpublished = {Cryptology ePrint Archive, Paper 2016/818},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.