efficiently manage privacy on-device for private advertising APIs
As major browsers phase out third-party cookies, emerging advertising APIs offer an opportunity to improve web privacy. Cookie Monster enhances existing advertising measurement APIs from major tech companies with more efficient differential privacy (DP) budgeting. By using an individual form of DP, our approach enables more accurate private measurement queries, with additional benefits in terms of user transparency and control. We prototyped Cookie Monster in Chrome, and our design has been incorporated into Mozilla’s draft for standardization at the W3C Private Advertising Technology Working Group.
Big Bird builds on Cookie Monster to make privacy budgeting resilient across untrusted web domains. It shows that enforcing individual DP per querying domain is unsound in an open web setting, and instead enforces a global device-epoch budget shared by all domains. To keep that shared budget from being depleted by Sybil domains, Big Bird ties budget consumption to genuine user actions through privacy-loss quotas on impression and conversion sites and a per-user-action cap on quota activations. We implemented Big Bird in Firefox, using pdslib, our generic Rust library for on-device DP budgeting.
References
2026
Big Bird: Resilient Privacy Budgeting Across Untrusted Web Domains
Pierre Tholoniat, Alison Caulfield, Giorgio Cavicchioli, Mark Chen, Benjamin Case, Asaf Cidon, Roxana Geambasu, Mathias Lécuyer, and Martin Thomson
In Symposium on Operating Systems Principles, 2026
The W3C Attribution API is an emerging standard for privacy-preserving advertising measurement. Its current privacy architecture enforces individual differential privacy (IDP) independently for each domain (e.g., an advertiser) issuing queries. We show that this guarantee is unsound under realistic system behavior: it fails under cross-querier data adaptivity and can also fail when shared limits are enforced across queriers. The issue is not the on-device accounting model itself – device-epoch IDP – but treating each querying domain in isolation. We propose Big Bird, a privacy-budget manager that makes global device-epoch IDP – enforced jointly across all domains – both sound and deployable for Attribution. Big Bird addresses the main obstacle to global enforcement in open multi-querier systems: denial-of-service depletion of a shared global budget by Sybil web domains. Its key insight is that benign Attribution workloads have a stock-and-flow structure: impressions create potential privacy loss, conversions realize it, and meaningful budget consumption should be tied to genuine user actions across distinct web domains. Big Bird enforces this structure with privacy-loss-based quotas on impression and conversion sites and a per-user-action cap on how many quotas can be activated, ensuring that adversarial impact scales with genuine user interactions rather than with the number of Sybil domains. We implement Big Bird in Rust, integrate it into Firefox’s Attribution prototype, and evaluate it theoretically and empirically on real ad-tech data. We show that Big Bird provides rigorous global device-epoch IDP, formal resilience to depletion attacks, and utility for benign queriers under attack.
@inproceedings{bigbird,title={Big {{Bird}}: {{Resilient Privacy Budgeting Across Untrusted Web Domains}}},shorttitle={Big {{Bird}}},author={Tholoniat, Pierre and Caulfield, Alison and Cavicchioli, Giorgio and Chen, Mark and Case, Benjamin and Cidon, Asaf and Geambasu, Roxana and L\'ecuyer, Mathias and Thomson, Martin},year={2026},booktitle={Symposium on Operating Systems Principles},series={SOSP '26},location={Prague, Czech Republic},publisher={Association for Computing Machinery},address={New York, NY, USA},numpages={35},doi={10.1145/3830418.3843897},url={https://doi.org/10.1145/3830418.3843897},note={To appear at SOSP '26},keywords={differential privacy, web, measurement}}
2024
Cookie Monster: Efficient On-Device Budgeting for Differentially-Private Ad-Measurement Systems
Pierre Tholoniat, Kelly Kostopoulou, Peter McNeely, Prabhpreet Singh Sodhi, Anirudh Varanasi, Benjamin Case, Asaf Cidon, Roxana Geambasu, and Mathias Lécuyer
In Proceedings of the ACM SIGOPS 30th Symposium on Operating Systems Principles, 2024
With the impending removal of third-party cookies from major browsers and the introduction of new privacy-preserving advertising APIs, the research community has a timely opportunity to assist industry in qualitatively improving the Web’s privacy. This paper discusses our efforts, within a W3C community group, to enhance existing privacy-preserving advertising measurement APIs. We analyze designs from Google, Apple, Meta and Mozilla, and augment them with a more rigorous and efficient differential privacy (DP) budgeting component. Our approach, called Cookie Monster, enforces well-defined DP guarantees and enables advertisers to conduct more private measurement queries accurately. By framing the privacy guarantee in terms of an individual form of DP, we can make DP budgeting more efficient than in current systems that use a traditional DP definition. We incorporate Cookie Monster into Chrome and evaluate it on microbenchmarks and advertising datasets. Across workloads, Cookie Monster significantly outperforms baselines in enabling more advertising measurements under comparable DP protection.
@inproceedings{cookiemonster24,author={Tholoniat, Pierre and Kostopoulou, Kelly and McNeely, Peter and Sodhi, Prabhpreet Singh and Varanasi, Anirudh and Case, Benjamin and Cidon, Asaf and Geambasu, Roxana and L\'{e}cuyer, Mathias},title={Cookie Monster: Efficient On-Device Budgeting for Differentially-Private Ad-Measurement Systems},year={2024},isbn={9798400712517},publisher={Association for Computing Machinery},address={New York, NY, USA},url={https://doi.org/10.1145/3694715.3695965},doi={10.1145/3694715.3695965},booktitle={Proceedings of the ACM SIGOPS 30th Symposium on Operating Systems Principles},pages={693--708},numpages={16},keywords={differential privacy, budgeting, measurement},location={Austin, TX, USA},series={SOSP '24},}