Large-Scale Secure Computation: Multi-party Computation for (Parallel) RAM Programs

Abstract. We present the first efficient (i.e., polylogarithmic overhead) method for securely and privately processing large data sets over mul-tiple parties with parallel, distributed algorithms. More specifically, we demonstrate load-balanced, statistically secure computation protocols for computing Parallel RAM (PRAM) programs, handling (1/3−) frac-tion malicious players, while preserving up to polylogarithmic factors the computation and memory complexities of the PRAM program, aside from a one-time execution of a broadcast protocol per party. Addition-ally, our protocol has polylog communication locality—that is, each of the n parties speaks only with polylog(n) other parties.