Downgrading the central authority in covid-19 tracing (part 4)

In part 3 of this blog series I sketched a system for tracing virus infections with minimal data leaked. The goal is still to let people warn each other about possible infection, but not give any clues to who has the infection or who is being warned. The end result was a system where:

• Igor being the infected person knew that Bob (possibly infected) was a member of a group G
• Bob knew the date of possible infection. If Bob interacted with many people that day, it’s difficult to guess who is infected. If he only met Igor that day, he will, unfortunately, have learned that Igor is infected

The central authority will also know that someone in group G may have been infected. By using the secretly known names and elimination, they may possibly guess who is infected (in particular if G is a small group, but the central authority may also fill G with dummy users, so that it effectively identifies a single person). In this way, if they track the group G that Igor is emitting, they are tracking him.

Furthermore, lets say each group represents a continent. Now if Igor travels from Asia (group A) to Europe (group E), every European he meets will identify him as the rare “Asian guy”, the only person with group A. Thus they will all know that every time they meet someone with group A, it’s probably Igor.

Note that guessing someone’s identity is not a fatal problem for infection tracking. Igor may know that he is warning Bob, but Igor still doesn’t know if Bob is infected (no one knows before Bob gets a test). And Bob will never know that Igor is the infected person warning him. Identifying someone may allow tracking though, if beacons are placed where Igor is moving about.

This suggests that you want to be grouped by location, and the location should be related to where you spend your time. If the group is sufficiently large, the location need not be very precise. But you definitively want to mingle with a few people sharing your group.

So in a revised scheme, each user registers in the central authority both with a public key and a City name, then the central authority groups individuals by Cities into sufficiently large groups (eg. combining smaller cities or splitting large ones). This solves the issue of being “the Asian guy” in Europe, just make sure to register for a group nearby where you stay, and keep it updated when you’re traveling.

Next we will solve the issue with the central authority being able to use elimination or dummy addresses to single out an individual. In part three I suggested using deterministic wallets to generate a new key every day. Today I scrap this idea and introduce a new scheme.

The public keys that are verified by the central authority will be called generation 0 keys. The central authority knows the identity of the public key’s owners. To create a generation 1 key, each user selects a new public key and group, then signs that with the generation 0 private key using a ring signature for the generation 0 group that was assigned by the central authority. A generation 2 key is likewise created based on a generation 1 key. It takes two periods to obtain a generation 2 key. Furthermore, generation 1 and 2 keys expire after a single period of 24 hours.

Every time a new generation key is created, the central authority will only know that a member of a group is now this particular a member of a second group. Lets assume the group size is 100, and the central authority has no additional data. After the second generation public key has been created, the central authority will only know any person is one out of 10.000 people.

Only generation 2 keys may be used as the public key when doing infection tracing.

If a user loses his private [generation 0] key, that user must re-verify with the central authority. As all generation 1 and 2 keys expire in a period, such keys are out of the system after a two period delay, even if the user secretly still has his private key. In this period, the user will not be able to generate a new generation 2 key, a process that takes two periods to perform.

With this change, the central authority no longer knows the identities of the people in a group or which group a certain person belongs to. Users may change their group at will. And still the invariant of one public key per user is taken care of.