Transcript Practical Private Computation of Vector Addition

Practical Private Computation of Vector
Addition-Based Functions
Yitao Duan and John Canny
Computer Science Division
University of California, Berkeley
PODC 2007, August 12, Portland OR
Overview



A method for performing privacy
preserving distributed computation of
many algorithms that is practical and
secure in a realistic threat model at
large scale
Provably strong (information-theoretic)
privacy
Efficient ZKP to deal with cheating users
Model
• A few collaborating data miners mining
data from n users
• Each user has an m-dimensional vector
• Realistic scale: m, n large (103 – 106)
• Threat: data miners are passive, users are
allowed to cheat arbitrarily
Challenge: standard
cryptographic tools not
feasible at this scale
Our Results

Private computation based on secret sharing using
addition only steps




Private addition is much simpler than multiplication
The main computation is in small field (32 or 64 bits) – private
computation has the same cost as regular arithmetic
A lot of (nonlinear) algorithms can be done with addition:
Regression, Classification, Bayes net, Link analysis, SVD, EM.
An extremely efficient ZKP that the L2 norm of user
vector is bounded by L (Only O(logm) large field
operations)
An Efficient Proof of Honesty


The server asks for N random projections of the user’s
vector, the user proves the square sum of them is small.
Projections are done in small field. The only large field
operations are N encryptions and boundedness ZKP
O(log m) public key crypto operations (instead of O(m)) to prove
that the L-2 norm of an m-dim vector is smaller than L.
Acceptance/rejection probabilities
(a) Linear and (b) log plots of probability of user input acceptance as a function of |d|/L for N =
50. (b) also includes probability of rejection. In each case, the steepest (jagged curve) is the
single-value vector (case 3), the middle curve is Zipf vector (case 2) and the shallow curve is
uniform vector (case 1)
Performance
(a) Verifier and (b) prover times in seconds with N = 50, where (from top to bottom) L
has 40, 20, or 10 bits. The x-axis is the vector length m.
More Info

Code available for download, soon.
[email protected]
http://www.cs.berkeley.edu/~duan

Thank you!

