Source-linked AI summary
PACT: Privacy Sensitive Protocols and Mechanisms for Mobile Contact Tracing
Justin Chan, Dean Foster, Shyam Gollakota, Eric Horvitz, Joseph Jaeger, Sham Kakade, Tadayoshi Kohno, John Langford, Jonathan Larson, Puneet Sharma, Sudheesh Singanamalla, Jacob Sunshine, Stefano Tessaro
TL;DR
Mobile contact tracing can scale epidemic response but risks privacy and civil liberties. This work specifies third-party-free protocols and mechanisms, examines inferential risks, and identifies adoption-dependent value across its proposed functionalities.
Problem
Mobile contact tracing can scale epidemic response, but straightforward applications may invade privacy and enable government data collection and mass surveillance.
Method
The work specifies third-party-free protocols and mechanisms for three contact-tracing functionalities, allowing app designers to choose which functionalities to use.
Results
The proposed functionalities have different adoption-value curves: two are linear in average adoption, while privacy-sensitive mobile tracing is quadratic.
Takeaways & Limitations
The protocols avoid requiring a trusted third party while explicitly addressing inferential risks in which exposure alerts can reveal identifying information.
Takeaways & Limitations
The approach cannot prevent relay attacks without sufficiently accurate timing information and accepts that positive users’ IDs can be linked within the infection window.
Abstract
from arXiv · showhide
The global health threat from COVID-19 has been controlled in a number of instances by large-scale testing and contact tracing efforts. We created this document to suggest three functionalities on how we might best harness computing technologies to supporting the goals of public health organizations in minimizing morbidity and mortality associated with the spread of COVID-19, while protecting the civil liberties of individuals. In particular, this work advocates for a third-party free approach to assisted mobile contact tracing, because such an approach mitigates the security and privacy risks of requiring a trusted third party. We also explicitly consider the inferential risks involved in any contract tracing system, where any alert to a user could itself give rise to de-anonymizing information. More generally, we hope to participate in bringing together colleagues in industry, academia, and civil society to discuss and converge on ideas around a critical issue rising with attempts to mitigate the COVID-19 pandemic.
1 Introduction and Motivation
PACT proposes privacy-sensitive mobile contact-tracing protocols that use computing to augment public-health efforts while upholding civil liberties. Its third-party–free approach keeps data largely on users’ phones, but acknowledges inferential re-identification risks and the continued need for conventional tracing.
- Motivation: Mobile contact tracing can scale conventional epidemic response, but straightforward applications risk privacy invasion and mass surveillance.The paper argues that privacy and security advances are needed for effective and acceptable designs.
- PACT objectives: PACT names privacy-sensitive technologies, architectures, and protocols that use voluntary disclosure consistent with personal decision making, disclosure, and consent.The objective is to establish transparent privacy and anonymity standards while upholding civil liberties.
- PACT objectives: The work specifies third-party–free protocols to avoid the aggregation of information and power, potential central-authority misuse, and problematic precedent.This design choice addresses concerns about relying on trusted third parties.
- Functionalities: PACT covers mobile-assisted interviews, privacy-sensitive proximity tracing, and related functionalities that augment public-health services.Interview data remains on the user’s device unless voluntarily revealed, while proximity sensing avoids collecting or sharing absolute location information.
- Adoption: Privacy-sensitive mobile tracing has value quadratic in average adoption, whereas Narrowcast and mobile-assisted tracing have value linear in average adoption.The paper expects the linear-value approaches to provide initial value and privacy-sensitive tracing to add substantial value at higher adoption rates.
- Scope and risks: The protocols aim to empower public-health services while maintaining civil liberties, but alerts can themselves provide de-anonymizing information.The paper also notes that mobile solutions do not replace conventional tracing because not everyone has or uses a phone app.
2 FAQ: Privacy, Security, and Re-Identification
The protocol keeps personal data on users’ phones by default and shares information voluntarily, but positive disclosures can still create inferential and re-identification risks. Cryptographic protections prevent some attacks, while replay, location inference, implementation issues, and incomplete smartphone coverage remain practical boundaries.
- Privacy and disclosure: If a user does not report being positive, the protocol sends no personal information to remote servers beyond random pseudonymous broadcasts.These broadcasts support proximity-based tracing, while other data remains on the device unless voluntarily disclosed.
- Privacy and disclosure: A positive disclosure notifies at-risk application users and may share exposure times, but does not explicitly reveal the positive individual’s identity or other information.The basic system stores random broadcasts rather than identities.
- Re-identification and inference: Re-identification remains possible because exposure alerts can correlate with outside information, such as a user having been near only one person.The paper characterizes this as a risk that cannot be completely avoided, including in manual contact tracing.
- Re-identification and inference: The app can reduce average-user re-identification by reporting only risk status or a rough time of day, although sophisticated users may circumvent this mitigation.The underlying protocol may still allow an at-risk user to learn the exposure time.
- Security attacks: Keeping the initial seed private prevents an attacker from impersonating a negative user’s broadcasts, even if Bluetooth traffic is recorded.This protection depends on the attacker being unable to break the underlying cryptographic mechanism.
- Security attacks: A malicious party recording broadcasts at multiple locations may infer where and when a positive individual traveled, while Bluetooth signals may also correlate with other de-anonymizing signals.These are implementation and inferential risks rather than explicit identity broadcasts.
- Security attacks: False alerts can arise from unlikely replay attacks in which colluding individuals reuse one private seed, although the protocol includes measures intended to make such attacks difficult.Malicious parties may thereby alert people who were not near the reporting individual.
- Deployment boundaries: The protocol does not address users without mobile phones, and an unalerted app user must not assume they had no exposure because smartphone ownership and app adoption are incomplete.Users should continue following public health guidance despite receiving no notification.
3 Protocols
PACT specifies three mobile contact-tracing functionalities built around Bluetooth proximity signals, local data storage, voluntary reporting, and third-party–free protocols. The protocol provides pseudorandomness, one-wayness, privacy, and integrity guarantees while explicitly accepting or mitigating several inference and attack risks.
- Overview: PACT describes mobile tracing in which users exchange Bluetooth IDs, and positive users may upload de-identified information to warn contacts of potential exposure.The paper also presents interview assistance and tailored public-service announcements as additional functionalities.
- Privacy-sensitive mobile tracing: Users generate pseudorandom IDs from a seed, collect nearby ID-time pairs locally, report a seed and time interval after a positive test, and check downloaded reports for exposure.The infection window is typically two weeks, and exposure checking regenerates reported ID sequences for local comparison.
- Security properties: Proposition 1 states that all unreported IDs are pseudorandom, while Proposition 2 states that attackers cannot generate a seed producing an honest user’s unreported ID without breaking G.These properties underpin privacy for negative users and prevent attackers from misreporting another user’s broadcasts.
- Privacy trade-offs: Negative users’ IDs cannot be linked without internal state, but more frequent seed updates improve privacy at the cost of less efficient exposure checking.Positive users’ reported IDs can be linked within the infection window, while IDs outside that window retain the negative-user guarantee.
- Limitations and extensions: A relay attack can rebroadcast an honest user’s captured ID elsewhere, although sufficiently accurate timing can prevent the attack once delay is sufficient.The protocol also strengthens integrity against malicious seed reuse by binding signed verification keys into ID generation.
- Inference risks and other functionalities: The system acknowledges that positive users’ IDs can be linked during the infection window and that server-side buffering and shuffling may reduce leakage while increasing latency and harming public-health value.Mobile-assisted interviews extract consented information for health authorities, while public-server queries for area-time announcements reveal no information through the protocol itself.
4 Alternative Approaches
The paper compares PACT with dual and centralized trusted-third-party approaches, emphasizing differences in integrity, privacy, temporal ambiguity, and implementation requirements.
- Dual approach: An attacker must almost simultaneously rebroadcast the same identifier near every falsely alerted individual to replicate the dual approach’s effect against PACT.
- Dual approach: PACT prevents framing a negative user because positive reports include a seed known only to the reporter.The dual approach allows uploaded nearby identifiers to frame another user.
- Dual approach: Both PACT-like and dual designs leave timing and contextual information that can let an at-risk user de-anonymize a positive user.The dual approach uses re-randomization to mitigate this temporal ambiguity.
- Dual approach: Under the DDH assumption, PACT identifiers are pseudorandom, and re-randomization prevents a negative user from identifying which broadcast was reported.This privacy benefit requires the reporting user to re-randomize identifiers and reuse the same secret exponent.
- Centralized approaches: Centralized approaches let a trusted third party identify identifier owners, but require substantial trust because it can learn at-risk users’ identities and manipulate alerts.The TTP may generate or decrypt identifiers and can falsely target users or withhold alerts.
- Location-based approaches: Absolute-location approaches face lower localization accuracy than Bluetooth proximity detection and require stronger cryptographic protection for positive users’ traces.
5 Related Efforts
The paper situates PACT among contemporaneous privacy-sensitive and centralized contact-tracing efforts, comparing identifier generation, reporting, timing protection, and storage trade-offs.
- Privacy-sensitive efforts: CoEpi, CovidWatch, and DP3T use privacy-sensitive protocols with structures similar to PACT but differ in their technical details and implications.
- Privacy-sensitive efforts: CEN derives an initial seed from a signing key and incorporates iteration counts and a verification key into pseudorandom identifier generation.The verification-key binding is intended to provide strong integrity and support cryptographically bound report memos.
- Privacy-sensitive efforts: An earlier CEN version allowed attackers to create valid reports containing another user’s identifiers with attacker-chosen memos; a fix was later proposed.
- Privacy-sensitive efforts: DP3T randomizes daily identifier order to hinder casual timing inference, but cannot hide timing from attackers that record when identifiers are received.
- Storage trade-offs: Uploading individual identifiers increases bandwidth and storage, while bloom filters reduce storage at the cost of reliability.DP3T also added cuckoo filters as an alternative storage mechanism.
- Other efforts: TraceTogether uses BlueTrace, which is closely related to the paper’s encryption-based centralized technique.
6 Discussion and Further Considerations
The discussion addresses interoperability, ethics, accessibility, and the role of mobile tracing within testing, tracing, and timeout programs.
- Interoperability: Most protocols store a server-side seed that deterministically generates identifier sequences, although sequence formats and cryptographic algorithms differ.Apps may be modified to support multiple sequence formats, but different protocols may provide different protection levels.
- Interoperability: Supporting multiple tracing services requires an interoperable server-entry format and possibly a common API.
- Ethics and access: Ethical questions center on balancing public-health disclosures against individual freedoms, while recognizing that conventional tracing already affects privacy.
- Ethics and access: Contact-tracing quality depends partly on phone ownership and service installation, raising fairness concerns beyond technological design.
- Epidemic response: Mobile tracing scales the testing, tracing, and timeout strategy beyond reliance on human contact tracers.
- Epidemic response: The overall strategy requires widespread testing, broad adoption, and user action, and its effectiveness across subscription levels remains a subject for study.
A Issues around Practical Implementation
The paper identifies practical implementation issues involving anonymity, querying, bandwidth, multiple authorities, and the choice of server infrastructure.
- Anonymity: Internet-based queries can expose a requester’s approximate location through GeoIP lookups, although anonymization services may reduce this exposure.
- User interfaces: Map software could query the server and display narrowcast public-health messages to users.
- Querying: Querying the full database may exceed a phone’s bandwidth and compute capacity, motivating regional-query extensions.
- Disjoint authorities: Apps can connect to multiple servers to accommodate testing authorities that do not share common infrastructure.
- Authority visibility: Mobile proximity tracing does not directly identify contacts for public authorities, though the volume of posted messages provides some aggregate information.
- Server infrastructure: A public GitHub repository is a simple server implementation when message volume is limited.
A.1 Regional Query Support
The protocol supports regional and time-scoped messaging while keeping location and sensory-log matching on the phone. Its queries trade precision, downloaded data, and information revealed to the server.
- Definitions: Region combines latitude and longitude prefixes with separate precision levels, allowing locations such as New York to be coarsened.The example coarsens 40.71455 N, -74.00712 E to 40 N, -74 E with two digits of precision.
- Definitions: Time is represented as seconds since January 1, 1970, while Location stores full-precision latitude and longitude.
- Definitions: An Area combines a Location, Radius, beginning Time, and ending Time; a Bluetooth Message is matched locally against the sensory log to trigger an exposure warning.
- Definitions: Messages are cryptographically signed byte strings interpreted by the phone app as public-health or Bluetooth messages.
- Queries: GetMessages returns server-added Area–Message pairs after a timestamp, which the app intersects locally with recorded sensory-log locations before alerting the user.
- Queries: HowBig estimates download size so the app can refine region precision according to a bandwidth/privacy tradeoff, while Announce distributes signed messages checked against a server whitelist.
B Alternative Protocol
The alternative protocol prevents the server from generating a positive user’s broadcast IDs, instead storing verification keys, and changes exposure-checking costs. It provides privacy and integrity properties but introduces replay risks and deployment limitations.
- Design: The alternative protocol stores a short verification key rather than enabling the server to generate IDs broadcast by a positive user.It may still permit several inference scenarios, but offers a different exposure-checking cost for some deployments.
- Design: Each user generates pseudorandom daily IDs using signatures and hashes, broadcasts them with random strings and timestamps, and deletes the daily signing key afterward.
- Protocol: Collected broadcasts are locally validated for timestamp proximity and hash consistency before being stored; exposure checking verifies stored IDs against downloaded verification keys.
- Protocol: Positive reporting uploads recent verification keys to a public server list, after which the reporting user erases memory and restarts ID generation.
- Efficiency: Signature verification is generally slower than evaluating the prior generator, although Ed25519 supports fast batch verification.
- Efficiency: The scheme is especially suitable when a user collects few IDs, meaning S is small relative to ∆· log(S).
- Assumptions: The protocol assumes hash pseudorandomness and collision resistance, plus signature unforgeability, one-wayness, and pseudorandomness; Ed25519 is reported to satisfy these properties under reasonable assumptions.
- Privacy: Negative users’ broadcasts cannot be linked without internal state, while positive users’ IDs are linkable within a day but retain negative-user guarantees outside the reported infection window.