W3C Breakout Minutes: Individual Differential Privacy for High-Utility Private Web Measurements – 09.25.24
Session Info:
https://www.w3.org/events/meetings/e75479d6-b578-4565-bd53-4f30a259726e/
IRC Chat: https://irc.w3.org/?channels=%23differential-privacy
Scribes
Willing victims
Agenda
- <= 5 min: Intro. W3C Policies
- <= 30 min: Presentation by Roxana
- >= 25 min: Questions and Feedback
Participants
- Alex Koshelev (Meta)
- Aloïs Bissuel (Criteo)
- Andrew Pascoe (NextRoll)
- Andy Leiserson (Mozilla)
- Ben Savage (Meta)
- Benjamin Case (Meta)
- Benjamin De Kosnik (Mozilla)
- Brandon Maslen (Microsoft Edge)
- Christian Berkhoff (Meta)
- Erik Taubeneck (Meta)
- Fabian Höring (Criteo)
- Isaac Foster (Microsoft Ads)
- John Delaney (Google Chrome)
- Maxime Vono (Criteo)
- Michal Kalisz (RTB House)
- Martin Thomson (Mozilla)
- Phillipp Schoppmann (Google)
- Richa Jain (Meta)
- Roxana Geambasu (Columbia University)
- Sarah Murphy (Microsoft Edge)
- Shinta Liem (Meta)
- Sid Sahoo (Google Privacy Sandbox)
- Steven Valdez (Google)
- Charlie Harrison (Google Chrome)
- Aram Zucker-Scharff (The Washington Post)
Notes
- Developed a framework for cross site web measurements, with improved privacy/utility tradeoff.
- Background:
- Online ads have an advantage over offline due to measuring conversion attribution. Historically relied on 3PC/fingerprinting.
- Browsers seeking privacy preserving alternatives. Chrome ARA. Sarari PAM. Mozilla/Meta IPA & Hybrid.
- Record impressions locally
- Send encrypted attributed conversions to ad tech
- Ad tech aggregates conversion reports with secure aggregation service (SAS)
- Aggregates have noise added to make them differentially private
- Privacy/utility tradeoff: DP adds noise to limit what is learned about individual users. Increasing noise improves privacy but hurts utility. Privacy loss accumulates across queries. Our aim is to push the frontier of this tradeoff, e.g., allow for more utility without reducing privacy.
- Cookie monster is based on Individual Differential Privacy (IDP), which offers the same privacy guarantee as traditional DP. IDP allows for it to be controlled per user, while DP is across all users.
- Devices track their own privacy loss, and enforce a cap (total privacy budget).
- Ad tech specifies an (ε, max) when reporting an impression and conversion, as well as when aggregated.
- With traditional DP, all devices would have to account for the same global privacy loss. This doesn’t make much sense as it would need to account for imps/convs it has nothing to do with.
- IDP loss is always less than or equal to the global DP loss.
- A device that doesn’t participate, has contribution 0. Another device has a conversion, but with no ads, it also has a contribution 0. In both cases, IDP loss is 0.
- Another device that converted ($70) and did have impressions. It can account for privacy loss from that conversion scaled by that $70.
- Yet another device has a conversion of $140. It can account for the privacy loss from that conversion scaled by $140.
- Evaluation on a PATCG dataset
- Y-axis: inverse utility metric (error) (lower is better)
- X-axis: privacy metric (higher is better)
- IPA-like: very small error, but very few measurements before exhausting budget.
- ARA-like: finishes all queries. Relatively higher measurement error, especially at higher levels of privacy.
- Cookie Monster: finishes all queries, lower error than ARA, but utility decreases as privacy increases.
- Other properties that come from IDP formulation
- Transparency: Browsers could provide a UI to users about their privacy loss.
- Control: User device is in charge of capping its own user’s privacy loss.
- Downside: Adds potential for bias
- Individual privacy loss depends on user data, and itself must be kept private. When the cap is reached, the device sends null reports. Null reports can introduce bias.
- WIP: Measure bias in the aggregation service with DP. “recursive design”
- Bias is low in current experiments
Questions
- Sarah Murphy: At what rate does the device refresh?
- Roxana: This offers a formal IDP over (browser, epoch). The smaller the epoch, the worse the semantic. Budget resets to 0 at the start of each epoch.
- Martin: Tradeoff between making it granular enough that you get more if you waste it. Longer period means we could give you more budget, but has a risk of being used up early.
- Ben: Once the budget expires in one epoch, you cannot query anymore data in that epoch (even when it refreshes next epoch.)
- Martin: Longer epoch has more privacy risk.
- Roxana: In our experiments and in academic work we fix ε = 1.
- Charlie Harrison (accounting across units, bias more than typical capping approaches?) Seems similar to other DP techniques. Is there more here?
- Roxana: Yes, when null reports are sent. In a typical DP system, there is one source of bias (the sensitivity cap). In Cookie Monster, it also sends null. It cannot reveal that it ran out of data.
- Daniel: With formal DP, you’d know you ran out of budget so, you wouldn’t run more queries. In this model, you could get events, and not know that events have run out.
- Charlie: Accounting across privacy units. Epoch is all data in that time period. Attribution is a join across two events.
- Martin: Only conversions deduct. If you query over impressions in multiple epochs, budget deducts from all of them. Conversion queries multiple privacy budget data bases.
- John Delaney (clarification question on the scaling max). Suppose my actual MAX is $1000, but in general, most only spend $100. Does this need to be public or private?
- Martin: This needs to be public. If you set it to $1000, but everyone spends $100, you pay in 10x more noise. In this case, you’d probably want to set your max to $100.
- Andrew: Paying this price in noise.
- Martin: Or in noise.
- Andrew: Bias / noise tradeoff.
- Charlie: Is that because you’re adding too much noise?
- Ben: No, just based on the data set.
- Charlie: How did you determine the maximum in the experiment?
- Roxana: Will have to follow up.
- Isaac (DP basics reminder, two questions re budget & epoch) Could epoch be device specified? Different for different browsers?
- Unclear.
- Martin: My sense, different browsers could have different epochs.
- Isaac: Could use this with other datasets stored locally?
- Roxana: Intuition - compelling that you walk around with your device and leave breadcrumbs on the phone. Would ask for a report of this.
- Isaac: In theory you could build an auto-intender. I visited a site that implies I’m going to build a car. In the last 3 epochs, has a user visited a site like this, and I could show an ad for a car.
- Martin: No answer for now.
- Aram Zucker-Scharff (question: Does this bias towards particular sales/purchase/purchasers?) Does it bias it in a way that you do cheap drop ship vs expensive goods.
- Ben: It does potentially bias towards more rare conversions. Those would use less privacy budget, upper funnel would spend more of the budget.
- Charlie: I had the opposite intuition, you’d waste your budget early.
- Erik: You could spend very little ε in upper funnel events, and then more of it on lower funnel events.
- Aloïs (Idea to get more bias on a real life dataset) Ad techs usually measure several metrics per events. May want to have different bias/variance for different measurements.
- This is essentially what the budget management is created for.