Honest Majority and Beyond: Efficient Secure Computation over Small Population

Abstract

Secure Multi-Party Computation for small population has witnessed notable practically-efficient works in the setting of both honest majority and dishonest majority. While honest majority provides the promise of stronger security goals of fairness (either all parties get the output or none of them do) and guaranteed output delivery (honest parties always get the output irrespective of adversary’s behaviour), the best that dishonest majority can offer is unanimous abort (either all honest parties get the output or none of them do). In this work, we consider the computation among 4 parties in two different threat models. To avoid clutter and enable ease of understanding, we segregate the thesis into two parts (one for each threat model). Part I considers the standard honest majority (i.e. 1 corruption) where we provide constant-round (lowlatency) protocols in a minimal model of pairwise private channels. Improving over the state-of-the-art work of Byali et al. (ACM CCS ’18), we present two instantiations that efficiently achieve: (a) fairness in 3 rounds using 2 garbled circuits (GC) (b) guaranteed output delivery (GOD) in 3 rounds using 4 GCs. Further, improving the efficiency of 2-round 4PC feasibility result of Ishai et al. (CRYPTO ’15) that achieves GOD at the expense of 12 GCs, we achieve GOD in 2 rounds with 8 GCs, thus saving 4 GCs over that of Ishai et al. Under a mild one-time setup, the GC count can further be reduced to 6 which is half of what the prior work attains. This widely-followed demarcation of the world of MPC into the classes of honest and dishonest majority suffers from a worrisome shortcoming: one class of protocols does not seem to withstand the threat model of the other. Specifically, an honest-majority protocol promising fairness or GOD violates the primary notion of privacy as soon as half (or more) parties are corrupted, while a dishonest-majority protocol does not promise fairness or GOD even against a single corruption, let alone a minority. The promise of the unconventional yet much sought-after brand of MPC, termed as Best-of-Both-Worlds (BoBW), is to offer the best possible security in the same protocol depending on the actual corruption scenario. With this motivation in perspective, part II presents two practically-efficient 4PC protocols in the BoBW model, that achieve: (1) guaranteed output delivery against 1 corruption and unanimous abort against 2 corruptions. (2) fairness against 1 corruption and unanimous abort against arbitrary corruptions. The thresholds are optimal considering the feasibility given in the work of Ishai et al. (CRYPTO ’06) that marks the inauguration of the BoBW setting. We provide elaborate empirical results through implementation that support the theoretical claims made in all our protocols. We emphasize that this work is the first of its kind in providing practically-efficient constructions with implementation in the BoBW model. Also, the quality of constant-rounds makes all protocols in this work suitable for high-latency networks such as the Internet.