Secure parallel computation on national scale volumes of data

We revisit the problem of performing secure computation of graph-parallel algorithms, focusing on the applications of securely outsourcing matrix factorization, and histograms. Leveraging recent results in low-communication secure multiparty computation, and a security relaxation that allows the computation servers to learn some differentially private leakage about user inputs, we construct a new protocol that reduces overall runtime by 320X, reduces the number of AES calls by 750X, and reduces the total communication by 200X. Our system can securely compute histograms over 300 million items in about 4 minutes, and it can perform sparse matrix factorization, which is commonly used in recommendation systems, on 20 million records in about 6 minutes. 1 Furthermore, in contrast to prior work, our system is secure against a malicious adversary that corrupts one of the computing servers. * Lead co-authors 1 These numbers are for computation in a LAN. For results in a WAN, see Section 5. a near minimum. Of course, there are no free lunches, and computing on secret-shared data will always require increased communication and computation when compared with the cost of computing on plaintext data. However, several recent research directions have helped narrow the gap between secure data processing and plaintext computations.