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. 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. 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.
The Privacy-Utility Deadlock
Traditional contact tracing during the COVID-19 pandemic faced a significant "privacy vs. utility" deadlock. Centralized databases of citizen movements present severe surveillance risks, while decentralized Bluetooth-based applications often suffer from low adoption rates and technical inaccuracies.
This research addresses the challenge of Private Proximity Testing: determining if an individual was near an infected person at a specific time without either party revealing their full location history to the other or to the government. The goal is a solution that is "blind" (hiding the where and when) and capable of operating at a national scale using existing infrastructure, such as cellular tower data.
A Cryptographic Framework for Contact Tracing
The proposed framework utilizes Secure Two-Party Computation (2PC), specifically a protocol adapted from Ishai et al. (2013), to transform geographic proximity into a "blind" equality testing problem.
The process follows three primary stages:
- Tessellation: The Earth's surface is divided into a discrete grid. This converts the complex geometric problem of calculating distance into a simpler equality test: if two individuals occupy the same grid cell at the same time, they are in proximity.
- The Trusted Dealer: A "Key Generator" provides correlated randomness (keys) to both the government and the data provider (e.g., a Telecom) before computation begins. Crucially, this dealer never sees the actual location data.
- Blind Equality Testing: The individual or telecom masks their location data with random strings and sends it to the government. The government compares this against its database of infected locations. The individual receives only a count ($N$) of matches over a period (e.g., two weeks), preventing them from triangulating the exact identity or location of the infected person.
Key Insights
- Proximity as Equality: Reducing proximity to a grid-based equality test allows the use of highly efficient cryptographic protocols originally designed for string matching.
- Information-Theoretic Security: Unlike systems relying on computational hardness, this protocol offers information-theoretic security, meaning even an adversary with infinite computing power cannot extract private data from the exchanged messages.
- Infrastructure Agnostic: The method is compatible with GPS, GSM (cell tower) triangulation, or Wi-Fi logs, removing the requirement for citizens to install a specific smartphone application.
Scalability and Resource Analysis
To evaluate the feasibility of this approach, the authors modeled resource requirements across various population scales, ranging from small cities to large nations.
The analysis demonstrates that while the data requirements are significant, they are within the capabilities of modern cloud infrastructure. For a large nation (modeled at ~1.3B population), the protocol requires approximately 11,000 TB of keys and 16,000 TB of communication overhead. At a city scale (1 million people), these requirements drop to a manageable 2.35 TB of keys and 3.3 TB of communication. Modern data centers with 100Gb/s interfaces are equipped to handle these volumes.
Limitations and Future Outlook
Despite its privacy advantages, the system has several limitations:
- The Trusted Dealer: The framework assumes the key generator does not collude with the government. Future work may explore "dealerless" 2PC to remove this single point of failure.
- Edge Effects: Grid-based testing can fail if two people are close but on opposite sides of a grid line. While overlapping grids can solve this, it triples the data requirements.
- False Positives: The system cannot account for physical barriers (e.g., walls) that prevent viral transmission despite geographic proximity.
- Resource Intensity: While technically feasible, the Terabyte-scale requirements represent a significant logistical and financial undertaking for national deployment.
Summary updated