Introduction
The COVID-19 pandemic underscored a critical tension in public health: the necessity for rapid, automated contact tracing (ACT) versus the fundamental right to digital privacy. Existing ACT systems generally fall into two categories: centralized and decentralized. Centralized systems, where a server tracks all encounters, pose significant privacy risks. Decentralized systems, such as DP-3T, mitigate some risks but remain vulnerable to metadata leakage and "false alarm" attacks where malicious actors upload fake keys.
Ovid is a novel ACT system that addresses these gaps through a message-based architecture. By combining blind signatures for infection verification and anonymous postbox channels for message delivery, Ovid ensures that a Health Authority (HA) can verify a user's infection status without ever learning their social graph or encounter history.
System Architecture and Methods
Ovid moves away from the "global blackboard" approach common in decentralized systems, opting instead for a targeted message-based delivery mechanism.
Encounter Detection and Postboxes
Like most ACT applications, Ovid utilizes Bluetooth Low Energy (BLE) to exchange Ephemeral Pseudonyms (EPs)—temporary public keys—between devices in close proximity. When a user is diagnosed as infected, they do not publish their own keys. Instead, they send encrypted warning messages to the "postboxes" of the individuals they encountered.
These postboxes are hosted on a central server but are aggregated into Postbox Channels. By grouping EPs by a prefix, Ovid provides plausible deniability; users poll an entire channel rather than a specific postbox, preventing the server from identifying which specific EP a user is checking.
Cryptographic Protections
To prevent malicious users from flooding the system with fake warnings, Ovid employs several cryptographic layers:
- Blind Signatures: Every message must be signed by the HA. Blind signatures allow the HA to verify that a message originates from a legitimate patient without seeing the message content or the intended recipient.
- Permission Tokens: Patients receive tokens from healthcare providers after a positive test. These tokens are generated using ring signatures, hiding which specific doctor issued the token from the HA.
- Cover Traffic: To thwart eavesdroppers, infected users are provided with "dummy" tokens to send signed cover traffic (fake messages) to random postboxes, increasing the system's noise floor.
Evaluation and Results
The authors evaluated Ovid using a custom simulation environment with 3,000 clients and a Python-based REST backend. Each user was simulated to have an average of 100 encounters over a 14-day period.
Performance and Scalability
The evaluation demonstrated that Ovid is highly scalable. The HA server can issue approximately 4,651 blind signatures per second, sufficient for large metropolitan outbreaks. Database operations are also efficient, with the storage of 10,000 infection messages taking only 6.33 seconds. On the client side, retrieving and decrypting 14 days of messages takes approximately 80 seconds.
Privacy Analysis
A key metric for Ovid is its resilience against "curious stalker" attacks. The simulation results show that privacy improves significantly with the introduction of cover traffic and user aggregation within channels.
As shown in the figure above, even a modest cover traffic rate (e.g., $P_{ct} = 0.1$) combined with at least two users per channel makes deanonymization statistically inefficient for an attacker.
Discussion and Limitations
Ovid's primary innovation is "Verification Without Identification." The use of blind signatures solves the authentication problem without compromising user contact lists. Furthermore, by incentivizing noise through infected users, Ovid provides robust privacy at a negligible overhead for those already uploading real messages.
However, the system faces challenges:
- Computational Cost: Asymmetric decryption on smartphones is CPU-intensive and can impact battery life, especially in high-density channels.
- Network Overhead: Downloading entire channels requires more data than downloading compact keys in decentralized systems.
Future work may involve "outsourcing" heavy decryption tasks to user-controlled devices like home servers, maintaining privacy while alleviating the burden on mobile hardware.
Summary updated