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