Preserving privacy through cryptography in online behavioural advertising

Abstract

Online advertising is a multi-billion dollar industry, forming one of the primary sources of income for many publishers that offer free web content. Online Behavioural Advertising (OBA), the practice of showing advertisements based on individual users' web browsing behaviours, greatly improves the expected effectiveness of advertisements, and is believed to be beneficial to advertisers and users alike. The privacy of users, however, is threatened by the widespread collection and exchange of users' browsing behaviour by dozens of companies for the purpose of behavioural advertising. The aim of this thesis is to alleviate these privacy concerns by investigating how an online advertising system can serve advertisements tailored to users' interests within the current online advertising ecosystem, such that no party other than the user themselves can gain any knowledge of the user's interests. To protect user privacy in the online advertising ecosystem, two main challenges need to be overcome. Not only do advertising companies need to adapt their machine learning models to a setting in which they have no knowledge of user interests, they also need to integrate their privacy-preserving targeting systems into a complex advertising landscape where advertisement impressions are traded within a fraction of a second. We present two complete privacy-preserving protocols for online behavioural advertising that combine machine learning methods commonly encountered in existing advertising systems with secure multi-party computation techniques. The first protocol uses a threshold variant of an additively homomorphic cryptosystem to distribute trust between parties while allowing computations on encrypted data, such that advertisements can be served based on detailed user profiles. The second protocol distributes trust between advertising companies using an additively homomorphic threshold secret sharing scheme, allowing collaborative computations on user profiles while preventing a coalition of colluding parties smaller than a predefined threshold from obtaining any sensitive information. Both protocols achieve performance multilinear in the size of user profiles and the number of advertising campaigns, and show promising initial results in terms of privacy and performance. To the best of our knowledge, our two protocols are the first protocols that preserve user privacy in behavioural advertising while allowing the use of detailed user profiles and machine learning methods.