Paper 2021/1032

AdVeil: A Private Targeted-Advertising Ecosystem

Sacha Servan-Schreiber and Kyle Hogan and Srinivas Devadas

Abstract

This paper presents AdVeil, a privacy-preserving advertising ecosystem with formal guarantees for end users. AdVeil is built around an untrusted advertising network which is responsible for brokering the display of advertisement to users. This ad network targets relevant ads to users without learning any of the users’ personal information in the process. Our targeting protocol combines private information retrieval with standard, locality-sensitive hashing based techniques for nearest neighbor search. By running ad targeting in this way, users of AdVeil have full control over and transparency into the contents of their targeting profile. AdVeil additionally supports private metrics for ad interactions, allowing the ad network to correctly charge advertisers and pay websites for publishing ads. This is done without the ad network learning which user interacted with an ad, only that some honest user did. AdVeil achieves this using an anonymizing proxy (e.g., Tor) to transit batched user reports along with unlinkable anonymous tokens to certify the authenticity of each report. We build a prototype implementation of AdVeil which we evaluate on a range of parameters to demonstrate the applicability of AdVeil to a real-world deployment. Our evaluation shows that AdVeil scales to ad networks with millions of ads, using state-of-the-art single-server private information retrieval. A selection of ads from a database of 1 million ads can be targeted to a user in approximately 4.5 seconds with a single 32-core server, and can be parallelized further with more servers. Targeting is performed out-of-band (e.g., on a weekly basis) while ad delivery happens in real time as users browse the web. Verifying report validity (for fraud prevention) requires less than 300 microseconds of server computation per report.