Practical private computation of vector addition-based functions

In this paper we explore private computation built on vector addition which is a surprisingly general tool for implementing many useful analysis on user-provided data. Examples include both linear and non-linear algorithms such as singular value decomposition (SVD), regression, analysis of variance (ANOVA), and several machine learning algorithms based on Expectation Maximization (EM). The non-linear algorithms aggregate user data only in certain steps, such as conjugate gradient, which are linear in per-user data. We introduce a new and highly efficient VSS (Verifiable Secret-Sharing) protocol in a special but widely-applicable model that allows secret-shared arithmetic operations in such aggregation steps to be done over small fields (e.g. 32 or 64 bits), so that private arithmetic operations have the same cost as normal arithmetic. Verification of user data is required to prevent a malicious user from biasing the computation. We provide a random projection method for verification that uses a linear number of inexpensive small field operations, and only a logarithmic number of large-field (1024 bits or more) cryptographic operations. Our implementation shows that the approach can achieve orders of magnitude reduction in running time over standard techniques (from hours to seconds) for large scale problems (e.g. at the scale where the number of values per user is 106).