A privacy-preserving tests optimization algorithm for epidemics containment

Alessandro Nuara, Francesco Trovò, Nicola GattiarXiv 2020 · arXiv

Introduction

During an epidemic such as SARS-CoV-2, health authorities face a dual challenge: the "swab bottleneck" and the "privacy paradox." Testing resources are often limited, and focusing solely on symptomatic individuals is insufficient because asymptomatic and presymptomatic carriers significantly drive transmission. Simultaneously, while effective contact tracing is vital, privacy regulations like GDPR necessitate that contact data remain decentralized and anonymized on individual devices.

This paper proposes PPTO (Privacy-Preserving Test Optimization), a decentralized algorithm designed to identify high-risk individuals for testing without compromising personal privacy.

The SAPSR Model

To accurately model the spread, the researchers developed the SAPSR model, an extension of the classic SIR framework. It partitions the population into five distinct states: Susceptible ($S$), Asymptomatic ($A$), Presymptomatic ($P$), Symptomatic ($Y$), and Recovered ($R$).

The SAPSR model transitions, illustrating the pathways from susceptibility to recovery through various infection states.

This model explicitly accounts for "hidden" spreaders—asymptomatic individuals who are difficult to detect but critical to the epidemic's trajectory.

The PPTO Algorithm

The core of the solution is the PPTO algorithm, which utilizes decentralized Monte Carlo simulations to reconstruct potential infection chains.

  • Decentralized Simulation: Instead of a central server knowing the contact graph, the simulation is distributed. When an individual tests positive ($Y$), their device initiates a request.
  • Probabilistic Tracing: The algorithm performs both backward tracing (identifying potential sources of infection) and forward tracing (identifying potential secondary infections) using probabilistic logic.
  • Risk Scoring: Infection paths are simulated locally on devices using anonymous tokens. Each device maintains a local "risk score" based on how many simulated paths intersect with its contact history.
  • Privacy-Preserving Selection: Only the final risk scores are shared with a central authority, which then selects the $K$ individuals with the highest scores for testing. The central server never accesses raw contact data.

Experimental Results

The algorithm was evaluated using synthetic datasets of 10,000 individuals, with parameters modeled on real-world SARS-CoV-2 data. PPTO was compared against two baselines: Testing Symptomatics (TS) and Testing Symptomatics and Direct Contacts (TSDC).

Simulation results: (a) Evolution of population states over time; (b) Comparison of total infections across different testing strategies; (c) Impact of varying app adoption rates on infection totals.

Key Findings

  • Superior Containment: In a 30-day simulation with 100 daily tests, PPTO reduced total infections by 50% compared to the TS strategy and by 20% compared to TSDC.
  • Adoption Sensitivity: The effectiveness of the system depends heavily on public participation. If adoption drops to 50% ($\rho = 0.5$), the final number of infections increases by approximately 35% compared to full adoption.
  • Efficiency: The decentralized nature of the computation ensures that the algorithm is lightweight enough for standard smartphones, avoiding significant battery drain.

Discussion and Future Work

While PPTO shows significant promise, its current evaluation relies on synthetic data. Real-world challenges such as Bluetooth signal noise and the assumption of honest reporting by users remain to be addressed. Future research could focus on "online" parameter estimation to adapt to evolving epidemic characteristics and incorporating environmental transmission factors.

By moving computation to the edge, PPTO offers a legally and ethically viable path toward effective epidemic management in a privacy-conscious world.

Summary updated

Abstract

The SARS-CoV-2 outbreak changed the everyday life of almost all the people over the world.Currently, we are facing with the problem of containing the spread of the virus both using the more effective forced lockdown, which has the drawback of slowing down the economy of the involved countries, and by identifying and isolating the positive individuals, which, instead, is an hard task in general due to the lack of information. For this specific disease, the identificato of the infected is particularly challenging since there exists cathegories, namely the asymptomatics, who are positive and potentially contagious, but do not show any of the symptoms of SARS-CoV-2. Until the developement and distribution of a vaccine is not yet ready, we need to design ways of selecting those individuals which are most likely infected, given the limited amount of tests which are available each day. In this paper, we make use of available data collected by the so called contact tracing apps to develop an algorithm, namely PPTO, that identifies those individuals that are most likely positive and, therefore, should be tested. While in the past these analysis have been conducted by centralized algorithms, requiring that all the app users data are gathered in a single database, our protocol is able to work on a device level, by exploiting the communication of anonymized information to other devices.
BibTeX
@misc{nuara2020privacy,
  author = {Alessandro Nuara and Francesco Trovò and Nicola Gatti},
  title = {{A privacy-preserving tests optimization algorithm for epidemics containment}},
  year = {2020},
  eprint = {2006.15977},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2006.15977},
}
Figure