Ovid: Message-based Automatic Contact Tracing

Leonie Reichert, Samuel Brack, Björn Scheuermann

Abstract

The COVID-19 pandemic created various new challenges for our societies. Quickly discovering new infections using automated contact tracing without endangering privacy of the general public is one of these. Most discussions concerning architectures for contact tracing applications revolved around centralized against decentralized approaches. In contrast, the system proposed in this work builds on the idea of message-based contact tracing to inform users about their risk. Our main contribution is the combination of a blind-signature approach to verify infections with an anonymous postbox service. In our evaluation, we analyze all components in our system for performance and privacy, as well as security. We also derive parameters for operating our system in a pandemic scenario.

Introduction

The global response to the COVID-19 pandemic highlighted a critical tension in automated contact tracing (ACT): the need for rapid infection discovery versus the protection of individual privacy. Existing solutions generally fall into two categories. Centralized systems provide health authorities with a comprehensive social graph, raising significant surveillance concerns. Conversely, decentralized systems like DP-3T offer better privacy but often suffer from efficiency issues, requiring all users to download massive global lists of infected keys.

Ovid introduces a third way: a message-based architecture that leverages blind signatures and anonymous postbox channels. This approach ensures that while infection alerts are authenticated, the Health Authority (HA) remains blind to the identities of both the sender and the recipient.

System Architecture and Methods

Ovid's core mechanism involves users exchanging Ephemeral Pseudonyms (EPs)—temporary public keys—via Bluetooth Low Energy (BLE) during encounters. When a user tests positive, they obtain a "permission token" from a medical facility. This token allows them to request a blind signature from the HA for their infection messages.

The Ovid Postbox System architecture

As shown in the figure above, the system operates as an anonymous postbox. Instead of broadcasting alerts to everyone, an infected user (Alice) writes an encrypted message to specific "channels" associated with the EPs of people she encountered (e.g., Bob). These channels are defined by prefixes of the EPs, allowing multiple users to poll the same channel. This "mailbox" model significantly reduces data traffic compared to global broadcast models while maintaining an anonymity set.

To further protect privacy:

  • Blind Signatures prevent the HA from seeing the content of infection messages it signs.
  • Ring Signatures ensure that the HA cannot trace a permission token back to a specific clinic.
  • Cover Traffic is injected to provide plausible deniability, ensuring that an observer cannot distinguish between a user receiving a real alert and a dummy message.

Evaluation and Key Results

The authors evaluated Ovid using a custom simulation environment with 3,000 virtual clients. The results demonstrate that the system is highly scalable and provides robust privacy guarantees. The HA server proved capable of processing 4,651 blind signatures per second, more than sufficient for large-scale deployment. On the client side, checking 14 days of history takes approximately 80 seconds.

Anonymity probability vs. users per channel

A critical aspect of Ovid is the balance between privacy and efficiency. The figure above illustrates the probability of identifying a specific user ($P_{Bob}$) relative to the number of users per channel. By adjusting the channel prefix length, the system can achieve a density (e.g., 5 users per channel) that, combined with cover traffic ($P_{ct}$), significantly lowers the probability of successful de-anonymization.

Conclusion and Future Work

Ovid presents a viable middle ground for ACT, offering the authenticity of centralized systems with the privacy of decentralized ones. By moving to a message-based "postbox" model, it optimizes network load and enhances user anonymity. Future work may focus on reducing the computational burden on mobile devices by offloading decryption to trusted local hardware and further hardening the system against sophisticated timing attacks through the use of mix-nets.

Summary updated

Abstract

The COVID-19 pandemic created various new challenges for our societies. Quickly discovering new infections using automated contact tracing without endangering privacy of the general public is one of these. Most discussions concerning architectures for contact tracing applications revolved around centralized against decentralized approaches. In contrast, the system proposed in this work builds on the idea of messagebased contact tracing to inform users about their risk. Our main contribution is the combination of a blind-signature approach to verify infections with an anonymous postbox service. In our evaluation, we analyze all components in our system for performance and privacy, as well as security. We also derive parameters for operating our system in a pandemic scenario.
BibTeX
@article{reichert2020ovid,
  author = {Leonie Reichert and Samuel Brack and Björn Scheuermann},
  title = {{Ovid: Message-based Automatic Contact Tracing}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2020},
}
Figure