ANONYMOUS DISTRIBUTED CONTACT TRACING AND VERIFICATION SYSTEM

Abstract

An automated contact tracing system for anonymously identifying contacts between users includes at least a tracing server; and more than one mobile device or wearable of a user comprising means for short-range proximity communication and means for carrying out a computer program for generating Encounter-Tokens, when one user spent a pre-defined amount of time in a pre-defined proximity range of another user.

Claims

1. An automated contact tracing system for anonymously identifying contacts between users, the system comprising: at least a tracing server; and more than one mobile device or wearable of a user comprising means for short-range proximity communication and means for carrying out a computer program for generating Encounter-Tokens, when one user spent a pre-defined amount of time in a pre-defined proximity range of another user.

2. The system of claim 1, further comprising a server of a health authority being connectable to the tracing server and a mobile device of a user.

3. A method for operating an automated contact tracing system for anonymously identifying contacts between users comprising the following steps: a) sending a cryptographic token from a mobile device of a first user; b) receiving another cryptographic token from a mobile device of a second user being within a pre-defined amount of time in a pre-defined proximity range of the first user; c) generating an encrypted encounter token on the mobile device of the first user based on information included in the received cryptographic token and the sent cryptographic token; d) storing the generated encounter token locally on the mobile device of the first user; e) uploading the encounter token generated on the mobile device of the first user to a tracing server; f) downloading encounter tokens stored on the tracing server to a mobile device of a user; and g) contact verification based on encounter tokens downloaded by the user.

4. The method according to claim 3, further comprising verification of infected users with an infectious disease by receiving an authentication code issued by a health authority server on the mobile device of the first user and sending the authentication code from the mobile device of the first user to the tracing server which compares the received authentication code with a list of valid authentication codes received from the health authority server.

5. The method according to claim 4, wherein a proximity communication protocol used is Bluetooth Low Energy, ZigBee, or Z-Wave.

6. The method according to claim 3, wherein a proximity communication protocol used is Bluetooth Low Energy, ZigBee, or Z-Wave.

7. A method for operating a tracing server in an automated contact tracing system for anonymously identifying contacts between users comprising the following steps: a) receiving encounter tokens generated by mobile devices of users; b) storing encounter tokens for a pre-defined duration; c) allowing stored encounter tokens to be downloaded to a mobile device of a user.

8. The method according to claim 7, further comprising automatic deletion of encounter tokens after a pre-defined duration.

9. The method according to claim 8, further comprising voluntary sharing of contact data between users.

10. The method according to claim 7, further comprising voluntary sharing of contact data between users.

11. The system of claim 1 wherein the computer program comprises a computer program for generating Encounter-Tokens, when one user has spent a specific amount of time in a pre-defined proximity of another user comprising instructions which, when the program is executed by a computer, causes the computer to carry out: receiving a cryptographic token from a Tracing App of another user; generating a cryptographic token of the user's Tracing App that was valid at the time when the other cryptographic token was received; and calculating an Encounter-Token with an Encounter-Token derivation function.

12. The system of claim 11, which when the program is executed by a computer, causes the computer to generate a random ephemeral cryptographic token.

13. The system of claim 12, which when the program is executed by a computer, causes the computer to advertise the random ephemeral cryptographic token over a proximity communication protocol.

14. The system of claim 11, which when the program is executed by a computer, causes the computer to store received cryptographic tokens locally for further processing.

15. The system of claim 12, which when the program is executed by a computer, causes the computer to store received cryptographic tokens locally for further processing.

16. The system of claim 13, which when the program is executed by a computer, causes the computer to store received cryptographic tokens locally for further processing.

17. The method according to claim 7 wherein each mobile device of the users comprises a mobile device or a wearable device comprising means for short-range proximity communication and means for carrying out a computer program for generating Encounter-Tokens.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0031] In order to best describe the manner in which the above-described embodiments are implemented, as well as define other advantages and features of the disclosure, a more particular description is provided below and is illustrated in the appended drawings. Understanding that these drawings depict only exemplary embodiments of the invention and are not therefore to be considered to be limiting in scope, the examples will be described and explained with additional specificity and detail through the use of the accompanying drawings in which:

[0032] FIG. 1a illustrates a System overview, according to an embodiment of the invention.

[0033] FIG. 1b illustrates a System overview including a server of a Health Authority, according to an embodiment of the invention.

[0034] FIG. 1c illustrates an Encounter Token establishment, according to an embodiment of the invention.

[0035] FIG. 2 illustrates an infection status verification, according to an embodiment of the invention.

[0036] FIG. 3 illustrates an Encounter Token upload, according to an embodiment of the invention.

[0037] FIG. 4 illustrates an Encounter Token download and contact verification, according to an embodiment of the invention.

DETAILED DESCRIPTION

[0038] Various embodiments of the disclosed system and methods are discussed in detail below. While specific implementations are discussed, it should be understood that this is done for illustration purposes only. A person skilled in the relevant art will recognize that other components, configurations, and steps may be used without departing from the spirit and scope of the disclosure.

[0039] FIG. 1a shows a system overview for an embodiment of the present invention. The system 18 comprises two main components, namely respective Tracing apps 20, 22 and a Tracing server 24. The tracing app 20, 22 are installed on respective mobile devices 26, 28 of the user A 30 and user B 32. The mobile devices 26, 28 communicate through a short-range proximity communication protocol with each other. Further, each mobile device 26, 28 of user A 30 and user B 32 communicates with a tracing server 24.

[0040] FIG. 1b illustrates another embodiment including a server 34 of a Health Authority 36. This server 34 is connected to a user A 30 which has been infected and with the tracing server 24, to allow the tracing server to communicate the risk of infection due to prior contact with an infected person to user B 32 who had an encounter with user A 30.

[0041] The operation of the system 18 of FIG. 1a and FIG. 1b may comprise the following steps:

1. Establishing encounter tokens;
2. Optional verification of infected users if used in an epidemiological context;
3. Encounter token upload to a tracing server;
4. Encounter token download from a tracing server and contact verification;
5. Optional sharing of contact data for epidemiologic research if accepted by the user.

[0042] For establishing Encounter Tokens, the Tracing App 20, 22 of a user 30, 32 uses a proximity communication protocol with limited range to sense the presence of tracing Apps from other users 30, 32. In one embodiment of the invention, the used proximity communication protocol could be Bluetooth Low Energy. In other embodiments of the invention, other proximity communication protocols like ZigBee®, Z-Wave® or similar protocols can be used. Each generates a random ephemeral cryptographic token and advertises this over the proximity communication protocol. Tracing Apps 20, 22 on devices of other users 30, 32 in the proximity sense these tokens and store them locally on the mobile device 26, 28 of the other user 30, 32 for further processing.

[0043] In one embodiment of the invention, this cryptographic token contains a randomly-generated ephemeral public key associated with the Tracing App 20, 22 of a user 30, 32. In another particular embodiment of this invention, the ephemeral public key is an Elliptic Curve public key. The cryptographic token advertised by the Tracing App 20, 22 of a user 30, 32 must be changed frequently to thwart tracing attacks against the tracing app of the user. In one embodiment of the invention, the cryptographic token is changed every 30 minutes.

[0044] Each Tracing App 20, 22 of a user 30, 32 continuously advertises its cryptographic token that is currently valid and records any other cryptographic token generated and sent by a tracing app 20, 22 of another user 30, 32 it can sense in a pre-defined proximity. When the tracing App 20, 22 of a user 30, 32 detects a cryptographic token emitted by a Tracing App 20, 22 of another user 30, 32, it will store the detected token locally and perform an Encounter Token derivation function to derive an Encounter Token for the encounter with the other user 30, 32.

[0045] When a mobile device 26, 28 finds another mobile device 26, 28 the two devices start the Ephemeral Cryptographic Token Exchange. First, one device 26, 28 starts the Bluetooth client and the another device 26, 28 starts the Bluetooth server and both devices exchange their Cryptographic Tokens (CTs) (520-bit length). Both devices 26, 28 store the CTs which later on are used to calculate encounter tokens (ET). CT may be changed every 30 minutes along with Ephemeral Identifier (EID). During a 30-minute lifetime, to save energy, CT may only be sent when the device 26, 28 finds a new device 26, 28.

[0046] At least the following data items are given as input to the Encounter Token derivation function: the received cryptographic token of the Tracing App 20, 22 of the other user 30, 32 and the generated cryptographic token of the own Tracing App 20, 22 that was valid at the time when the other cryptographic token was received. Based on these inputs, an Encounter Token is calculated by the Encounter Token derivation function.

[0047] In one embodiment of this invention, shown in FIG. 1c, the Encounter Token derivation function performs a known Elliptic Curve Diffie-Hellman (ECDH) key exchange algorithm, in which the Encounter Token is a session key established using the cryptographic tokens representing the public keys of the corresponding Tracing Apps 20, 22.

[0048] In another embodiment of the invention, the Diffie-Hellman key exchange algorithm is used. In yet another embodiment of the invention, also a symmetric key agreement protocol can be used.

[0049] In yet another embodiment of the invention, the encounter derivation function may be a simple exclusive or operation (XOR) applied on the cryptographic tokens (CT).

[0050] In one embodiment of the invention, the cryptographic token generation function and the Encounter Token derivation function are executed during the time when the mobile device 26, 28 is being charged, e.g., during the night, in order to preserve battery lifetime of the mobile device.

[0051] Each Tracing App 20, 22 stores the derived Encounter Tokens locally together with metadata characterizing the encounter. In one embodiment of the invention, the metadata comprises at least following data items: duration of the encounter, signal strengths associated with the encounter as well as other contextual information about the encounter. In another embodiment of the invention, the app will also store the location of the encounter as metadata.

[0052] In order to make sure that only users who really have been infected can report their Encounter Tokens, the system must verify the infection status of the user 30, 32 submitting their Encounter Tokens to the Tracing Server 24 (FIG. 1b). This can be done in a number of ways.

[0053] In one embodiment of the invention, as shown in FIG. 2, a Health Authority Server 34 will issue an authentication code auth-code to a user 30 who has been tested positive for the disease. To verify his infection status the user 30 will enter this authentication code auth-code into the Tracing App 20. The Tracing App 20 will then use the authentication code auth-code for deriving an authenticator value auth-val when uploading Encounter Tokens to the Tracing Server 24. In another embodiment of the invention, the Tracing App 20 derives the authenticator value auth-val using the authentication code auth-code and other metadata like a date, a timestamp or a location code.

[0054] In yet another embodiment of the invention, the authentication code auth-code can be given in the form of a QR code printed on paper or transmitted as a PDF file by e-mail. The user 30 may then use the Tracing App QR code reader functionality to photograph the QR code. The Tracing App 20 will then extract the auth-code contained in the QR code.

[0055] Encounter Token upload.

[0056] The user 30 will enter the authentication code auth-code into its app 20 when uploading the Encounter Tokens (ET) to the Tracing Server 24. The Health Authority Server 34 will send the list of valid auth-codes issued to infected users to the Tracing Server 24.

[0057] In one embodiment of the invention, the Tracing App 20 sends the authentication code auth-code to the Tracing Server 24. The Tracing Server 24 will check whether the auth-code received from the Tracing App 20 is among the list of valid auth-codes received from the Health Authority Server 34 and respond with a nonce (random number, used once).

[0058] The Tracing App 20 will then derive an authenticator value auth-val and attach it to the message containing the Encounter Tokens it uploads to the Tracing Server 24. The auth-val is a cryptographic message authentication code (MAC) derived from the Encounter Tokens using the authentication code auth-code as the key to the authentication code: auth-val=MAC(auth-code|ET_1|ET_2| . . . |ET_k). In one embodiment of the invention, the nonce received from the Tracing Server 24 is used as the key to the MAC: auth-val=MAC(nonce, |ET_1|ET_2| . . . |ET_k).

[0059] In yet another embodiment of the invention, the auth-val also depends on metadata related to the Encounter Tokens: auth-val=MAC(auth-code, metadata, ET_1 ET_2 . . . ET_k), or, auth-val=MAC(nonce, metadata, |ET_1|ET_2| . . . |ET_k).

[0060] When the Tracing App 20 sends its Encounter Tokens to the Tracing Server 24, the Tracing Server will check the authenticator value auth-val by calculating if it is derived using a valid auth-code or nonce. If the authenticator value is valid, the submitted Encounter Tokens are accepted and stored locally by the Tracing Server 24. Otherwise they are rejected and discarded.

[0061] In another embodiment of the invention shown in FIG. 3, the Tracing App 20 sends an authentication code auth-code to the Tracing Server 24 and receives a list of nonces (n_1, n_2, . . . , n_k) from the Tracing Server 24. The Tracing App 20 then calculates an authentication value auth-val_i for each Encounter Token ET_i separately: auth-val_1=MAC(n_1|ET_1), auth-val_2=MAC(n_2|ET_2), . . . , auth-val_k=MAC(n_k|ET_k). The Tracing Server 24 will then check each Encounter Token ET_i separately by verifying that its authenticator value auth-val_i is derived using a valid nonce n_i.

[0062] In a preferred embodiment of this invention the Encounter Tokens (ET) are not transmitted to the Tracing Server 24 in plain text, but instead a cryptographic hash value h(ET) of the Encounter Token is transmitted instead of the Encounter Token.

[0063] In a preferred embodiment of the invention, the Tracing App 20 will upload only such Encounter Tokens that have a duration associated with them that exceeds a minimum duration threshold (e.g., 10 minutes). This is to avoid publishing unnecessary information that is not relevant for the transmission of the disease and thus protect the user's privacy.

[0064] FIG. 4 illustrates the Encounter Token download and contact verification. Each Tracing App 22 participating in the system may regularly download verified Encounter Tokens ET from the Tracing Server 24. In a preferred embodiment of this invention, the download will take place at least once a day. In another embodiment, the time of the download is determined based on a random time interval within maximum interval duration.

[0065] The Tracing App 22 will download a list (ET_1, ET_2, . . . , ET_k) of Encounter Tokens. It will then compare each of these Encounter Tokens to the list of Encounter Tokens stored locally on the mobile device. If a matching ET_i is found, the Tracing App 22 will notify the user 32 that an encounter with a person tested positive with the infectious disease. In another embodiment of the invention, also other suitable actions can be triggered by the Tracing App 22, including, e.g., establishing contact or communications with health authorities.

[0066] In another embodiment of the invention, upon a matching Encounter Token is found, additional metadata stored with the Encounter Token may be examined to determine an infection risk level.

[0067] In yet another embodiment, the notification of the contact with an infected person may be triggered by the Tracing App 22 only if the determined risk level surpasses a determined threshold value.

[0068] In yet another embodiment, the actions taken by the Tracing App 22 may be dependent on the determined risk level.

[0069] In a preferred embodiment of the invention the matching of Encounter Tokens is based on the cryptographic hash values h(ET) of the Encounter Tokens (ET).

[0070] In one embodiment of the invention, the Tracing App 22 can be used to share information about verified encounters with an external entity. An external entity could be, e.g., an epidemiological research institute 36 (FIG. 2). In this embodiment, the Tracing App 20 (FIG. 3) of the infected person 30 (FIG. 3) attaches to each Encounter Token ET_i an individual encrypted nonce value enc-n_i, using the encounter token ET_i as the encryption key: enc-n_i=encryption(ET n_i). In this embodiment, only cryptographic hash values of the Encounter Tokens are sent to the Tracing Server 24.

[0071] In this embodiment, other Tracing Apps will retrieve the verified cryptographic hash values h(ET_i) as well as the encrypted Encounter Token-specific nonce values enc-n_i from the Tracing Server 24. The Tracing Apps 22 compare the cryptographic hashes with the cryptographic hashes of their own Encounter Tokens and if a match is determined, they use the value of the matching Encounter Token ET_i to decrypt the nonce value n_i: n_i=decryption(ET_i, enc-n_i).

[0072] In one particular embodiment of this invention, the encryption algorithm AES is used for encryption and decryption.

[0073] In the preferred embodiment of this invention, the Tracing App 20 (FIG. 3) of the infected person 30 (FIG. 3) receives the Encounter Token-specific nonces n_i used from the Tracing Server 24. In another embodiment, the Tracing App 20 (FIG. 3) of the infected person 30 (FIG. 3) generates the Encounter Token-specific nonces itself and provides the list of nonces to the Tracing Server 24 when it uploads its Encounter Tokens to the Tracing Server.

[0074] For allowing an external entity 36 (FIG. 2) to verify contacts to infected persons, the Tracing Server 24 will share the list of Encounter Token-specific nonces with the external entity. When a Tracing App 22 determines that a contact with an infected person has taken place, it will use the matching Encounter Token as described above to decrypt the nonce associated with the matching Encounter Token and can send this nonce to the external entity 36 (FIG. 2). If the nonce is on the list of nonces provided to the external entity by the Tracing Server 24, the nonce is a valid proof of a contact with an infected person.

[0075] In one embodiment of the invention the external entity 36 (FIG. 2) will keep track of nonces provided to it as proof of contact and accept only one instance of each nonce in order to make it impossible for malicious Tracing Apps to duplicate proofs of contact by sending decrypted nonce.

[0076] In one embodiment of the invention, the proximity communication required for exchange of the cryptographic tokens is realized by an external wearable device 38. Wearable devices 38 can be wristbands, bracelets, necklaces, jewelry, etc. with built in processing capability, memory and proximity communication interfaces for communicating with other Tracing Apps or wearables. The main advantage of this embodiment is that the tracing functionality is not tied to the possession of a smart phone, but can also be used in usage contexts where using or carrying a smart phone is inconvenient or not possible. Examples of such usage contexts include sports activities, children at school or the playground and other comparable situations, in which one cannot assume users to constantly carry a smart phone with them. Carrying a wristband, on the other hand, is not intrusive and can be used in most situations, e.g., even under the shower, as wristbands usually are water-proof, contrary to many smart phone models.

[0077] In this embodiment, the wearable device 38 is paired with the user's tracing app 22 and communicates over the proximity communication protocol with the Tracing App. The Tracing App 22 generates cryptographic tokens used for Encounter Token establishment and uploads them over the proximity communication channel to the wearable 38. The wearable 38 will store the cryptographic tokens locally.

[0078] According to a fixed time schedule, the wearable device 38 will transmit the cryptographic tokens into its proximity over the proximity communication protocol. The wearable device 38 exchanges cryptographic tokens with other devices in proximity and stores cryptographic tokens of other devices it encounters locally. The wearable device 38 and the smart phone 28 frequently synchronize their data, so that the smart phone sends the cryptographic tokens that it generates to the wearable device and the wearable device sends the cryptographic tokens it has stored locally along with metadata associated with them to the smart phone. This synchronization function can be executed periodically or when the phone is charged or when the user interacts with the Tracing App 22, i.e., the app is running in the foreground.

[0079] The role of the wristband could be to exchange the cryptographic tokens required for establishing Encounter Tokens and transmit these to the Tracing App 22 with which it is paired. The derivation of Encounter Tokens, uploading Encounter Tokens to the Tracing Server 24, as well as downloading Encounter Tokens and contact verification all are performed by the Tracing App 22 independent of the wearable device 38. The tracing app 22 could be installed on a smart phone, a PC computer or any other suitable device to be connected to the wrist band and the tracing server 24.

[0080] The uploading and downloading of information can be in real time or subsequently, depending of the needs and the nature of the used device.

[0081] The number of expected encounter tokens is relevant for the size of the data storage to be provided by the mobile device 28. In average, a user has ca. 20 encounters (15 minutes or longer) with other users excluding known contacts e.g., household members or colleagues in the same office. Therefore, the expected number of Encounter Tokens per day is 20 Encounter tokens, preferably 30 Encounter tokens, more preferable 50 encounter tokens per day.

[0082] The app 20 (FIG. 3) of the infected user 30 (FIG. 3) uploads the hashes (128 bits) of Encounter Tokens (ETs) for 14 days. Hence, the total amount of data uploaded by the app 20 (FIG. 3) to the server 24 can be estimated to be, 14 days*20encounter tokens*128 bits=35,840 (bits) or 4.3 (kB). In case of higher numbers of encounter tokens this amount of data will increase respectively.

[0083] Under the assumption that there are 2000 new COVID-19 cases per day, the tracing app 22 according to an embodiment of the present invention will download from the tracing server 2000 cases*4.3 kB=8,600 (kB) or 8.6 MB per day. Also here, the amount of data will vary depending on the assumed numbers of cases and the amount of uploaded data.

[0084] Assuming that there are 2000 new COVID-19 cases per day, the tracing server 24 will receive 2000cases*4.3 kB=8,600 (kB) or 8.6 MB per day (the same to the data that an app downloaded).

[0085] Further assuming that there are 50 million app users, the tracing server 24 will send 50,000,000 users*8.6 MB=430,000,000 (MB) or 430 TB per day. If the number of users is higher, the numbers have to be adapted accordingly and the capacity of the tracing server will need to match these numbers.

[0086] In order to establish an Encounter Token (ET), the mobile device 28 needs to send and receive an advertising message (AM) and cryptographic token (CT) that are 192+520=712 (bits) or 712*2=1,424 (bits) for both sending and receiving. In the worst case, the BLE bandwidth is 125 (kbit/s) that means the tracing app 22 can establish 125,000/1,424=175 ETs per second. In the ideal case, the BLE bandwidth is 2 Mbit/s that means the tracing app 22 can establish 2,000,000/1,424=1,404 ETs per second. However, since the latency to establish a BLE connection is ca. 6 ms, the tracing app 22 may only establish 1000/6=160 ETs per second assuming that the data transmission time is much smaller than the connection time, it is fair to estimate that the tracing app 22 can establish 100 encounters per second, i.e. the maximum numbers of devices in a pre-defined proximity that the App 22 can establish the Encounter Tokens for is approximately 100/sec.

[0087] According to one embodiment of the present invention, the tracing app 22 constantly advertises and scans for advertising messages (AMs). The tracing app 22 periodically advertises AMs for every minute, in which devices run BLE advertising for 40 seconds and are in idle mode for 20 seconds. The tracing app 22 periodically scans AMs for every 50 seconds, in which devices run BLE scanning for 30 seconds and are in idle mode for 20 seconds. These advertising and scanning patterns are empirically selected to ensure that the tracing app 22 keeps track of other devices every 2 minutes.

[0088] According to one aspect of the invention no position data are provided in the metadata of the encounter token. This increases the privacy of the user and is not necessary for the evaluation of an infection risk. However, in other embodiments, the position data may be included in the metadata of the encounter token.

[0089] Those of skill in the art will appreciate that other embodiments of the invention may be practiced in an automated contact tracing system for anonymously identifying contacts between users. Embodiments may also be practiced in distributed computing environments where tasks are performed by local and remote processing devices that are linked (either by hardwired links, wireless links, or by a combination thereof) through a communications network. In a distributed computing environment, program modules may be located in both local and remote memory storage devices.

[0090] Communication at various stages of the described system can be performed through a variety of communication protocols. Although the underlying communication technology may change, the fundamental principles described herein are still applicable.

[0091] The various embodiments described above are provided by way of illustration only and should not be construed to limit the invention. For example, the principles herein may be applied to any mobile device or tag. Those skilled in the art will readily recognize various modifications and changes that may be made to the present invention, without following the example embodiments and applications illustrated and described herein, by combining only some technical features of different embodiments as far as technical possible, without departing from the scope of the present disclosure.