Paper 2020/418

Delayed Authentication: Preventing Replay and Relay Attacks in Private Contact Tracing

Krzysztof Pietrzak


Currently several projects (including DP-3T, east and west coast PACT, Covid watch) aim at designing and implementing protocols for privacy preserving automated contact tracing to help fight the current pandemic. Those proposal are very similar, and in their most basic from basically propose an app for mobile phones which broadcasts frequently changing pseudorandom identifiers via (low energy) Bluetooth, and at the same time, the app stores IDs broadcast by phones in its proximity. Only if a user is tested positive, their IDs of the last 14 days are published so other users can check if they have stored them locally and thus were close to an infected person. Vaudenay [eprint 2020/399] observes that this basic scheme (he considers the DP-3T proposal) succumbs to relay and even replay attacks, and proposes more complex \emph{interactive} schemes which prevent those attacks without giving up too many privacy aspects. Unfortunately interaction is problematic for this application for efficiency and security reasons. In this note propose a simple \emph{non-interactive} variant of the basic protocol that \begin{itemize} \item (security) Provably prevents replay and relay attacks. \item (privacy) The data of all parties (even jointly) reveals no information on the location or time where encounters happened. \item (efficiency) The broadcasted message can fit into 128 bits and uses simple crypto (commitments and secret key authentication). \end{itemize} Towards this end we introduce the concept of ``delayed authentication", which basically is a message authentication code where verification can be done in two steps, where the first doesn't require the key, and the second doesn't require the message.

Available format(s)
Publication info
Preprint. MINOR revision.
Contact author(s)
pietrzak @ ist ac at
2020-04-20: revised
2020-04-13: received
See all versions
Short URL
Creative Commons Attribution


      author = {Krzysztof Pietrzak},
      title = {Delayed Authentication: Preventing Replay and Relay Attacks in Private Contact Tracing},
      howpublished = {Cryptology ePrint Archive, Paper 2020/418},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.