Paper 2020/1092

The Round Complexity of Secure Computation Against Covert Adversaries

Arka Rai Choudhuri, Vipul Goyal, and Abhishek Jain


We investigate the exact round complexity of secure multiparty computation (MPC) against *covert* adversaries who may attempt to cheat, but do not wish to be caught doing so. Covert adversaries lie in between semi-honest adversaries who follow protocol specification and malicious adversaries who may deviate arbitrarily. Recently, two round protocols for semi-honest MPC and four round protocols for malicious-secure MPC were constructed, both of which are optimal. While these results can be viewed as constituting two end points of a security spectrum, we investigate the design of protocols that potentially span the spectrum. Our main result is an MPC protocol against covert adversaries with variable round complexity: when the detection probability is set to the lowest setting, our protocol requires two rounds and offers same security as semi-honest MPC. By increasing the detecting probability, we can increase the security guarantees, with round complexity five in the extreme case. The security of our protocol is based on standard cryptographic assumptions. We supplement our positive result with a negative result, ruling out *strict* three round protocols with respect to black-box simulation.

Note: Full version of the paper appearing at SCN 2020.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. MAJOR revision.12th Conference on Security and Cryptography for Networks, SCN 2020
covert adversaryround complexity
Contact author(s)
achoud @ cs jhu edu
goyal @ cs cmu edu
abhishek @ cs jhu edu
2020-09-15: received
Short URL
Creative Commons Attribution


      author = {Arka Rai Choudhuri and Vipul Goyal and Abhishek Jain},
      title = {The Round Complexity of Secure Computation Against Covert Adversaries},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1092},
      year = {2020},
      doi = {10.1007/978-3-030-57990-6_30},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.