Secure multi-party computation (MPC) protocols allow a group of n parties to compute some function on the parties’ private inputs, while preserving a number of security properties such as privacy and correctness. The former property means that nothing leaks from the protocol execution but the computed output. The latter implies that the protocol enforces the integrity of the computation, namely, honest parties are not lead to accept a wrong output. We present a new approach to designing concretely efficient MPC protocols against honest-but-curious adversaries corrupting a majority of the parties. Motivated by the fact that within the dishonest majority setting the efficiency of most practical protocols does not depend on the number of honest parties, we investigate how to construct protocols which improve in efficiency as the number of honest parties increases.

Our central idea is to take protocols which are secure for n-1 corruptions and modify them to use short symmetric keys, with the aim of basing security on the concatenation of all honest parties’ keys. This results in more efficient protocols tolerating fewer corruptions, whilst also introducing an LPN-style syndrome decoding assumption.

We first apply this technique to a modified version of the semi-honest GMW protocol, using OT extension with short keys. We also obtain more efficient constant-round MPC using BMR-style garbled circuits with short keys, and present an implementation of the online phase of this protocol. Our techniques start to improve upon existing protocols when there are around n=20 parties with h=6 honest parties, and as these increase we obtain up to a 13 times reduction (for n=400,h=120) in communication complexity for our GMW variant, compared with the best-known GMW-based protocol modified to use the same threshold.