Cryptology ePrint Archive: Report 2020/1309

Provable Security Analysis of Decentralized Cryptographic Contact Tracing

Noel Danz and Oliver Derwisch and Anja Lehmann and Wenzel Puenter and Marvin Stolle and Joshua Ziemann

Abstract: Automated contact tracing leverages the ubiquity of smartphones to warn users about an increased exposure risk to COVID-19. In the course of only a few weeks, several cryptographic protocols have been proposed that aim to achieve such contract tracing in a decentralized and privacy-preserving way. Roughly, they let users' phones exchange random looking pseudonyms that are derived from locally stored keys. If a user is diagnosed, her phone uploads the keys which allows other users to check for any contact matches. Ultimately this line of work led to Google and Apple including a variant of these protocols into their phones which is currently used by millions of users. Due to the obvious urgency, these schemes were pushed to deployment without a formal analysis of the achieved security and privacy features. In this work we address this gap and provide the first formal treatment of such decentralized cryptographic contact tracing. We formally define three main properties in a game-based manner: pseudonym and trace unlinkability to guarantee the privacy of users during healthy and infectious periods, and integrity ensuring that triggering false positive alarms is infeasible. A particular focus of our work is on the timed aspects of these schemes, as both keys and pseudonyms are rotated regularly, and we specify different variants of the aforementioned properties depending on the time granularity for which they hold. We analyze a selection of practical protocols (DP-3T, TCN, GAEN) and prove their security under well-defined assumptions.

Category / Keywords:

Date: received 20 Oct 2020, last revised 30 Mar 2021

Contact author: anja lehmann at hpi de

Available format(s): PDF | BibTeX Citation

Version: 20210330:112054 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]