Infection reveals lots, so consider using cuckoo filters about documents HOT 17 CLOSED

I do not get why they want an infected user to share their sk_t with others. It should be only shared with the server to confirm that infected person is one it claims to be (proving ownership of given ephids).
But it is better to publish ephids instead.

from documents.

I'd assume they're concerned the ephids would be too numerous.

from documents.

@burdges And that is why ephids probably should be published in the form of some Bloom(-ish) filters as many has pointed out before.

from documents.

I briefly thought about that, but I did not notice any such issues, and did not work out the filter parameter space myself. We should close this issue in favor of whatever issue worked out the filter parameters.

from documents.

If your target false positive rate lies blow 3%, which it obviously does here, then cuckoo filters are more space efficient than bloom filters. As a quick guesstimate, we require about only a couple bytes per newly infected person in the daily cuckoo filter, so I think distributing this daily cuckoo filter sounds doable via libtorrent.

I've renamed this issues because seemingly no existing discussions covered this.

from documents.

I honestly never heard before of Bloom or cuckoo filters, but can you help me understand how they mitigate #37?

If the published infected info is neither the set of his EphIDs or the sk_t that generated them, but rather the Bloom/cuckoo filter for his set of EphIDs, can't malicious users just test all the EphIDs they tracked against the filter?

from documents.

@inaitana Cuckoo/Bloom filters are probabilistic data structures. They have a given (and adjustable) ratio of false-positives. And we would sacrifice some false-positives for a small privacy gain. Attacker can't be sure if the given EphID was in fact marked, or it is just a false-positive.

from documents.

Ok, but if the attackers built a significative history of EphIDs locations false positives wouldn't be much of a problem.

Every person must have an EphID in every significative timeframe (a day, in the current proposed implementation) when tracing is desired to happen. This is required for the solution to work.
If you have false positives and no false negatives (and a low enough chance of not tracing the user during a timeframe), then you will have more than one match for some timeframe.
You can still determine which is the correct one for each timeframe by analyzing frequent locations.

Let's say you analyse 14 days traffic, and 16 EphIDs test positive against an infected person's filter.
You can infer 2 of them are false positives.
If 14 of them were in the same location at the same time (at home in the evening, at office during working hours...), and 2 were in another one, the false positives are filtered out.

This implementation would just slightly mitigate the problem by adding some false locations for the infected person (which can be filtered out), but most of the person's location history, especially domicile and frequent locations, could still be pinpointed effectively.

And this would be at the cost of creating false positive alarms for regular users.

from documents.

I'm considering the possibility to not publish EphIDs but let clients periodically query the backend for their EphIDs presence. Clients can query only for theirs EphID.

This will permit to not publish any data, sk_t nor EphIDs at all.

from documents.

Incorrect @jasisz we do not improve privacy meaningfully from false positives. We improve location privacy for infected people dramatically by their ephids not being linked together. We'd batch all infections detected over a couple day period into one large cuckoo filter.

Any private query scheme incurs significant privacy costs @camstork especially if you must query daily for all 20,000 ephids from a 2 week period (one fresh ephids one per minute). We prefer cryptographic or unbreakable location privacy for uninfected individuals, but a PIR-like query exposes their location if all servers collude. We've discussed SURB schemes on the mixnet repo, in which users "pre-query each ephid only once" by supplying a SURB, but mixnet schemes lie outside DP-3T.

from documents.

@burdges This can be also achieved by other means, e.g. #14 or #35
But this is still possible to do what I've described in #13 or others in #27, false-positives of Cuckoo filters on top of that add a little bit of privacy.

from documents.

They've added why they discarded our propositions in FAQ: https://github.com/DP-3T/documents/blob/master/FAQ.md

from documents.

@burdges batching multiple infections into one filter would be a good idea and partially hinder consistently backtracing a single infected user's locations.
But still it would be failry easy to observe frequent locations in the batch and identify homes and workplaces of infected users.
And then possibly try linking EphIDs from that.

from documents.

You cannot "link ephids" created with a PRF for which the key remains secret.

You can expose infected peoples' real identities under all proposed solutions though.

from documents.

I meant empirically linking them together by analyzing frequent locations.
But this would be secondary to detecting frequent locations (and possibly identities) themselves.

from documents.

They've added it to the doc as an alternative design.

from documents.

We have added an alternative design in the new version of the whitepaper. The alternative design uses cuckoo filters, comments welcome! We documented the main trade-offs between the two designs.

from documents.