John F. Canny and Yitao Duan

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2006-12

February 8, 2006

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-12.pdf

In this paper we explore private computation built on vector addition. Vector addition is a surprisingly general tool for computing private aggregates over many users' data. Examples including linear algorithms like voting and summation, but also many non-linear algorithms like SVD, regression, ANOVA and several machine learning algorithms based on Expectation Maximization (EM). These methods aggregate user data only in certain steps, such as conjugate gradient, which are {\em linear} in per-user data. In this paper we introduce a new and highly-efficient private vector addition protocol which is a blend of P2P and client-server. Secret-shared arithmetic operations are done {\em 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, which uses large-field public-key arithmetic (1024 bits or more) and homomorphic computation. The main result of this paper is a random projection method for verification that requries only a {\em logarithmic} number of large-field operations. Overall, the protocol is dominated by the (linear) time to do small-field operations on user data. Essentially our solution provides user privacy for free from a server or client's perspective. In experiments, addition and verification of a million-element vector takes approximately three seconds of server time and about five seconds of client time on state-of-the-art PCs.

---

BibTeX citation:

@techreport{Canny:EECS-2006-12,
    Author= {Canny, John F. and Duan, Yitao},
    Title= {Practical Private Computation of Vector Addition-Based Functions or: Can Privacy be for Free?},
    Year= {2006},
    Month= {Feb},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-12.html},
    Number= {UCB/EECS-2006-12},
    Abstract= {In this paper we explore private computation built on vector addition. Vector addition is a surprisingly general tool for computing private aggregates over many users' data. Examples including linear algorithms like voting and summation, but also many non-linear algorithms like SVD, regression, ANOVA and several machine learning algorithms based on Expectation Maximization (EM). These methods aggregate user data only in certain steps, such as conjugate gradient, which are {\em linear} in per-user data.  In this paper we introduce a new and highly-efficient private vector addition protocol which is a blend of P2P and client-server. Secret-shared arithmetic operations are done {\em 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, which uses large-field public-key arithmetic (1024 bits or more) and homomorphic computation.  The main result of this paper is a random projection method for verification that requries only a {\em logarithmic} number of large-field operations. Overall, the protocol is dominated by the (linear) time to do small-field operations on user data. Essentially our solution provides user privacy for free from a server or client's perspective. In experiments, addition and verification of a million-element vector takes approximately three seconds of server time and about five seconds of client time on state-of-the-art PCs.},
}

EndNote citation:

%0 Report
%A Canny, John F. 
%A Duan, Yitao 
%T Practical Private Computation of Vector Addition-Based Functions or: Can Privacy be for Free?
%I EECS Department, University of California, Berkeley
%D 2006
%8 February 8
%@ UCB/EECS-2006-12
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-12.html
%F Canny:EECS-2006-12