  The current COVID-19 pandemic highlights the utility of contact tracing, when
combined with case isolation and social distancing, as an important tool for
mitigating the spread of a disease [1]. Contact tracing provides a mechanism of
identifying individuals with a high likelihood of previous exposure to a
contagious disease, allowing additional precautions to be put in place to
prevent continued transmission. Here we consider a cryptographic approach to
contact tracing based on secure two-party computation (2PC). We begin by
considering the problem of comparing a set of location histories held by two
parties to determine whether they have come within some threshold distance
while at the same time maintaining the privacy of the location histories. We
propose a solution to this problem using pre-shared keys, adapted from an
equality testing protocol due to Ishai et al [2]. We discuss how this protocol
can be used to maintain privacy within practical contact tracing scenarios,
including both app-based approaches and approaches which leverage location
history held by telecoms and internet service providers. We examine the
efficiency of this approach and show that existing infrastructure is sufficient
to support anonymised contact tracing at a national level.
