I feel like the crypto in the COVID tracing apps is so simple that it doesn’t need much explanation. But I also see plenty of people nervous about the privacy these things provide. Is it worth explaining?
-
Show this thread
-
Replying to @matthew_d_green
I think there's some more to it that is going unappreciated. The Google/Apple scheme looks optimized for a hybrid between filter distribution (first pass) and exact-match confirmation (second pass) in a way that reduces bandwidth a lot.
1 reply 0 retweets 4 likes -
Replying to @colmmacc @matthew_d_green
Because things are derived deterministically by time, the app can fetch a filter, or a set of exact infected ids (whichever is smaller), that covers the time periods it knows it had contacts. And then see if there are any matches.
1 reply 0 retweets 1 like -
Replying to @colmmacc @matthew_d_green
Yes, but some people might consider fetching IDs by time a bug, not a feature. It allows Alice to know that Bob was infected because they met alone 3PM yesterday.
1 reply 0 retweets 4 likes -
Replying to @XorNinja @matthew_d_green
Good point, but the same applies to days anyway. In practice, which is better might hinge on whether the mobile providers are willing to zero-rate the daily dataset download.
1 reply 0 retweets 3 likes -
Replying to @colmmacc @matthew_d_green
Days are *slightly* better because Alice may also meet Mallory. Downloads can happen over WiFi at night, like how photos are being backed up. I agree less data is better.
1 reply 0 retweets 3 likes -
Replying to @XorNinja @matthew_d_green
If I crack the downloaded dataset (which at least has to be in memory on the phone), can't I narrow down the time to a 10 minute window anyway?
1 reply 0 retweets 0 likes -
Replying to @colmmacc @matthew_d_green
Yes, you can do that with the current scheme because pseudo ID X are derived from time T and key K. Knowing K and X, you can brute-force T. I hope that this time-based derivation will go away.
1 reply 0 retweets 1 like -
Replying to @XorNinja @matthew_d_green
If you're going to that volume of data, doing 63-bit ECDH between bluetooth senders is doable. Distribute a cuckoo filter to find the matches. That removes correlation and passive attacks. Though it does take bi-directional bluetooth ID receipt instead of unidirectional.
1 reply 0 retweets 1 like -
Replying to @colmmacc @matthew_d_green
There was a discussion about using blinded bloom filter to reduce download size. It was rejected because it enables the server to mount active targeted attacks
2 replies 0 retweets 3 likes
What if you make it two stage? bloom filter to determine if it's worth downloading a dataset of exact matches. The dataset can be sharded arbitrarily by the first N bits of matching IDs. Of course don't let N get too big.
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.