Secure Vickrey Auctions for Online Advertising

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. 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 for online advertising, is challenging.

Obsidian enables secure Vickrey auctions for online advertising with three ideas: a new Multiparty Computation (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. Obsidian outperforms generic MPC and homomorphic encryption approaches by orders of magnitude. Moreover, it also surpasses the state-of-the-art system, Addax, which is tailored to ad auctions under a weaker (covert) threat model and leaks more information.