Communication complexity of secure computation

Abstract

A secret-ballot vote for a single proposition is an example of a secure distributed computation. The goal is for n participants to jointly compute the output of some n-ary function (in this case, the sum of the votes), while protecting their individual inputs against some form of misbehavior. In this paper, we initiate the investigation of the communication complexity of unconditionally secure multi-party computation, and its relation with various fault-tolerance models. We present upper and lower bounds on communication, as well as tradeoffs among resources. First, we consider the "direct sum problem" for communication complexity of perfectly secure protocols: Can the communication complexity of securely computing a single function f: Fn → F at κ sets of inputs be smaller if all are computed simultaneously than if each is computed individually? We show that the answer depends on the failure model. A factor of O(n/logn) can be gained in the privacy model (where processors are curious but correct); specifically, when f is n-ary addition (mod 2), we show a lower bound of ω(n2) bits for computing f once and an upper bound of O(n2 log n) for computing f O(n) times simultaneously. No gain is possible in a slightly stronger fault model (fail-stop mode); specifically, when f is n-ary addition over GF(q), we show an exact bound of ⊖(κn2 logq) for computing f at k sets of inputs simultaneously (for any kappa; ≥ 1). However, if one is willing to pay an additive cost in fault tolerance (from t to t - kappa; + 1), then a variety of known non-cryptographic protocols (including "provably unparallelizable" protocols from above!) can be systematically compiled to compute one function at kappa; sets of inputs with no increase in communication complexity. Our compilation technique is based on a new compression idea of polynomial-based multi-secret sharing. Lastly, we show how to compile private protocols into error-detecting protocols at a big savings of a factor of O(n3) (up to a log factor) over the best known error-correcting protocols. This is a new notion of fault-tolerant protocols, and is especially useful when malicious behavior is infrequent, since error-detection implies error-correction in this case.