Cryptology ePrint Archive: Report 2020/1428

On Statistical Security in Two-Party Computation

Dakshita Khurana and Muhammad Haris Mughees

Abstract: There has been a large body of work characterizing the round complexity of general-purpose maliciously secure two-party computation (2PC) against probabilistic polynomial time adversaries. This is particularly true for zero-knowledge, which is a special case of 2PC. In fact, in the special case of zero knowledge, optimal protocols with unconditional security against one of the two players have also been meticulously studied and constructed.

On the other hand, general-purpose maliciously secure 2PC with statistical or unconditional security against one of the two participants has remained largely unexplored so far. In this work, we initiate the study of such protocols, which we refer to as 2PC with one-sided statistical security. We settle the round complexity of 2PC with one-sided statistical security with respect to black-box simulation by obtaining the following tight results: In a setting where only one party obtains an output, we design 2PC in $4$ rounds with statistical security against receivers and computational security against senders. In a setting where both parties obtain outputs, we design 2PC in $5$ rounds with computational security against the party that obtains output first and statistical security against the party that obtains output last.

Katz and Ostrovsky (CRYPTO 2004) showed that 2PC with black-box simulation requires at least $4$ rounds when one party obtains an output and $5$ rounds when both parties obtain outputs, even when only computational security is desired against both parties. Thus in these settings, not only are our results tight, but they also show that statistical security is achievable at no extra cost to round complexity. This still leaves open the question of whether 2PC can be achieved with black-box simulation in $4$ rounds with statistical security against senders and computational security against receivers. Based on a lower bound on computational zero-knowledge proofs due to Katz (TCC 2008), we observe that the answer is negative unless the polynomial hierarchy collapses.

Category / Keywords: cryptographic protocols / Statistical security, Two-party computation

Original Publication (with major differences): IACR-TCC-2020

Date: received 14 Nov 2020

Contact author: dakshita at illinois edu,mughees2@illinois edu

Available format(s): PDF | BibTeX Citation

Version: 20201115:074655 (All versions of this report)

Short URL: ia.cr/2020/1428


[ Cryptology ePrint archive ]