Re: [docs-and-reports] Private measurement of single events (#41)

@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[^1]. 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_. Attempting to do so will likely 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). 

[^1]: k-anonymity and its flavors are notorious for their susceptibility to these kinds of composition attacks. See e.g. [Ganta et. al. 2008](https://arxiv.org/abs/0803.0032) and many others.

-- 
GitHub Notification of comment by csharrison
Please view or discuss this issue at https://github.com/patcg/docs-and-reports/issues/41#issuecomment-1518713499 using your GitHub account


-- 
Sent via github-notify-ml as configured in https://github.com/w3c/github-notify-ml-config

Received on Saturday, 22 April 2023 17:35:27 UTC