Collaborative Filtering with Privacy
by John Canny, IEEE Security and Privacy, May 2002
Discussed by the security reading group on 11 July 2002
This paper describes a method to compute an aggregate of user preferences for a
set of users, without exposing the individual user preferences. This is useful
for applications like users recommendations/ratings without compromising user
privacy.
The protocol assumes that at least half the participants are not cheating. It
also requires a write-once read-many storage system, and a
trusted source of random bits. Given this, it computes an aggregate
model of user preferences (without individual user preferences being
revealed), using an iterative conjugate-gradient algorithm. The goal
is to do this with reasonable amount of work per machine to be practical, and to
be able to efficiently check the computations. The protocol also involves
secret-sharing a private key between participating clients, so no single user
has the private key.
The authors implemented the numerical methods and tested it against the
EachMovie database, with good accuracy in the recommendations.
This method for recommendations has some interesting properties:
* Users can provide their ratings/recommendations to the system without their
individual preferences being visible to others.
* With n users recommendations for m items, the amount of work per client in
each round of the protocol is O(km log n)
* It makes it easier for users to get recommendations from groups of users with
different preferences from themselves, unlike most existing schemes that provide
one with recommendations from groups of people with similar to oneself.
Discussion:
* This protocol is only one component in a system to provide user
privacy, since vendors like Amazon will have access to user buying
records anyway.
* Some people were unhappy about the non-implementation of the
cryptographic part of the protocl.
* The group was not qualified to evaluate the mathematics of the model.
Vote:
1 accept, 1 abstain, 4 weak reject