search

TracingWithPrivacy / paper

A privacy preserving contact tracing design to battle infectious diseases
MIT License
28 stars 2 forks source link

Rendezvous addresses (SURBs) #11

Open burdges opened 4 years ago

burdges commented 4 years ago

As noted in https://github.com/TracingWithPrivacy/paper/issues/10#issuecomment-609003072 there are an excessive number of addresses in the current design.

We need 1440 addresses per user per day if we want new addresses at the 1 minute bluetooth announcement rate. We might reduce this by repeating addresses over several minutes, which costs privacy. We might reduce this by not broadcasting when the device believes the users to be home, but this sounds imperfect and could increases development costs substantially.

We must monitor these addresses daily, or more than daily, for 2 weeks, assuming nobody expects viruses with longer incubation times, so each user has 20k addresses open simultaneously. We cannot send poll 20k addresses per user per day because polling requires mixnet round trips, and this many messages breaks the mixnet's anonymity.

Instead, we separate the ephemeral "rendezvous" address from a long lived mailbox: Users deposit SURBs into their rendezvous addresses that route through the mixnet to their long lived mailbox. These SURBs should live for 2 weeks if addresses get populated by SURBs only once, or 1 week if we double traffic load on the mixnet, but doing this requires node keys rotate slowly enough.

We do still wind up storing 20k SURBs per user under this scheme, so maybe a couple petabytes for one billion users. We could avoid this storage if users queried the SURBs from the addresses they contacted, but doing so might not be cheaper than the storage.

JonathanLogan commented 4 years ago

Yes, that's something I also discussed with David over the weekend and that's the smart solution IMHO. Have long-lifetime (long mix epoch) SURBs for initial contact addresses, that then route to (fewer) mailboxes that are polled by the user through a short-epoch mixnet.

burdges commented 4 years ago

We'll broadcast a fresh address every couple minutes, but we could maybe avoid publishing SURBs to addresses for which we believe nobody received our beacon. We'd need some mechanism to distinguish bluetooth beacons for this system from beacons for ordinary devices.