Near-Linear
Unconditionally-Secure Multiparty Computation with a Dishonest Minority
Eli
Ben-Sasson (
Serge Fehr
(CWI, The
Rafail Ostrovsky (UCLA)
Abstract:
In the setting of unconditionally-secure MPC, where (dishonest) players are
unbounded and no cryptographic assumptions are used, it was known since the
1980's that an honest majority of players is both necessary and sufficient to
achieve privacy and correctness, assuming secure point-to-point and broadcast
channels. The main open question that was left is to establish the exact
communication complexity. In all works, there was a large gap between the
communication complexity of the best known protocols in the malicious setting
and in the honest-but-curious setting, where players do not deviate from the
protocol.
We settle the above question by showing an unconditionally-secure MPC
protocol, secure against a dishonest minority of malicious players,
that matches the communication complexity of the best known MPC
protocol in the honest-but-curious setting. More specifically, we present a
new n-player MPC protocol that is secure against a computationally-unbounded
malicious adversary that can adaptively corrupt up to t<n/2 of the
players. For polynomially-large binary circuits
that are not too unshaped, our protocol has an amortized communication
complexity of O(n*log(n) + k/n^c)
bits per multiplication (i.e. AND) gate, where k denotes the security
parameter and c is an arbitrary non-negative constant. This improves on the
previously most efficient protocol with the same security guarantee, which
offers an amortized communication complexity of O(n^2*k)
bits per multiplication gate. For any k polynomial in n, the amortized
communication complexity of our protocol matches the O(n*log(n))
bit communication complexity of the best known MPC protocol with passive
security.
We introduce several novel techniques that are of independent interest and we
believe will have wider applicability. One is a novel idea of computing
authentication tags by means of a mini MPC, which allows us to avoid
expensive double-sharings; the other is a
batch-wise multiplication verification that allows us to speedup Beaver's
multiplication triples. The techniques draw from the PCP world and this
infusion of new techniques from other domains of computational complexity may
find further uses in the context of MPC.