  The pandemic in 2020 and 2021 had enormous economic and societal
consequences, and studies show that contact tracing algorithms can be key in
the early containment of the virus. While large strides have been made towards
more effective contact tracing algorithms, we argue that privacy concerns
currently hold deployment back. The essence of a contact tracing algorithm
constitutes the communication of a risk score. Yet, it is precisely the
communication and release of this score to a user that an adversary can
leverage to gauge the private health status of an individual. We pinpoint a
realistic attack scenario and propose a contact tracing algorithm with
differential privacy guarantees against this attack. The algorithm is tested on
the two most widely used agent-based COVID19 simulators and demonstrates
superior performance in a wide range of settings. Especially for realistic test
scenarios and while releasing each risk score with epsilon=1 differential
privacy, we achieve a two to ten-fold reduction in the infection rate of the
virus. To the best of our knowledge, this presents the first contact tracing
algorithm with differential privacy guarantees when revealing risk scores for
COVID19.
