Paper 2019/1032

On Fully Secure MPC with Solitary Output

Shai Halevi, Yuval Ishai, Eyal Kushilevitz, 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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A minor revision of an IACR publication in TCC 2019
Keywords
Multi-Party ComputationFull SecurityDishonest MajorityMalicious AdversariesFairnessSolitary
Contact author(s)
n makriyannis @ gmail com
yuvali @ cs technion ac il
eyalk @ cs technion ac il
shaih @ alum mit edu
talrny @ yahoo com
History
2019-09-19: revised
2019-09-16: received
See all versions
Short URL
https://ia.cr/2019/1032
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/1032,
      author = {Shai Halevi and Yuval Ishai and Eyal Kushilevitz and Nikolaos Makriyannis and Tal Rabin},
      title = {On Fully Secure MPC with Solitary Output},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1032},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/1032}},
      url = {https://eprint.iacr.org/2019/1032}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.