Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Infection reveals lots, so consider using cuckoo filters #24

Closed
burdges opened this issue Apr 4, 2020 · 17 comments
Closed

Infection reveals lots, so consider using cuckoo filters #24

burdges opened this issue Apr 4, 2020 · 17 comments
Labels
privacy risk Questions or comments regarding privacy issues and concerns protocol Questions about the protocol/cryptography will-close-soon-without-further-input For discussions that seem resolved (or stalled). We do so to be able to handle new issues.

Comments

@burdges
Copy link

burdges commented Apr 4, 2020

If I understand, an infected user reveals the linkage between all their ephids by revealing their sk_t. It's quite efficient solution, but revealing this linkage might discourage adoption and/or discourage disclosure. I'd think too few individuals worry about their privacy enough for this to be a serious problem.

There is however some risk that individuals might observe and publish ephids along with location information, which ties published sk_t to real movements. If done, this could harm adoption or increases disclosure refusals more than linkability concerns.

We could consider doing the hashing inside some trusted enclave, except iOS lacks this. If iOS proves unworkable for other reasons like #7 then this sounds more plausible.

Instead, I'd suggest merely giving user control over pausing and switching between sk chains whenever they like. I doubt devices could manage a few independent sk chains automatically, but appl forks could attempt to do this too.

@jasisz
Copy link

jasisz commented Apr 4, 2020

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.

@burdges
Copy link
Author

burdges commented Apr 4, 2020

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

@jasisz
Copy link

jasisz commented Apr 5, 2020

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

@burdges
Copy link
Author

burdges commented Apr 5, 2020

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.

@burdges
Copy link
Author

burdges commented Apr 5, 2020

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.

@burdges burdges changed the title Infection reveals lots Infection reveals lots, so use a cuckoo filter Apr 5, 2020
@burdges burdges changed the title Infection reveals lots, so use a cuckoo filter Infection reveals lots, so consider using cuckoo filters Apr 5, 2020
@s-chtl s-chtl added privacy risk Questions or comments regarding privacy issues and concerns protocol Questions about the protocol/cryptography labels Apr 6, 2020
@inaitana
Copy link

inaitana commented Apr 6, 2020

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?

@jasisz
Copy link

jasisz commented Apr 6, 2020

@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.

@inaitana
Copy link

inaitana commented Apr 6, 2020

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.

@camstork
Copy link

camstork commented Apr 7, 2020

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.

@burdges
Copy link
Author

burdges commented Apr 7, 2020

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.

@jasisz
Copy link

jasisz commented Apr 7, 2020

@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.

@jasisz
Copy link

jasisz commented Apr 7, 2020

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

@inaitana
Copy link

inaitana commented Apr 7, 2020

@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.

@burdges
Copy link
Author

burdges commented Apr 7, 2020

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.

@inaitana
Copy link

inaitana commented Apr 7, 2020

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

@jasisz
Copy link

jasisz commented Apr 8, 2020

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

@cascremers
Copy link
Collaborator

cascremers commented Apr 8, 2020

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.

@lbarman lbarman added the will-close-soon-without-further-input For discussions that seem resolved (or stalled). We do so to be able to handle new issues. label Apr 14, 2020
@lbarman lbarman closed this as completed Apr 15, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
privacy risk Questions or comments regarding privacy issues and concerns protocol Questions about the protocol/cryptography will-close-soon-without-further-input For discussions that seem resolved (or stalled). We do so to be able to handle new issues.
Projects
None yet
Development

No branches or pull requests

7 participants