Summer 2015

Crypto Reading Group

Thursday, Jul. 30, 2015 10:00 am12:00 pm PDT

Add to Calendar

Parent Program: 

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