Paper 2020/670

Inverse-Sybil Attacks in Automated Contact Tracing

Benedikt Auerbach, Suvradip Chakraborty, Karen Klein, Guillermo Pascual-Perez, Krzysztof Pietrzak, Michael Walter, and Michelle Yeo


Automated contract tracing aims at supporting manual contact tracing during pandemics by alerting users of encounters with infected people. There are currently many proposals for protocols (like the “decentralized” DP-3T and PACT or the “centralized” ROBERT and DESIRE) to be run on mobile phones, where the basic idea is to regularly broadcast (using low energy Bluetooth) some values, and at the same time store (a function of) incoming messages broadcasted by users in their proximity. In the existing proposals one can trigger false positives on a massive scale by an “inverse-Sybil” attack, where a large number of devices (malicious users or hacked phones) pretend to be the same user, such that later, just a single person needs to be diagnosed (and allowed to upload) to trigger an alert for all users who were in proximity to any of this large group of devices. We propose the first protocols that do not succumb to such attacks assuming the devices involved in the attack do not constantly communicate, which we observe is a necessary assumption. The high level idea of the protocols is to derive the values to be broadcasted by a hash chain, so that two (or more) devices who want to launch an inverse-Sybil attack will not be able to connect their respective chains and thus only one of them will be able to upload. Our protocols also achieve security against replay, belated replay, and one of them even against relay attacks.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. MINOR revision.CT-RSA 2021
Contact author(s)
krzpie @ gmail com
benedikt auerbach @ ist ac at
suvradip chakraborty @ ist ac at
karen klein @ ist ac at
guillermo pascualperez @ ist ac at
michael walter @ ist ac at
michelle yeo @ ist ac at
2021-03-12: revised
2020-06-05: received
See all versions
Short URL
Creative Commons Attribution


      author = {Benedikt Auerbach and Suvradip Chakraborty and Karen Klein and Guillermo Pascual-Perez and Krzysztof Pietrzak and Michael Walter and Michelle Yeo},
      title = {Inverse-Sybil Attacks in Automated Contact Tracing},
      howpublished = {Cryptology ePrint Archive, Paper 2020/670},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.