Practical private computation of vector addition-based functions

ABSTRACT

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 10⁶).

REFERENCES

• 1: John Canny, Collaborative Filtering with Privacy, Proceedings of the 2002 IEEE Symposium on Security and Privacy, p.45, May 12-15, 2002
• 2: John Canny, Collaborative filtering with privacy via factor analysis, Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval, August 11-15, 2002, Tampere, Finland [doi>10.1145/564376.564419]
• 3: John Canny, GaP: a factor model for discrete data, Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, July 25-29, 2004, Sheffield, United Kingdom [doi>10.1145/1008992.1009016]
• 4: Ronald Cramer , Ivan Damgård, Zero-Knowledge Proofs for Finite Field Arithmetic; or: Can Zero-Knowledge be for Free?, Proceedings of the 18th Annual International Cryptology Conference on Advances in Cryptology, p.424-441, August 23-27, 1998
• 5: Y. Duan, J. Wang, M. Kam, and J. Canny. A secure online algorithm for link analysis on weighted graph. In Proceedings of the Workshop on Link Analysis, Counterterrorism and Security, SIAM Data Mining Conference, 2005, pages 71--81.
• 6: O. Goldreich , S. Micali , A. Wigderson, How to play ANY mental game, Proceedings of the nineteenth annual ACM symposium on Theory of computing, p.218-229, January 1987, New York, New York, United States [doi>10.1145/28395.28420]
• 7: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Journal of the ACM (JACM), v.46 n.5, p.604-632, Sept. 1999 [doi>10.1145/324133.324140]
• 8: A. C.-C. Yao. Protocols for secure computations. In FOCS '82, pages 160--164. IEEE, 1982.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

General Terms:
Security

Keywords:
L2-norm, private computation, vector addition, zero-knowledge protocol