Cryptographically-enhanced privacy for recommender systems (2013)

Automated recommender systems are used to help people find interesting content or persons in the vast amount of information available via the internet. There are different types of recommender systems, for example collaborative filtering systems and content-based recommender systems. However, all recommender systems share a common trait: in order to generate personalized recommendations, they require information on the attributes, demands, or preferences of the user. Typically, the more detailed the information related to the user is, the more accurate the recommendations for the user are. Service providers running the recommender systems collect large amounts of personal information to ensure accurate recommendations. This data must be protected to increase the privacy of all participating users. Privacy is typically enhanced through one (or more) of three methods: (1) decentralization, (2) introduction of uncertainty, and (3) secure computation. Decentralization aims to remove the central service provider and gives more control to the individual users. However, decentralized systems cannot guarantee the availability of data as users go online and offline as they please. Furthermore, no single entity is responsible for data that does not belong to a specific user (such as item data). Uncertainty is typically introduced by adding random noise to the data, which provides a mask over the user information. However, this noise negatively impacts the accuracy of the recommender system. When the users introduce their own noise, then the system consists mainly of noise. To preserve accuracy, only the service provider introduces noise, therefore no privacy is achieved against the service provider. Secure computation protects the data that is used during the computation of recommendations by providing confidentiality, both at rest and during computation. However, it suffers from a large computational overhead, due to the use of cryptography and secure multi-party protocols. In this thesis we focus on the use of secure computation to enhance the privacy of recommender systems, where we strive to make the computations as efficient as possible. To provide this, we build specialized secure computation protocols based on homomorphic encryption schemes and secure multi-party computation. Each protocol is tailored to the specific problem that is addressed, with a minimum of expensive operations and interactions. These protocols address the following challenges: (1) fostering cooperation between competing service providers, (2) coping with the unavailability of users, and (3) dealing with malicious intent by the users. Cooperating service providers are able to leverage each others databases to provide better recommendations. However, privacy of users and secrecy of a service provider’s database normally prevents competing service providers from collaborating based on sharing their plain-text databases. We provide a secure protocol that allows competing service providers to collaborate and share their respective databases of information, without leaking the database to the competitor. Most existing secure computation protocols for recommender systems require interaction between the service provider and its users, which makes unavailability of users a serious issue. Secure computation protocols that do not rely on the availability of users are therefore preferred. We contribute a secure protocol that allows users to be unavailable during the computation of a recommendation for a specific user (this specific user is still required to be online). The typical approach to deal with unavailable users is to introduce a second (independent) server, which needs to be (partly) trusted by the users. Our protocol does not rely on an additional server, but instead relies on existing trust relationships (e. g. friendship) between users who wish to share their preferences. In general, secure computation protocols for recommender systems assume honest behaviour of participating users. However, this assumption is not valid in most cases, as users attempt to exploit the recommender system for their own gain. More robust protocols for recommender systems are preferred. We present a secure framework for recommender systems that can cope with malicious user behaviour. The framework consists of two protocols for users to update ratings and retrieve recommendations. The framework can be instantiated with different types of recommender systems.