6 ms·

To put some numbers to this: If you're living in a city with 10,000 new cases a day, with each case publishing 14 keys and each key being 16 bytes, it's a 2.2MB

To put some numbers to this: If you're living in a city with 10,000 new cases a day, with each case publishing 14 keys and each key being 16 bytes, it's a 2.2MB download a day (assuming incremental downloads). When you first install the app you might have to download all keys from the last 14 days, which would be about 15 MB.

loeg 6y ago
Probably don't need 16 byte keys, either. If you live in an area under 4 billion people you are unlikely to have any key collisions (for any given day) with a mere 8 bytes. If you can tolerate some probability of false positives, or have fewer than 4 billion people in your meta-region, shorter than 8 bytes is feasible. 16 -> 8 halves those data figures; diminishing returns from there, but it is possible to reduce the data use further (slightly).
byteshift 6y ago
My understanding is that this is even feasible without location information if you use an approximate filter (e.g., a Cuckoo Filter [1]), which they propose in DP-3T (II). With 20 bits/key such filters yield a false positive rate (FPR) of 0.001%. Meaning for 100,000 new cases per day worldwide, you would only need to download 0.24 MiB. Note that the FPR applies to each lookup. That is, if you have collected say 100 tokens on a given day, the overall probability of a false positive will be 0.01% (assuming independence). With each extra bit per key you can roughly halve that probability. So in practice size won't be an issue. [1] https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf
oarsinsync 6y ago
2.2 * 30 + 15 = 81MB For people with 200MB & 500MB data caps (which is a surprisingly large number of people), this is a significant amount of their data allowance. These are likely to be people that are still required to go out into the world and work, so are still using their data instead of wifi, and thus higher risk. It's easy to forget when you're on 10GB+ data plans for years just how many people are not.
- egoisticalgoat 6y ago
  That's assuming you're never connected to wifi within those 30 days. The apps could either let you choose to only download the list while on wifi, or it'll probably download the list in the middle of the night when it's reasonable to assume most people are at home near wifi.

loeg 6y ago

Probably don't need 16 byte keys, either. If you live in an area under 4 billion people you are unlikely to have any key collisions (for any given day) with a mere 8 bytes. If you can tolerate some probability of false positives, or have fewer than 4 billion people in your meta-region, shorter than 8 bytes is feasible. 16 -> 8 halves those data figures; diminishing returns from there, but it is possible to reduce the data use further (slightly).

byteshift 6y ago

My understanding is that this is even feasible without location information if you use an approximate filter (e.g., a Cuckoo Filter [1]), which they propose in DP-3T (II). With 20 bits/key such filters yield a false positive rate (FPR) of 0.001%. Meaning for 100,000 new cases per day worldwide, you would only need to download 0.24 MiB. Note that the FPR applies to each lookup. That is, if you have collected say 100 tokens on a given day, the overall probability of a false positive will be 0.01% (assuming independence). With each extra bit per key you can roughly halve that probability. So in practice size won't be an issue. [1] https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf

oarsinsync 6y ago

2.2 * 30 + 15 = 81MB For people with 200MB & 500MB data caps (which is a surprisingly large number of people), this is a significant amount of their data allowance. These are likely to be people that are still required to go out into the world and work, so are still using their data instead of wifi, and thus higher risk. It's easy to forget when you're on 10GB+ data plans for years just how many people are not.

egoisticalgoat 6y ago
That's assuming you're never connected to wifi within those 30 days. The apps could either let you choose to only download the list while on wifi, or it'll probably download the list in the middle of the night when it's reasonable to assume most people are at home near wifi.