Minimal data leakage covid-19 tracing part 3

I am trying to design a virus infection tracking system that does not leak any information. This third attempt uses linked ring signatures to hide the identity of the participants.

I compare the privacy of many tracing apps to this approach in part 5 of this series.

This is the work of a happy amateur. You might see other serious work on this elsewhere or even here, though I believe there may be some important advances in here.

Imagine Igor meets Bob, and it turns out Igor is infected at a later point in time. The system being described has the following properties

• Igor has a way of warning Bob that he may have been infected at a certain date
• Bob will not know who is issuing the warning except what he can deduce from the date (eg only one rendezvous on that date)
• Bob will not know any information pinpointing Igor, other than his membership in a group
• The public will know the date the rendezvous took place and which group Bob belongs to
• Only Bob (other than Igor) knows about the infection warning
• It is not possible to track a person as the emitted tokens change at every rendezvous
• A central authority is required to keep track of each person’s public key and assigning them to a single group
• Igor does not learn Bob’s public key or vice versa, only which group it belongs to

The reason a central authority is needed is to make sure every user just has a single identity. If this was not the case, a new identity could be created for every rendezvous. The central authority will know only the public key assigned to each user. The central authority can’t use the public keys to figure out information about other transactions.

The system depends on linked ring signatures, as described in https://doi.org/10.1007/11424826_65.

To make the system work, some infrastructure is required to be maintained by a central authority. Every real person may submit exactly one public key. Every new date, the key is progressed one generation in a deterministic fashion as described in Bitcoin BIP-32 Hierarchical Deterministic Wallets. Because a new public key is used every day, Bob will know for a fact that Igor may have infected him on a specific date, because of the key that Bob would use on that day is the only one to decode the infection warning.

The system assigns each user to a group depending on their order of participation. Eg. users 1 through 10.000 are in group 1, 10.001 through 20.000 are group number two etc. The grouping should be stable, a single user should remain in the same group day after day. The list of public keys and groups is frozen at midnight every day for 24 hours.

The size of the groups should be as large as possible, though there might be some practical limits such as the processing time and memory required to calculate the ring signatures.

The public keys and their groups are stored in a publicly accessible registry, known to all.

When Igor meets Bob, Bob starts out by sending Igor a random value R. Using the ring signature for Igor’s group, Igor signs R and returns it along with Igor’s group G to Bob. If Igor has seen R previously, he may and should decline to sign it. We will call the signature σ1. σ1 proves that Igor is a member of a group G and thus a real person in the central registry.

Nothing more is done until later when Igor is verified to be infected by the virus. The doctor creates a message containing: (infection id, The first date of possible infection, the last date of possible infection, the group G, the doctor’s signature). The message is published at the central registry.

Less important note: The doctor may also sign with a ring signature to avoid revealing exactly which doctor who verified the infection.

When Bob sees that someone in his group may have been infected, he creates a brand new public key P1, and signs it with a linked ring signature once for each date in question. This data, (infection id, P1, σ2), is published to the central registry.

When Igor scans through the registry for anything related to his infection id, he finds Bob’s record. He can verify that σ1 and σ2 is indeed signed by the same member of group G. Thus he can encrypt a message (eg. “You are affected by infection id x”) with P1 so that only Bob is able to read it using his private key S1. Then he publishes the (infection id, ciphertext) to the public registry.

Finally, Bob picks up the ciphertext from the public registry, and using the key for the correct date, chosen by trial and error, he finds out that one of them unlocks the warning about a possible infection.

This ends the exchange of information.

In part four, we limit the amount of information that the central authority needs to keep secret.