Cryptology ePrint Archive: Report 2020/1092

The Round Complexity of Secure Computation Against Covert Adversaries

Arka Rai Choudhuri and Vipul Goyal and Abhishek Jain

Abstract: 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.

Category / Keywords: cryptographic protocols / covert adversary, round complexity

Original Publication (with major differences): 12th Conference on Security and Cryptography for Networks, SCN 2020

Date: received 10 Sep 2020

Contact author: achoud at cs jhu edu,goyal@cs cmu edu,abhishek@cs jhu edu

Available format(s): PDF | BibTeX Citation

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

Version: 20200915:111623 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]