Cryptographically Distributed COVID contact tracing through WiFi ad-hoc networking

2020 April 10
by Daniel Lakeland

This is a quick note to try to sketch out an idea that I thought up about how to have people cooperatively determine if they have come in contact with a COVID patient. Here’s the basic idea.

Every Android or iPhone generates a random UUID. Then, when walking around, periodically the phones beacon out a peer-to-peer SSID on their WiFi radios called something like COVID-CONTACT-{UUID}. Everyone’s phones scans the surroundings for stations, and whatever stations they hear, they record the UUID of the phone.

Now… at the end of the day, each phone uploads a one-way cryptographic hash of their own UUID, and the UUIDs that they contacted today.

If a person tests COVID positive, they upload a record of their cryptographic hash, and the fact that they tested positive.

Now, every day you look at all the contacts you’ve contacted in the last ~ 10 days, you hash those, and you see if any of those hashes report being COVID positive. Also, you look up all the COVID positives in the last 10 days, and you see if they report having contacted YOUR hash…

Now, there’s probably some subtlety to this which requires working out by people who are more crypto nerdy than I am, but the dataset is such that you can’t determine whether A contacted B unless you know the UUID of *both* parties. Since the UUID itself is stored internal to the app and never sent to anyone else, basically the UUID itself is a secret, and it’s only possible to determine if A contacted B or vice versa if you are in fact either A or B.

Of course, you could just try EVERY UUID that’s possible… Good luck with that, since there are ~ 2^128 = 340282366920938463463374607431768211456 of them. If you tried 1 Million per second, it’d take 10^25 years to try them all.

So, is this a viable non-invasive contact tracing strategy? What am I missing?

No comments yet

Leave a Reply

Note: You can use basic XHTML in your comments. Your email address will never be published.

Subscribe to this comment feed via RSS