Decentralized Privacy-Preserving Proximity Tracing

The DP-3T protocol works off the basis of Ephemeral IDs (EphID), semi-random rotating strings that uniquely identify clients.[23] When two clients encounter each other, they exchange EphIDs and store them locally in a contact log.[24] Then, once a user tests positive for infection, a report is sent to a central server. Each client on the network then collects the reports from the server and independently checks their local contact logs for an EphID contained in the report. If a matching EphID is found, then the user has come in close contact with an infected patient, and is warned by the client. Since each device locally verifies contact logs, and thus contact logs are never transmitted to third parties, the central reporting server cannot by itself ascertain the identity or contact log of any client in the network. This is in contrast to competing protocols like PEPP-PT, where the central reporting server receives and processes client contact logs.[25]

A diagram demonstrating how the different components of the Ephemeral ID algorithm feed into each other

Similar to the TCN Protocol and its Temporary Contact Numbers, the DP-3T protocol makes use of 16 byte Ephemeral IDs (EphID) to uniquely identify devices in the proximity of a client. These EphIDs are logged locally on a receiving client's device and are never transmitted to third parties.[1]

To generate an EphID, first a client generates a secret key that rotates daily (${\displaystyle SK_{t}}$) by computing ${\displaystyle SK_{t}=H(SK_{t-1})}$, where ${\displaystyle H()}$ is a cryptographic hash function such as SHA-256. ${\displaystyle SK_{0}}$ is calculated by a standard secret key algorithm such as Ed25519. The client will use ${\displaystyle SK_{t}}$ during day ${\displaystyle t}$ to generate a list of EphIDs. At the beginning of the day, a client generates a local list of size ${\displaystyle n=(24*60)/l}$ new EphIDs to broadcast throughout the day, where ${\displaystyle l}$ is the lifetime of an EphID in minutes. To prevent malicious third parties from establishing patterns of movement by tracing static identifiers over a large area, EphIDs are rotated frequently. Given the secret day key ${\displaystyle SK_{t}}$, each device computes ${\displaystyle S\_EphID(BK)=PRG(PRF(SK_{t},BK))}$, where ${\displaystyle BK}$ is a global fixed string, ${\displaystyle PRF()}$ is a pseudo-random function like HMAC-SHA256, and ${\displaystyle PRG()}$ is a stream cipher producing ${\displaystyle n*16}$ bytes. This stream is then split into 16-byte chunks and randomly sorted to obtain the EphIDs of the day.[1]

The DP-3T protocol is made up of two separate responsibilities, tracking and logging close range encounters with other users (device handshake), and the reporting of those encounters such that other clients can determine if they have been in contact with an infected patient (infection reporting). Like most digital contact tracing protocols, the device handshake uses Bluetooth Low Energy to find and exchange details with local clients, and the infection reporting stage uses HTTPS to upload a report to a central reporting server. Additionally, like other decentralized reporting protocols, the central reporting server never has access to any client's contact logs; rather the report is structured such that clients can individually derive contact from the report.[1]

When a user installs a DP-3T app, they are asked if they want to opt in to sharing data with epidemiologists. If the user consents, when they are confirmed to have been within close contact of an infected patient the respective contact log entry containing the encounter is scheduled to be sent to a central statistics server. In order to prevent malicious third parties from discovering potential infections by detecting these uploads, reports are sent at regular intervals, with indistinguishable dummy reports sent when there is no data to transmit.[1]

To facilitate compatibility between DP-3T apps administered by separate health authorities, apps maintain a local list of the regions a user has visited. Regions are large areas directly corresponding to health authority jurisdiction; the exact location is not recorded. The app will later connect these regions to their respective foreign central reporting server, and fetch reports from these servers in addition to its normal home reporting server. Apps will also submit reports to these foreign reporting servers if the user tests positive for infection.[1]

Cryptography and security scholar Serge Vaudenay, analyzing the security of DP-3T[28] argued that:

some privacy protection measurements by DP3T may have the opposite affect [sic] of what they were intended to. Specifically, sick and reported people may be deanonymized, private encounters may be revealed, and people may be coerced to reveal the private data they collect.

— Serge Vaudenay, [28]^{: p. 1}

Vaudenay's work presents several attacks against DP-3T and similar systems. In response, the DP-3T group claim that out of twelve risks Vaudenay presents, eight are also present in centralized systems, three do not work, and one, which involves physical access to the phone, works but can be mitigated.[29] In a subsequent work[30] Vaudenay reviews attacks against both centralized and decentralized tracing systems and referring to identification attacks of diagnosed people concludes that:

By comparing centralized and decentralized architectures, we observe that attacks against decentralized systems are undetectable, can be done at a wide scale, and that the proposed countermeasures are, at best, able to mitigate attacks in a limited number of scenarios. Contrarily, centralized systems offer many countermeasures, by accounting and auditing.

— Serge Vaudenay, [30]^{: p. 6}

In the same work[30] Vaudenay advocates that, since neither the centralized nor the decentralized approaches offer sufficient level of privacy protection, different solutions should be explored, in particular suggesting the ConTra Corona,[31] Epione[32] and Pronto-C2[33] systems as a "third way".

Tang[34] surveys the major digital contact tracing systems and shows that DP-3T is subject to what he calls "targeted identification attacks".

Theoretical attacks on DP-3T have been simulated[35] showing that persistent tracking of users of the first version of the DP-3T system who have voluntarily uploaded their identifiers can be made easy to any 3rd party who can install a large fleet of Bluetooth Low Energy devices. This attack leverages the linkability of a user during a day, and therefore is possible on within a day on all users of some centralized systems such as the system proposed in the United Kingdom,[36] but does not function on 'unlinkable' versions of DP-3T where infected users' identifiers are not transmitted using a compact representation such as a key or seed.[37]

• BlueTrace
• TCN Protocol
• Pan-European Privacy-Preserving Proximity Tracing
• Google / Apple contact tracing project

• DP-3T Github