Divisible E-Cash for Billing in Private Ad Retargeting
Authors: Kevin Liao (MIT and Harvard Law School), Henry Corrigan-Gibbs (MIT), Dan Boneh (Stanford University)
Volume: 2024
Issue: 4
Pages: 5–23
DOI: https://doi.org/10.56553/popets-2024-0104
Abstract: This paper presents new techniques for private billing in systems for privacy-preserving online advertising. In particular, we show how an ad exchange can use an e-cash scheme to bill advertisers for ad impressions without learning which client saw which ad: The exchange issues electronic coins to advertisers, advertisers pay publishers (via clients) for ad impressions, and publishers unlinkably redeem coins with the exchange. To implement this proposal, we design a new divisible e-cash scheme that uses modern zero-knowledge proofs to reduce the ad exchange's computational costs by roughly 250x compared to the previous state-of-the-art. With our new e-cash scheme, our private-billing infrastructure adds little overhead to existing private ad-retargeting systems: less than 63 ms of latency, negligible client computation, less than 3.2 KB of client communication, and a combined server operating cost (advertisers, publishers, and exchange) of less than 1% of ad spend, an over 5x savings compared to the previous state-of-the-art.
Keywords: electronic cash, privacy-preserving advertising
Copyright in PoPETs articles are held by their authors. This article is published under a Creative Commons Attribution 4.0 license.
