Cryptology ePrint Archive: Report 2019/1032

On Fully Secure MPC with Solitary Output

Shai Halevi and Yuval Ishai and Eyal Kushilevitz and Nikolaos Makriyannis and Tal Rabin

Abstract: We study the possibility of achieving full security, with guaranteed output delivery, for secure multiparty computation of functionalities where only one party receives output, to which we refer as solitary functionalities. In the standard setting where all parties receive an output, full security typically requires an honest majority; otherwise even just achieving fairness is impossible. However, for solitary functionalities, fairness is clearly not an issue. This raises the following question: Is full security with no honest majority possible for all solitary functionalities? We give a negative answer to this question, by showing the existence of solitary functionalities that cannot be computed with full security. While such a result cannot be proved using fairness based arguments, our proof builds on the classical proof technique of Cleve (STOC 1986) for ruling out fair coin-tossing and extends it in a nontrivial way. On the positive side, we show that full security against any number of malicious parties is achievable for many natural and useful solitary functionalities, including ones for which the multi-output version cannot be realized with full security.

Category / Keywords: cryptographic protocols / Multi-Party Computation, Full Security, Dishonest Majority, Malicious Adversaries, Fairness, Solitary

Original Publication (with minor differences): IACR-TCC-2019

Date: received 11 Sep 2019, last revised 19 Sep 2019

Contact author: n makriyannis at gmail com,yuvali@cs technion ac il,eyalk@cs technion ac il,shaih@alum mit edu,talrny@yahoo com

Available format(s): PDF | BibTeX Citation

Version: 20190919:181538 (All versions of this report)

Short URL: ia.cr/2019/1032


[ Cryptology ePrint archive ]