4 ms·

https://covid19-static.cdn-apple.com/applications/covid19/current/static/contact-tracing/pdf/ContactTracing-CryptographySpecification.pdf https://covid19-static

by est31 7y ago

https://covid19-static.cdn-apple.com/applications/covid19/current/static/contact-tracing/pdf/ContactTracing-CryptographySpecification.pdf https://covid19-static.cdn-apple.com/applications/covid19/cu... > Upon a positive test of a user for COVID-19, their Diagnosis Keys and associated DayNumbers are uploaded to the Diagnosis Server. A Diagnosis Server is a server that aggregates the Diagnosis Keys from the users who tested positive and distributes them to all the user clients who are using contact tracing. Is this scalable? Earlier in the document they mentioned that the tracing keys are 16 bytes long. Let's assume that there are 3 million patients in a country. That'd be 48 megabytes each user has to download and process per day to check whether they've been in contact with an infected person (processing involves calculation of 144 HMACs per tracing key). I don't think this is feasible at scale and one can't avoid thinking about area recognizing diagnosis servers. E.g. Smartphones of patients would upload not just the diagnosis keys, but also the areas (county, district, something like that) they've been inside during that day. Then smartphones querying the diagnosis servers would have to send the areas they are interested in. But it's easy to see that this approach is then quite privacy invading. On the bright side, this info is already available to carriers so it's already a sunken cost so to speak.

mkagenius 7y ago
Seems like a scenario where bloom filter[1] could be useful. 1. https://en.wikipedia.org/wiki/Bloom_filter https://en.wikipedia.org/wiki/Bloom_filter
- est31 7y ago
  Bloom filters aren't good for privacy because if there is a hit, you have to upload the id to check it. Which tells the service a) which ID you encountered and b) if it's an ID that was confirmed to be affected, whether you are affected by corona or not, something the system was designed to prevent.
  - mkagenius 7y ago
    > if there is a hit, you have to upload the id to check it. Why would you upload it if you know (almost for sure) there was a hit? We can all live with small false positives I think.
  - jlokier 7y ago
    You don't have to upload the full id. It's enough to upload the bucket that was hit in the Bloom filter to fetch the subset of detailed data that corresponds to the bucket. If the buckets are coarse enough that doesn't reveal much. And if the Bloom filter is too fine-grained for that, fetch a set of buckets instead of one.
loeg 7y ago
3 million is way too high. Old infections aren't interesting for this; users only need to download newly reported infections since yesterday. Limiting to broad geographic regions would also help reduce scope and not be especially privacy invasive.
- est31 7y ago
  > Old infections aren't interesting for this Yes, healed patients who don't produce viruses any more aren't important, but anyone still infectious is still a danger. Even if you are supposed, often even legally required, to stay at home while being infected, there is no guarantee you aren't. I'd bet that most of these people also take their phones with them, after all far more serious criminals like actual murderers are often taking their phones to sites of crimes as well. The IDs of those devices are still relevant. Quarantine after diagnosis may last up to 14 days, so your phone should be uploading IDs for 14 days to the diagnosis server. Given continuation of exponential spread, we aren't far from having 3 million new patients within a span of two weeks in populous countries like the US.
  - FabHK 7y ago
    It’s new patients only, but for each day they might have been infectious. So, if it’s 100k new cases a day, and each uploads 5 days of keys, then it’s 8 MB. Seems doable, especially considering that you’d want to have fully blown lockdown during the exponential growth, and only then switch over to this contact tracing phase once the initial wave has abated.
sowbug 7y ago
https://en.wikipedia.org/wiki/Bloom_filter https://en.wikipedia.org/wiki/Bloom_filter
nkohari 7y ago
There wouldn't be 3 million new patients per day. Wouldn't each phone just need to download the newly-discovered cases since the last time they checked?
- est31 7y ago
  Each patient creates a new key per day. Only those keys are uploaded. So everyone who is positive in the app needs their keys to be uploaded. At least this would be a reasonable design choice of the app. Maybe the designers of the app assume you actually follow the quarantine that infected people should do and don't leave your home. In that case, the app can stop uploading of those daily keys.
- FabHK 7y ago
  Say a newly identified case is assumed to have been infectious for the preceding week. My reading of the spec is that they’d upload 7 diagnosis keys (which all devices would have to download).
mmcnl 7y ago
Is your calculation correct? You only need to download the Diagnosis Keys. How would that be 48MB?
- est31 7y ago
  I used the definition 1 MB == 1 000 000 bytes (there are several definitions for what a megabyte is). Each diagnosis key has 16 bytes. 16 bytes * 3 million patients = 48 million bytes = 48 MB. Note that not just the diagnosis are uploaded but also day numbers. Those follow strict power laws and compress pretty well with even the simplest entropy coding schemes to a sub byte size.
gok 7y ago
48MB per day just isn't that much these days.
- Saaster 7y ago
  For reference WhatsApp is ~70MB (that's considered small) and a Facebook app is ~380MB on iOS.
  - est31 7y ago
    Both are one time downloads with comparatively rare updates. Users can visit a place with WiFi for doing the download. The daily dataset of infected users however can't wait for manual prompting and is thus likely downloaded in the background. Users might not always be able to connect their devices to WiFi. In many countries, traffic quotas are quite limited.

by est31 7y ago

mkagenius 7y ago

Seems like a scenario where bloom filter[1] could be useful. 1. https://en.wikipedia.org/wiki/Bloom_filter https://en.wikipedia.org/wiki/Bloom_filter

est31 7y ago
Bloom filters aren't good for privacy because if there is a hit, you have to upload the id to check it. Which tells the service a) which ID you encountered and b) if it's an ID that was confirmed to be affected, whether you are affected by corona or not, something the system was designed to prevent.
- mkagenius 7y ago
  > if there is a hit, you have to upload the id to check it. Why would you upload it if you know (almost for sure) there was a hit? We can all live with small false positives I think.
- jlokier 7y ago
  You don't have to upload the full id. It's enough to upload the bucket that was hit in the Bloom filter to fetch the subset of detailed data that corresponds to the bucket. If the buckets are coarse enough that doesn't reveal much. And if the Bloom filter is too fine-grained for that, fetch a set of buckets instead of one.

loeg 7y ago

3 million is way too high. Old infections aren't interesting for this; users only need to download newly reported infections since yesterday. Limiting to broad geographic regions would also help reduce scope and not be especially privacy invasive.

est31 7y ago
> Old infections aren't interesting for this Yes, healed patients who don't produce viruses any more aren't important, but anyone still infectious is still a danger. Even if you are supposed, often even legally required, to stay at home while being infected, there is no guarantee you aren't. I'd bet that most of these people also take their phones with them, after all far more serious criminals like actual murderers are often taking their phones to sites of crimes as well. The IDs of those devices are still relevant. Quarantine after diagnosis may last up to 14 days, so your phone should be uploading IDs for 14 days to the diagnosis server. Given continuation of exponential spread, we aren't far from having 3 million new patients within a span of two weeks in populous countries like the US.
- FabHK 7y ago
  It’s new patients only, but for each day they might have been infectious. So, if it’s 100k new cases a day, and each uploads 5 days of keys, then it’s 8 MB. Seems doable, especially considering that you’d want to have fully blown lockdown during the exponential growth, and only then switch over to this contact tracing phase once the initial wave has abated.

sowbug 7y ago

https://en.wikipedia.org/wiki/Bloom_filter https://en.wikipedia.org/wiki/Bloom_filter

nkohari 7y ago

There wouldn't be 3 million new patients per day. Wouldn't each phone just need to download the newly-discovered cases since the last time they checked?

est31 7y ago
Each patient creates a new key per day. Only those keys are uploaded. So everyone who is positive in the app needs their keys to be uploaded. At least this would be a reasonable design choice of the app. Maybe the designers of the app assume you actually follow the quarantine that infected people should do and don't leave your home. In that case, the app can stop uploading of those daily keys.
FabHK 7y ago
Say a newly identified case is assumed to have been infectious for the preceding week. My reading of the spec is that they’d upload 7 diagnosis keys (which all devices would have to download).

mmcnl 7y ago

Is your calculation correct? You only need to download the Diagnosis Keys. How would that be 48MB?

est31 7y ago
I used the definition 1 MB == 1 000 000 bytes (there are several definitions for what a megabyte is). Each diagnosis key has 16 bytes. 16 bytes * 3 million patients = 48 million bytes = 48 MB. Note that not just the diagnosis are uploaded but also day numbers. Those follow strict power laws and compress pretty well with even the simplest entropy coding schemes to a sub byte size.

gok 7y ago

48MB per day just isn't that much these days.

Saaster 7y ago
For reference WhatsApp is ~70MB (that's considered small) and a Facebook app is ~380MB on iOS.
- est31 7y ago
  Both are one time downloads with comparatively rare updates. Users can visit a place with WiFi for doing the download. The daily dataset of infected users however can't wait for manual prompting and is thus likely downloaded in the background. Users might not always be able to connect their devices to WiFi. In many countries, traffic quotas are quite limited.