## 1/*p*-Secure Multiparty Computation without
Honest Majority and the Best of Both Worlds

**Amos Beimel, Yehuda Lindell, Eran Omri, and Ilan Orlov**

*
Ben Gurion University;
Bar Ilan University;
Bar Ilan University; and
Ben Gurion University*
**Abstract.** A protocol for computing a functionality is secure if an
adversary in this protocol cannot cause more harm than in an ideal computation,
where parties give their inputs to a trusted party which returns
the output of the functionality to all parties. In particular, in the ideal
model such computation is fair – all parties get the output. Cleve (STOC
1986) proved that, in general, fairness is not possible without an honest
majority. To overcome this impossibility, Gordon and Katz (Eurocrypt
2010) suggested a relaxed definition—1/*p*-secure computation—which
guarantees partial fairness. For two parties, they construct 1/*p*-secure
protocols for functionalities for which the size of either their domain or
their range is polynomial (in the security parameter). Gordon and Katz
ask whether their results can be extended to multiparty protocols.

We study 1/*p*-secure protocols in the multiparty setting for general
functionalities. Our main result is constructions of 1/*p*-secure protocols that
are resilient against any number of corrupt parties provided that the
number of parties is constant and the size of the range of the functionality
is at most polynomial (in the security parameter n). If less than
2/3 of the parties are corrupt, the size of the domain is constant, and
the functionality is deterministic, then our protocols are efficient even
when the number of parties is log log n. On the negative side, we show
that when the number of parties is super-constant, 1/*p*-secure protocols
are not possible when the size of the domain is polynomial. Thus, our
feasibility results for 1/*p*-secure computation are essentially tight.

We further motivate our results by constructing protocols with stronger
guarantees: If in the execution of the protocol there is a majority of
honest parties, then our protocols provide full security. However, if only
a minority of the parties are honest, then our protocols are 1/*p*-secure.
Thus, our protocols provide the best of both worlds, where the 1/*p*-security is
only a fall-back option if there is no honest majority.