Private measurement of single events

[csharrison]

I’m posting an issue based on a discussion that happened in patcg-individual-drafts/ipa#60. In that issue, I proposed a new privacy mechanism satisfying differential privacy that works best in the model where individual events are queried, rather than multiple events aggregated together and queried together. While this is a setting where currently both IPA and ARA have no restrictions, we thought it best to bubble up the conversation to this group in general to discuss.

With per-event output, typically results are only useful if you aggregate them in some way after the privacy mechanism / noise is applied (similar in some sense to local DP), otherwise data is too noisy to do anything useful with it. This is also usually a huge headache because it drowns your data in much more noise than it would normally (e.g. for simple aggregates, noise standard deviation scales with O(sqrt(#users)) vs. O(1)). However, there are a few big reasons why this is useful:

• Post-processing is “free”: Adding noise before aggregation means that you can allow for flexible aggregation as a post-processing step, separate from the platform or any trusted server infra. You can always “requery” an already-noised piece of data as many times as you want without paying more privacy budget, because the privacy is “built into” the data. For certain deployments with many downstream use-cases that otherwise would need a lot of requerying, this can end up being a more efficient mechanism.
• Pushes complexity out: If the aggregation is very complicated , potentially stateful, or difficult to pull off in MPC or at-scale, then event-level output frees the report collector to be able to implement this themselves. This is particularly useful for things like model training where the “aggregation” step is potentially an entire training pipeline. In fact, the motivation for the mechanism I proposed in Consider a randomized-response-like privacy mechanism patcg-individual-drafts/ipa#60 is to support recent research in private model training, where alternatives like DP-SGD are much more complex to support.

The main questions for the group are:

• Are we comfortable with per-event queries that satisfy a similar differential privacy bar as aggregates would? Is differential privacy alone satisfactory for us, or do we need an auxiliary privacy notion to protect against these kinds of queries?
• If not, how should we formalize the kind of protection we want that prevents them? Are these protections realistic within our threat model (sybil attacks, etc)?

Personally, I think we should support this kind of privacy mechanism as long as it satisfies our high level differential privacy bounds, given the benefits listed above, the challenges inherent with protecting this boundary, and the robustness of DP as a definition.

cc @eriktaubeneck @benjaminsavage @bmcase

[benjaminsavage]

Thanks for filing this issue Charlie, and I'm glad to see it's going to be a discussion topic at our next meeting.

I guess the big question is: Do we believe a "Private Measurement API" must necessarily include aggregation?

• PCM does not necessarily include aggregation, but the total number of individuals for whom you can query event level data is just 256 per website, which makes it economically unattractive to try to use the API for this purpose.

I would really love to hear what Mozilla, Brave, and Webkit think about this topic. CC: @martinthomson, @ShivanKaul, @johnwilander

If we think the answer is "Yes, a private measurement API must necessarily include aggregation", we should discuss what mechanisms we could use to try to enforce that.

1. There is the PCM approach, where you limit the total number of breakdowns, such that there is an upper bound on how many single events can be measured.
2. You can enforce a minimum threshold of at least K inputs having a given breakdown key. If an adversary can generate K-1 fake events, this doesn't make it technically impossible to measure single events, but it makes it cost K-times as much to do so.
3. You can enforce a minimum threshold of at least K events which contribute to the output for a given breakdown key. The same logic applies about adversaries who can generate fake events, with the added concern that this will make reporting effectively useless for small advertisers, who often have small budgets with only a handful of total attributed conversions.
4. We can just make sure that we chose epsilon such that the signal-to-noise ratio if terrible you attempt to measure a single event, effectively making it unattractive to even attempt to do so.

That's all the ideas that immediately come to mind, but I might be missing something. Happy to hear other ideas from other people!

[bmcase]

CC also Luke Winstrom @winstrom as you shared a lot perspectives from Apple at the last PATCG F2F.

[csharrison]

@benjaminsavage thanks for that breakdown of enforcement mechanisms. I do want to emphasize that all of these mitigations (1-3) are just that: mitigations. They can all be broken with a sophisticated enough attacker, especially if that attacker is interested in targeting a small population of people.

I also want to mention that while (2) and (3) are "easy" to break if the adversary can generate fake records as you mentioned, they can still be broken even if the adversary does not have that capability and is truly restricted to aggregating honestly generated events. e.g. for (2) if the system supports overlapping queries, issuing a query over sources {s_1, s_2, ..., s_k} and {s_2, ..., s_k} and taking their difference gives you the count for the single event s_1. (3) is the same as long as the queries cover enough conversions¹. Even if the mechanism is randomized and provides an additional DP guarantee all this does is put you back in option (4): single event counts w/ DP.

In summary, this boundary is extremely difficult to enforce rigorously. I am nervous that attempting to do so will result in less useful measurement capabilities (e.g. disallowing overlapping queries), or making overly ambitious assumptions about the attacker's capabilities (e.g. fake record generation, auxiliary information, etc).

Footnotes

1. k-anonymity and its flavors are notorious for their susceptibility to these kinds of composition attacks. See e.g. Ganta et. al. 2008 and many others. ↩

[bmcase]

Another mitigation similar to (2), (3) which brings the economic disincentive against getting individual level outputs but which doesn't require complicated checks in the MPC is:

5. For any query require that the ratio of the number of source reports to number of breakdowns is at least some K.

[csharrison]

FYI I have uploaded a PR with some text which I think captures what was discussed in the May meetings, but we are looking for feedback on this and will not merge it for some time (@AramZS for exact details on how long we'll wait for consensus)