Secure Vickrey Auctions for Online Advertising

Abstract

Online advertising is an essential part of the web ecosystem. When a user’s browser lands on a webpage, advertisers bid for the ad space on the webpage. An auction algorithm (e.g., Vickrey/second-price auction) is executed to determine the winner and the price—ideally, only this information is revealed, and everything else (i.e., the losing bids and the bidder identities) is kept private. However, achieving these privacy goals under a malicious security model, while operating under stringent performance requirements, is challenging.

We propose Obsidian, which enables secure Vickrey auctions with three ideas: a new MPC-friendly encoding scheme that decouples bid values from bidders’ identities; a novel use of function secret sharing to shift the cost of encoding validation to an offline phase; and a lightweight ring signature scheme to anonymously verify bidders. We show that Obsidian significantly outperforms generic MPC and homomorphic encryption approaches—by orders of magnitude—and even surpasses Addax, a system tailored to ad auctions, despite Addax assuming a weaker (covert) threat model and leaking more information.