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:
- 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.
- 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.
- 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).
- The Sender compares this to their database of infected locations using permutations provided by the dealer.
- 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