PaperlayerView exact revision on arXiv

Source-linked AI summary

Decentralized Privacy-Preserving Proximity Tracing

Carmela Troncoso, Mathias Payer, Jean-Pierre Hubaux, Marcel Salathé, James Larus, Edouard Bugnion, Wouter Lueks, Theresa Stadler, Apostolos Pyrgelis, Daniele Antonioli, Ludovic Barman, Sylvain Chatel, Kenneth Paterson, Srdjan Čapkun, David Basin, Jan Beutel, Dennis Jackson, Marc Roeschlin, Patrick Leu, Bart Preneel, Nigel Smart, Aysajan Abidin, Seda Gürses, Michael Veale, Cas Cremers, Michael Backes, Nils Ole Tippenhauer, Reuben Binns, Ciro Cattuto, Alain Barrat, Dario Fiore, Manuel Barbosa, Rui Oliveira, José Pereira

arXiv:2005.12273v1cs.CRcs.CY

TL;DR

DP3T addresses the challenge of containing SARS-CoV-2 while protecting privacy and accommodating technical constraints. It designs and analyzes three decentralized protocols that locally compute exposure risk, finding that they scale with minimal computation and centralization while limiting backend access to interaction graphs.

  • Problem

    The paper addresses the need for an implementable digital system to accelerate proximity tracing while containing SARS-CoV-2 and protecting privacy.

  • Method

    The paper designs and analyzes three decentralized proximity-tracing protocols with different trade-offs between privacy protection, bandwidth, and implementation cost.

  • Results

    The three alternatives scale to many users with minimal local computation and centralization, while protecting interaction graphs from the backend compared with centralized designs.

  • Takeaways & Limitations

    Exposure events remain on users’ phones, and the protocols limit private-data exposure while offering configurable privacy and bandwidth trade-offs.

  • Takeaways & Limitations

    A proactive tech-savvy adversary can identify people who reported a positive diagnosis and were in close proximity, regardless of the implementation or protocol.

Abstract

from arXiv · show

This document describes and analyzes a system for secure and privacy-preserving proximity tracing at large scale. This system, referred to as DP3T, provides a technological foundation to help slow the spread of SARS-CoV-2 by simplifying and accelerating the process of notifying people who might have been exposed to the virus so that they can take appropriate measures to break its transmission chain. The system aims to minimise privacy and security risks for individuals and communities and guarantee the highest level of data protection. The goal of our proximity tracing system is to determine who has been in close physical proximity to a COVID-19 positive person and thus exposed to the virus, without revealing the contact's identity or where the contact occurred. To achieve this goal, users run a smartphone app that continually broadcasts an ephemeral, pseudo-random ID representing the user's phone and also records the pseudo-random IDs observed from smartphones in close proximity. When a patient is diagnosed with COVID-19, she can upload pseudo-random IDs previously broadcast from her phone to a central server. Prior to the upload, all data remains exclusively on the user's phone. Other users' apps can use data from the server to locally estimate whether the device's owner was exposed to the virus through close-range physical proximity to a COVID-19 positive person who has uploaded their data. In case the app detects a high risk, it will inform the user.

Executive Summary

DP3T is a large-scale, secure and privacy-preserving proximity-tracing system that helps accelerate exposure notification while minimizing privacy and security risks. It keeps proximity data on users’ phones, enables local exposure-risk estimation, and provides protections against data abuse and user tracking.

  • System design: DP3T uses ephemeral pseudo-random IDs: phones broadcast their own IDs, record nearby IDs, and let diagnosed users upload previously broadcast IDs.Other apps download server data and locally estimate whether their owners were exposed through close-range proximity.
  • Privacy protections: The central server observes only anonymous identifiers from COVID-19-positive users, without proximity information, while health authorities learn only what notified users voluntarily provide.This implements data minimization by keeping other proximity data exclusively on users’ phones.
  • Privacy protections: Because the server receives only the minimum required information, it cannot misuse collected data for other purposes or be coerced or subpoenaed to disclose additional data.The protection follows from limiting what information the central server receives.
  • Privacy protections: No entity can track users who have not reported a positive diagnosis; implementations may expose positive users only within small regions covered by Bluetooth-beacon infrastructure.The scope of possible tracking depends on where infrastructure capable of receiving broadcast beacons is deployed.
  • System lifecycle: After the epidemic, positive users stop uploading data and people stop using the app, while server and app data are removed after 14 days.This provides a defined mechanism for dismantling the system once the epidemic ends.

1. Need, purpose and requirements

The section motivates digital proximity tracing as a scalable complement to manual contact tracing and defines requirements for effective exposure notification, privacy protection, and pandemic-scale deployment. DP3T deliberately excludes user tracking and epidemiological research uses that would increase privacy risks or exceed the system’s purpose.

  • Need and purpose: Manual contact tracing is time consuming, difficult to scale rapidly, and often misses unidentifiable close contacts such as nearby passengers on public transportation.These limitations motivate digital systems that can support human contact tracers and automatically alert otherwise unidentifiable contacts.
  • Need and purpose: Digital proximity tracing alerts users after prolonged close physical proximity to a confirmed positive case, triggering precautions such as testing or quarantine.Exposure indicates a need for precautionary intervention but does not imply that the person contracted COVID-19.
  • Need and purpose: Digital proximity tracing complements rather than replaces manual contact tracing by sending automatic alerts quickly and reaching contacts that patients cannot identify.The application records exposure events when phones meet predefined distance and duration thresholds.
  • Out of scope: The design does not track diagnosed users or support epidemiological research, because added data collection could compromise privacy and cannot establish causal transmission, fomite, or aerosol transmission.The system assumes users with positive test results act responsibly and does not attempt to detect post-diagnosis contacts or misbehavior.
  • Requirements: The system must enable proximity tracing, preserve individuals’ digital privacy rights, and meet the scalability requirements of a global pandemic.Its proximity-tracing properties include completeness, precision, authenticity, confidentiality, and notification.

2. Decentralized proximity tracing

DP3T proposes a decentralized proximity-tracing framework that minimizes information revealed to the backend by keeping exposure detection and tracing largely on smartphones. It offers three protocols sharing this framework, including a low-cost option with good privacy and small bandwidth requirements.

  • Common framework: Three protocols share a framework in which smartphones locally generate frequently changing ephemeral identifiers (EphIDs) and broadcast them.The protocols give developers a choice between privacy and computation cost.
  • Backend role: The backend serves as a communication platform that stores uploaded representations but performs no processing, so user privacy does not depend on its actions.The server is trusted for availability and for not adding or removing exposure events, but is untrusted to protect privacy.
  • Uploads: Authorized users can instruct their phones to upload EphID representations, while the upload-authorization mechanism is left abstract and self-reporting is discouraged.The paper advises implementing one of the proposed authorization mechanisms for stronger security guarantees.
  • Local exposure detection: Other smartphones periodically query the backend and locally reconstruct COVID-19-positive users’ EphIDs to detect matching recorded beacons and estimate possible exposure.A match between recorded beacons and reported EphIDs indicates that the smartphone’s user might have been exposed.
  • Low-cost protocol: The low-cost protocol is designed to provide good privacy properties and very small bandwidth requirements.It is presented as one of the protocols within the shared decentralized framework.
  • Initial seed generation: At the start of each UTC day t, smartphones generate a random initial daily seed SK_t for that day.The seed-generation procedure defines the current day as t.

Creating ephemeral IDs (EphIDs)

DP3T devices generate a daily batch of pseudorandom ephemeral identifiers from a rotating secret day seed. They broadcast these identifiers in random order, changing them every configurable epoch of L minutes to reduce location tracking.

  • Creating ephemeral IDs (EphIDs): To limit location tracking through broadcast identifiers, devices change EphIDs every configurable epoch of L minutes.An epoch is the duration for which a device broadcasts the same EphID.
  • Creating ephemeral IDs (EphIDs): Each day t, smartphones locally generate n = (24 * 60)/L new EphIDs from the day seed SKt.The day seed SKt is rotated daily, and the smartphone uses it to generate that day’s EphIDs.
  • Creating ephemeral IDs (EphIDs): The generation process uses a pseudo-random function and pseudorandom generator to produce n * 16 bytes, split into 16-byte EphIDs.Examples given are HMAC-SHA256 for PRF and AES in counter mode for PRG.
  • Creating ephemeral IDs (EphIDs): Smartphones randomly order the day’s EphIDs and broadcast each EphIDi for L minutes.The random broadcast order is selected locally for the day.

Local storage of observed EphIDs and seeds SKt

The low-cost design stores observed EphIDs with exposure measurements and receipt days, while diagnosed users upload a contagious-window seed and start day for local exposure matching. Privacy-oriented variants hash observed identifiers into Cuckoo filters or use time-window seeds, increasing storage or bandwidth costs.

  • Low-cost design: Phones store each received EphID, exposure measurement, and receipt day, grouping repeated observations by EphID for efficient storage.The proposed grouping requires 36 bytes per EphID.
  • Seed upload: After health-authority authorisation, a diagnosed user uploads seed SKt and day t marking the contagious window’s first day.The contagious window may begin 1 to 3 days before symptom onset.
  • Seed upload: After uploading SKt, the phone deletes it and generates a new random seed, preventing the user from becoming trackable after reporting.Other phones reconstruct the diagnosed user’s EphIDs from (SKt,t), then use recorded receive times and exposure measurements for risk computation.
  • Privacy-oriented variants: The unlinkable design stores H(EphID || i), exposure measurement, and receipt day, preventing EphID linkage while permitting redaction of sensitive identifiers.A grouped entry requires around 52 bytes, and epoch binding prevents replayed EphIDs from causing false at-risk events outside their original epoch.
  • Privacy-oriented variants: The hybrid design uses time-window seeds uploaded only when relevant to exposure estimation, requiring 480 to 960 bytes per user for 2- to 4-hour windows.The unlinkable design requires 2880 bytes per diagnosed patient, compared with 36 bytes for the low-cost design.

3. Interoperability in decentralised proximity tracing systems

DP3T supports cross-border interoperability among decentralized tracing designs, enabling visitors and residents to receive exposure notifications across regions. This requires applications to process multiple protocols and regional backends to exchange tracing data for up to 14 days after visits.

  • Effective proximity tracing must work across borders so visitors capture local beacons and residents are notified when diagnosed visitors upload their data.
  • All three proposed decentralized designs support interoperability across operators and regions, provided applications process every protocol required for interoperability.An application must run as many protocols as needed to interoperate with specific protocols.
  • Cross-border interoperability requires backend servers in different regions, such as countries or states, to exchange data.
  • Phones retrieve tracing data from visited regions for up to 14 days after visits, using entered or permanently stored region lists.The published data format differs by protocol; for the low-cost design, it is a list of (SKt,t) pairs.
  • Diagnosed users provide recently visited regions with uploaded seeds, enabling backends to redistribute tracing data so contacts can check observed EphIDs.The backend authenticates the upload before redistribution to all visited regions.

4. Exposure estimation

Exposure estimation approximates a smartphone owner’s past duration of exposure to COVID-19-positive users, with health authorities setting the notification threshold. When the score exceeds that threshold, the app notifies the user and provides precautionary guidance.

  • 4. Exposure estimation: Exposure estimation measures past exposure duration to COVID-19-positive users as a proxy for SARS-CoV-2 exposure level.A prolonged exposure does not imply that transmission occurred.
  • 4. Exposure estimation: Local health authorities determine the exposure threshold for notifying users.The threshold triggers notification decisions, while the notification supports precautionary interventions.
  • 4. Exposure estimation: When the exposure score exceeds the authority-defined threshold, the smartphone notifies users of prolonged physical proximity to COVID-19-positive individuals.The notification advises users what to do and where to find more information.

5. Security and privacy considerations · 5.1 Threat model

The paper evaluates the privacy and security of three decentralized proximity-tracing protocols against defined adversaries. The threat model spans ordinary users, technical attackers, infrastructure operators, health authorities, state actors, and unlimited-budget adversaries.

  • 5. Security and privacy considerations: The security analysis examines the privacy and security properties of the document’s three decentralized proximity-tracing protocols.The paper also references a separate, more extensive risk evaluation covering 14 classes of decentralized systems.
  • 5.1 Threat model: The threat model specifies adversary capabilities and risks, which the following section uses to analyze system security and privacy.The section explicitly frames the adversary descriptions as inputs to the subsequent analysis.
  • 5.1 Threat model: A regular user can install and use the app and infer private information about others only from information exposed through its user interface.This adversary is limited to the app’s UI rather than system-level access.
  • 5.1 Threat model: A tech-savvy user can access the app, deploy Bluetooth, WiFi, or mobile antennas, decompile or modify the app, and access backend source code.This category includes hackers, NGOs, and academic researchers, with both investigative and potentially malicious capabilities.
  • 5.1 Threat model: Network adversaries observe traffic to infer user states, while local Bluetooth sniffers observe broadcasts and attempt to trace people.The model identifies internet service providers, local system administrators, and Bluetooth sniffers as eavesdroppers.
  • 5.1 Threat model: Health authorities learn about COVID-19-positive users through diagnosis operations but learn at-risk users’ information only when those users contact them.Contact may follow an app notification.
  • 5.1 Threat model: Backend and app developers can access server data, alter backend software and downloaded smartphone data, and modify app code, although app modification is assumed detectable and therefore excluded.The backend can query mobile-app data as during normal operations, while the model assumes developers will not modify the mobile app.
  • 5.1 Threat model: State-level adversaries combine tech-savvy and eavesdropping capabilities with subpoena-based health-authority or backend access, while unlimited-budget adversaries scale these capabilities and may control infrastructure.Both adversary types may seek population or individual information; unlimited-budget adversaries may also disrupt proximity tracing.

5.2 Privacy

DP3T avoids revealing users’ social and interaction graphs, location traces, exposure status, positive status, and exposed locations to unnecessary parties. The unlinkable design improves privacy and permits redacting sensitive periods, while the low-cost design leaves identifiable risks for capable adversaries.

  • Privacy goals: The system does not need to reveal social or interaction graphs, location traces, COVID-19 positive status, at-risk status, or exposed locations.Only at-risk individuals need exposure information, while users and health authorities need positive-status information.
  • Privacy guarantees: The seeds uploaded by positive users are independent of their contacts, so they reveal no information about at-risk people beyond the individuals themselves.Any notified user necessarily learns that at least one person they interacted with tested positive.
  • Adversarial risks: A standard-interface user learns only that they were exposed, whereas proactive tech-savvy adversaries can identify positive contacts by correlating exposure notifications with detailed encounter logs.This attack follows from the exposure bit that proximity tracing must reveal and can apply regardless of implementation or protocol.
  • Design comparison: In the low-cost design, reported seeds can link a positive user’s EphIDs across the contagious period, enabling attackers to identify who reported a diagnosis.EphIDs are otherwise unlinkable outside the contagious window, but strategically placed Bluetooth receivers can track infected patients during the linkable past window.
  • Deployment implications: A small portion of the population avoiding participation because of these attacks would not greatly impair deployment effectiveness if a large fraction still runs the app.The system would continue producing enough at-risk identifications to significantly reduce transmission.
  • Design comparison: Both designs provide the same protection for social and interaction graphs, while the unlinkable design offers better overall privacy at increased bandwidth cost.The unlinkable design also lets positive users redact sensitive periods from disclosure.

5.3 Security

DP3T addresses fake exposure events, suppression of at-risk contacts, and prevented contact discovery across its designs. Relay attacks are constrained by time binding, while claiming another user’s EphID remains computationally infeasible; Bluetooth jamming remains inherent to BLE-based tracing.

  • Suppressing at-risk contacts and preventing contact discovery: Infected users or backend components can suppress at-risk contacts, while BLE jamming can stop EphID recording and prevent contact discovery.The low-cost, unlinkable, and hybrid designs share these suppression and contact-discovery security properties.
  • Fake exposure events: Powerful adversaries can trigger false exposure alerts by extending BLE range or relaying EphIDs beyond real-world proximity.The attack can involve broadcasting observed identifiers at another location or time, subject to design-specific timing constraints.
  • Low-cost design: The low-cost design permits same-day EphID relay attacks but prevents relays delayed more than 24 hours through day-bound positive-user seeds.It also requires uploading seeds SKt, making it computationally infeasible to derive another user’s seed from observed broadcasts.
  • Unlinkable design: The unlinkable design requires fake-exposure relays to occur within the same broadcast epoch, making such online attacks unavoidable for passive Bluetooth advertisements.Its EphID generation likewise prevents claiming another user’s EphID because inferring seedt from the broadcast identifier is computationally infeasible.
  • Hybrid design: The hybrid design requires adversaries to rebroadcast EphIDs within the seed’s valid time window, preventing relays delayed beyond that window.As in the low-cost design, inferring seedw from a broadcast identifier to claim another user’s EphID is computationally infeasible.

6. Protection from short-term and remote eavesdropping at the physical layer

The section proposes a physical-layer enhancement for decentralized proximity tracing to prevent short-duration or long-distance eavesdropping that produces imprecise exposure events. Efficient deployment likely requires low-level smartphone component changes and otherwise may significantly affect battery life.

  • Threat model: Modified apps or attacker-controlled software can record proximity events after brief contact or at long distance, violating precise exposure reporting.The underlying systems exchange Bluetooth advertisements between devices.
  • Threat model: Attackers can collect many EphIDs using specialist equipment in high-traffic locations or vehicles, with directional antennas extending range and selectivity.Recorded EphIDs can later be matched against positive diagnoses and combined with additional metadata.
  • Implementation limitations: Efficient enhancements likely require changes to low-level smartphone components such as Bluetooth chips; without them, battery-life impact may be non-negligible.The limitation concerns implementation efficiency and device energy consumption.

EphID spreading with secret sharing

EphID spreading with secret sharing encodes each ephemeral identifier into shares distributed across low-power beacons, requiring k of n shares for reconstruction. The enhancement aims to improve resistance to brief and distant eavesdropping without adding transmissions or receptions, while k and radio parameters must balance robustness against privacy.

  • Mechanism: Each EphID is encoded into n shares across low-power beacons, and receivers need at least k shares to reconstruct it.The design uses a k-out-of-n secret sharing scheme rather than transmitting the complete EphID from one beacon.
  • Mechanism: With spreading enabled, each broadcast contains EphID shares, while retransmission within an epoch generates new shares.In the simplest case, n can equal the number of broadcasts made during an epoch.
  • Overhead: The enhancement requires no additional transmission or reception over the basic designs and should not significantly affect battery life.This preserves the basic communication workload despite distributing EphIDs across broadcasts.
  • Privacy–robustness trade-off: Larger k forces an adversary to shadow a victim longer, whereas smaller k makes contact registration more robust when fewer beacons are received.The selected k must provide enough shares during the epidemiologically relevant contact interval while limiting adversarial collection.
  • Eavesdropping resistance: >99.9% probability of receiving an EphID within five minutes is achievable for a legitimate user within 5 meters under stated attacker and radio assumptions.The same parameter selection is intended to give an eavesdropper at 16 meters a small probability of success.
  • Integration: The scheme can complement RSSI-based or other ranging and may distribute shares across three BLE advertisement channels if chipsets support it.Further parameter choices depend on transmission power, frequency, required k, experiments, functional requirements, and risk assessment.

7. Comparison with centralized approaches

Centralized proximity-tracing systems shift identifier generation and/or exposure estimation to the backend, enabling notification or status queries but creating substantial privacy and security risks. Compared with decentralized designs, they can expose social and interaction graphs, enable location traceability and identify at-risk users, while DESIRE mitigates some risks at the cost of difficult deployment requirements.

  • Centralized processing: Centralized designs compute exposure on the backend, which either notifies at-risk users or answers smartphones’ exposure-status queries.PEPP-PT-NTK and OpenTrace notify users, whereas ROBERT users query the backend.
  • Privacy risks: When identifiers and exposure are centralized, the backend can reconstruct users’ social and timestamped interaction graphs from linked observations.The learned interaction-graph subset grows as confirmed users upload contact histories, and pseudonymous graph data is easy to reidentify.
  • Privacy risks: DESIRE prevents the backend from learning the interaction graph if its anonymous communication, upload mixing, and anonymous authentication mechanisms are deployed, but these mechanisms are difficult to realize in practice.The paper also states separately that analogous mechanisms are ineffective for ROBERT and still permit social-graph reconstruction.
  • Privacy risks: Server-generated keys enable linking observed EphIDs to permanent app identifiers, allowing retrospective location tracing; phone-generated keys provide location traceability equivalent to decentralized unlinkability.This comparison concerns access to server-side keys in centralized systems and DESIRE’s phone-generated-key design.
  • Privacy risks: In PEPP-PT-NTK and OpenTrace, backend-controlled notification requires recovering the identity of each at-risk individual.ROBERT instead returns whether a user’s exposure passed its threshold when the smartphone queries the backend.
  • Security risks: False exposure alerts are easy to trigger retroactively in centralized designs except DESIRE, which requires an active broadcast exchange between users.A tech-savvy diagnosed user can add a target’s EphIDs to uploaded observations without broadcasting in the other centralized designs.

8. Conclusion

The paper presents three privacy-preserving proximity-tracing protocols that keep exposure-event data on users’ phones while supporting local risk computation at scale. The alternatives differ in bandwidth, privacy properties, and resistance to attacks, motivating continued exploration of realistic trade-offs.

  • Conclusion: The three protocols minimize exposure of private data and thereby limit privacy-leakage risk.The paper analyzes all three protocols as privacy-preserving designs.
  • Conclusion: Smartphones locally compute users’ SARS-CoV-2 exposure risk, while specific interaction data remains on the user’s phone.The system evaluates exposure through prolonged proximity to COVID-19-positive people.
  • Conclusion: The implementations trade bandwidth against privacy protection while scaling to many users with minimal local computation and centralization.One design is extremely lightweight; the others add privacy properties with a small increase in download data size.
  • Conclusion: The design protects interaction graphs from the backend, unlike central designs that compute risks and inform users.The paper evaluates the protocols for performance, security, and privacy and states that only a determined, tech-savvy adversary can learn extra information beyond what the app reveals.
  • Conclusion: The implementations expose trade-offs among resistance to active and passive attacks, battery consumption, and bandwidth overhead.The authors encourage continued research into the best realistic operating point for proximity tracing.
Loading 2005.12273v1…