International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

On Fully Secure MPC with Solitary Output

Authors:
Shai Halevi
Yuval Ishai
Eyal Kushilevitz
Nikolaos Makriyannis
Tal Rabin
Download:
DOI: 10.1007/978-3-030-36030-6_13
Search ePrint
Search Google
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.
BibTeX
@article{tcc-2019-29977,
  title={On Fully Secure MPC with Solitary Output},
  booktitle={Theory of Cryptography},
  series={Lecture Notes in Computer Science},
  publisher={Springer},
  volume={11891},
  pages={312-340},
  doi={10.1007/978-3-030-36030-6_13},
  author={Shai Halevi and Yuval Ishai and Eyal Kushilevitz and Nikolaos Makriyannis and Tal Rabin},
  year=2019
}