Kai-Min Chung (Academia Sinica)
Calvin Lab Room 116
Large-Scale Secure Computation: Multi-party Computation for Parallel RAM Programs
We present the first efficient (i.e., polylogarithmic overhead) method for securely and privately processing large data sets over multiple parties with parallel, distributed algorithms. More specifically, we demonstrate load-balanced, statistically secure computation protocols for computing Parallel RAM (PRAM) programs, handling (1/3 - \eps) fraction malicious players, while preserving up to polylogarithmic factors the computation, parallel time, and memory complexities of the PRAM program, aside from a one-time execution of a broadcast protocol per party. Additionally, our protocol has \polylog communication locality---that is, each of the n parties speaks only with \polylog(n) other parties.
Joint work with Elette Boyle and Rafael Pass