A note on blind contact tracing at scale with applications to the COVID-19 pandemic

Jack K. Fitzsimons, Atul Mantri, Robert Pisarczyk, Tom Rainforth, Zhikuan Zhao

TL;DR

This paper proposes a privacy-first framework for COVID-19 contact tracing using Secure Two-Party Computation (2PC). By transforming geographic proximity into a "blind" equality testing problem, the authors demonstrate how governments and telecommunications providers can identify potential exposures without either party ever seeing the other's raw location data.

What Problem Does This Paper Address?

Traditional contact tracing during the COVID-19 pandemic faced a "privacy vs. utility" deadlock. Centralized databases of citizen movements are a surveillance nightmare, while decentralized Bluetooth-based apps often suffer from low adoption and technical inaccuracies.

The authors address the challenge of Private Proximity Testing: how can we determine if Person A was near Person B at Time T without Person A revealing their entire history to the government, and without the government revealing the exact movements of infected patients to Person A? Specifically, they aim for a solution that is "blind" (hiding the where and when) and "at scale" (capable of handling national populations using existing infrastructure like cellular tower data).

Methods

The authors utilize Secure Two-Party Computation (2PC), specifically a protocol adapted from Ishai et al. (2013). The process follows three main steps:

  1. Tessellation: To simplify the math, the surface of the Earth is divided into a discrete grid (tessellated). This turns the complex problem of "calculating distance" into a simpler "equality test"—if two people are in the same grid cell at the same time, they are in proximity. They use an FCC-recommended ellipsoid approximation of the Earth to ensure accuracy across different latitudes.
  2. The Trusted Dealer: The protocol assumes a "Trusted Dealer" who provides correlated randomness (keys) to both parties before the computation begins. This dealer never sees the actual location data.
  3. Blind Equality Testing:
    • The Receiver (e.g., an individual or telco) masks their location data with random strings and sends it to the Sender (e.g., the government).
  4. The Sender compares this to their database of infected locations using permutations provided by the dealer.
  5. The result returned to the Receiver is simply a count ($N$) of how many matches occurred over a period (e.g., two weeks). Crucially, the Receiver learns that they were exposed, but not where or exactly when, preventing them from triangulating the identity of the infected person.

Datasets

The paper does not use a specific training dataset, as it proposes a cryptographic framework rather than a machine learning model. However, to evaluate scalability, the authors used synthetic scenarios based on the populations and infection rates of three countries as of April 2020:

  • Ireland (Small nation: ~4.8M people)
  • Poland (Medium nation: ~38M people)
  • Japan (Large nation: ~126M people)
  • City-level abstractions (1M, 5M, and 20M populations)

Key Insights and Ideas

  • Proximity as Equality: The most elegant move is reducing "proximity" to "equality" via Earth tessellation. This allows the use of highly efficient cryptographic protocols that were originally designed just to check if two strings are identical.
  • Hiding the "When": By returning only the total number of matches ($N$) over a fixed window, the protocol prevents the receiver from knowing the exact timestamp of the encounter, which is a common metadata leak in other systems.
  • Information-Theoretic Security: Unlike many systems that rely on "computational security" (assuming an attacker doesn't have a supercomputer), this protocol offers information-theoretic security. This means that even with infinite computing power, a dishonest party cannot extract the other's private data from the messages exchanged.
  • Infrastructure Agnostic: The method works with GPS, GSM (cell tower) triangulation, or even Wi-Fi logs, meaning it doesn't require everyone to install a specific new smartphone app to be effective.

Key Results

The authors performed a resource intensiveness analysis to prove the system could run on modern cloud infrastructure (AWS/Oracle/Azure):

  • National Scalability: For a large nation like Japan, the protocol would require approximately 11,000 Terabytes (TB) of keys and 16,000 TB of communication overhead.
  • Feasibility: While these numbers seem massive, the authors note that modern data centers with 100Gb/s interfaces can handle this volume of data transfer.
  • City Scale: For a city of 1 million people, the requirements drop to a very manageable 2.35 TB of keys and 3.3 TB of communication.

Limitations and Future Work

  • The Trusted Dealer: The system relies on a dealer that doesn't collude with either party. If the dealer and the government conspired, privacy could be compromised. Finding ways to remove the dealer (using "dealerless" 2PC) is a noted area for improvement.
  • Edge Effects: If two people are 1 meter apart but on opposite sides of a grid line, the equality test fails. The authors suggest using overlapping grids (a $3 \times 3$ search) to fix this, but this triples the data requirements.
  • False Positives: The grid approach is a proxy for physical proximity. It cannot account for physical barriers (like a wall between two people in different apartments) that would prevent actual viral transmission.
  • Resource Heavy: The TB-scale data requirements for national deployment are technically feasible but represent a significant logistical and financial undertaking for any government.

Summary updated

Abstract

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.
BibTeX
@inproceedings{fitzsimons2020note,
  author = {Jack K. Fitzsimons and Atul Mantri and Robert Pisarczyk and Tom Rainforth and Zhikuan Zhao},
  title = {{A note on blind contact tracing at scale with applications to the COVID-19 pandemic}},
  booktitle = {ARES},
  year = {2020},
  url = {https://openreview.net/forum?id=krVpyqgn1Ue},
}

Loading related content...

Figure