A Protocol for Privately Reporting Ad Impressions at Scale

We present a protocol to enable privacy preserving advertising reporting at scale. Unlike previous systems, our work scales to millions of users and tens of thousands of distinct ads. Our approach builds on the homomorphic encryption approach proposed by Adnostic [42], but uses new cryptographic proof techniques to efficiently report billions of ad impressions a day using an additively homomorphic voting schemes. Most importantly, our protocol scales without imposing high loads on trusted third parties. Finally, we investigate a cost effective method to privately deliver ads with computational private information retrieval.