PaperlayerView exact revision on arXiv

Source-linked AI summary

Epione: Lightweight Contact Tracing with Strong Privacy

Ni Trieu, Kareem Shehata, Prateek Saxena, Reza Shokri, Dawn Song

arXiv:2004.13293v3cs.CR

TL;DR

Mobile contact tracing collects proximity information, but prior approaches leave privacy gaps in token collection and querying. Epione uses private set intersection cardinality to support exposure checks through an untrusted server. Its construction securely implements the specified contact-tracing functionality in the semi-honest setting.

  • Problem

    Prior private-set-intersection work often assumes similarly sized sets, while contact tracing compares a small client set with a much larger server set.

    Source: §2.2 · p. 8, §6.1.1 · p. 19

  • Method

    Epione uses PSI-CA to let a client privately check the size of the intersection between its tokens and a server’s token set.

    Source: §1.1 · p. 3, §1.2 · p. 4

  • Results

    The Epione construction securely implements the specified contact-tracing functionality in the semi-honest setting, given the stated PSI-CA primitive and a secure PRG.

    Source: §5.2.1 · p. 16

  • Takeaways & Limitations

    The PSI-CA construction and system optimizations are presented as making privacy-preserving contact tracing practical.

    Source: §1.1 · p. 3

    A user whose full token set matches only one other user can infer that person’s infection status, as this follows from the application’s intended functionality.

    Source: §5.2.3 · p. 18

Abstract

from arXiv · show

Contact tracing is an essential tool in containing infectious diseases such as COVID-19. Many countries and research groups have launched or announced mobile apps to facilitate contact tracing by recording contacts between users with some privacy considerations. Most of the focus has been on using random tokens, which are exchanged during encounters and stored locally on users' phones. Prior systems allow users to search over released tokens in order to learn if they have recently been in the proximity of a user that has since been diagnosed with the disease. However, prior approaches do not provide end-to-end privacy in the collection and querying of tokens. In particular, these approaches are vulnerable to either linkage attacks by users using token metadata, linkage attacks by the server, or false reporting by users. In this work, we introduce Epione, a lightweight system for contact tracing with strong privacy protections. Epione alerts users directly if any of their contacts have been diagnosed with the disease, while protecting the privacy of users' contacts from both central services and other users, and provides protection against false reporting. As a key building block, we present a new cryptographic tool for secure two-party private set intersection cardinality (PSI-CA), which allows two parties, each holding a set of items, to learn the intersection size of two private sets without revealing intersection items. We specifically tailor it to the case of large-scale contact tracing where clients have small input sets and the server's database of tokens is much larger.

1 Introduction

Mobile contact tracing must collect proximity information while protecting users’ privacy. Epione combines private set intersection cardinality with an untrusted-server workflow for exposure checks.

1 Introduction

  • Mobile contact tracing raises privacy concerns because it collects personal proximity information while serving a function that requires recording contacts.The paper frames this as a tension between contact tracing’s purpose and users’ privacy.Source: §1 · p. 1
  • Prior designs can expose diagnosed users’ social connections to servers, let users infer an exposure source, and allow false claims through modified app logs.The described risks include revealing when and for how long contacts occurred, identifying a suspected exposure source, and altering logs to claim diagnosis or contact.Source: §1 · pp. 2–3

1.1 Our Contribution

  • Epione aims to protect contact information from disclosure beyond intended functionality, limit diagnosis-status disclosure to health authorities, and prevent linkage attacks and false-positive claims.The system is designed to provide stronger privacy protections than the models discussed in related work.Source: §1.1 · p. 3
  • For asymmetric sets of sizes n << N, Epione’s PSI-CA protocol has communication overhead O(n log N).The protocol is designed for a small client set and a much larger server set.Source: §1.1 · pp. 3–4

1.2 System Overview

  • An untrusted Epione server supports private matching so users can learn the count of matching contact tokens without revealing their tokens to the server.The system uses secure computation, particularly PSI-CA, to prevent the server from inferring user linkages.Source: §1.2 · p. 4

2 Related Work

The related work compares trusted and untrusted contact-tracing designs, then surveys privacy improvements and secure set-intersection tools. It highlights the trade-offs between who learns contact information, linkage risks, and the cost of private queries.

2.1 Contact Tracing Approaches

  • Existing contact-tracing systems either expose data to a trusted third party or use decentralized/public lists that can reveal linkages; clients may also face substantial download and bandwidth burdens.The surveyed designs include variants of Covid-watch, Private Kit, PACT, and Google/Apple.Source: §2.1 · p. 5, §2.1.2 · p. 7

2.1.1 Trusted Third-Party (Centralized) Approaches

  • In TraceTogether’s centralized model, Grace registers users and issues tokens, then decrypts a diagnosed user’s submitted tokens to learn contacts and contact durations.The approach places trust in the government authority; a compromised key could support tracking users via Bluetooth.Source: §2.1.1 · pp. 5–6

2.1.2 Untrusted Third-Party or Decentralized Approaches

  • Untrusted or decentralized designs have diagnosed users submit tokens or token-generation secrets, after which users compare their histories with a private database or public token list.These designs remain susceptible to linkage attacks by users, the server, or both.Source: §2.1.2 · pp. 6–7

2.1.3 Privacy Improvements

  • Private messaging routes encrypted messages through non-colluding servers but leaves recipients able to infer exposure sources and requires substantial storage; PACT re-randomization depends on users reusing a secret key.A malicious user can choose different keys across encounters to determine which encounter caused exposure.Source: §2.1.3 · p. 7

2.2 Secure Computation and Private Set Intersection

  • Prior PSI reveals intersection items, while f-PSI and PSI-CA target functions such as threshold checks; existing approaches assume comparable sets or incur communication costs.Circuit-based methods spend communication on string comparisons and counting, while a homomorphic-encryption approach can still be communication-expensive for client-server settings.Source: §2.2 · p. 8

3 Problem Statement and Security Goal

The section defines token-based contact tracing and a security goal in which users learn whether received tokens match diagnosed users without exposing information beyond the intended functionality. It identifies linkage and false-positive attacks, and states that Epione provably provides contact-tracing functions while protecting against these attacks.

3.1 Problem Definition

  • The token-based workflow has clients generate and exchange contact tokens, then query a server with received tokens to learn how many came from diagnosed users.Source: §3.1 · p. 8

3.2 Security Definition and Goal

  • Security is framed by comparing real execution with an ideal trusted-party execution that reveals only the function’s final output.Source: §3.2 · pp. 9–10
  • The model assumes authenticated secure channels and non-colluding servers, and considers both semi-honest and malicious adversaries.Source: §3.2 · p. 9
  • Linkage attacks include servers re-identifying contact histories or tracking users over time, and users learning others’ contacts, infection status, or exposure source.Source: §3.2 · p. 10
  • A malicious user may falsely claim diagnosis, spreading false information and panic and reducing trust in the system.Source: §3.2 · p. 10
  • Epione is claimed to provably provide contact-tracing functions while protecting against the attacks identified in the security goals.Source: §3.2 · p. 10

4 Preliminaries

The preliminaries establish notation and introduce the cryptographic assumptions and tools used later. They define the DDH assumption and pseudorandom number generators, alongside shared notation for parameters, sets, and concatenation.

4 Preliminaries

  • The preliminaries introduce notation and cryptographic primitives used in later sections.Source: §4 · p. 11

4.1 Notation

  • The paper denotes computational and statistical security parameters by κ and λ, uses [n] for {1, …, n}, and || for string concatenation.Source: §4.1 · p. 11

4.2.1 Decisional Diffie–Hellman

  • The DDH assumption holds when every polynomial-time adversary’s advantage is bounded by a negligible function of λ.Source: §4.2.1 · p. 11

4.3 Pseudorandom Number Generator

  • A pseudorandom number generator maps a random seed to a sequence indistinguishable from truly random bits to an observer lacking the seed.Source: §4.3 · p. 11

4.4 Discrete Log Zero-Knowledge Proof

The section defines a discrete-log zero-knowledge proof and gives Schnorr protocol costs as an example.

4.4 Discrete Log Zero-Knowledge Proof

  • A discrete-log zero-knowledge proof lets Alice convince Bob she knows k for y = g^k without revealing k.Source: §4.4 · p. 11
  • Schnorr protocol communicates 2 group elements for a proof of knowledge of a discrete logarithm.Source: §4.4 · p. 11
  • Schnorr protocol requires 3 modular exponentiations in a cyclic group.Source: §4.4 · p. 11

4.5 Garbled Circuits

Garbled circuits are presented as a common generic technique for two-party secure computation, with the paper using subtraction and less-than circuits.

4.5 Garbled Circuits

  • Garbled circuits take two parties’ inputs and compute a function on them; the paper uses subtraction and less-than circuits.Source: §4.5 · p. 11
  • Modern garbled-circuit protocols evaluate two million AND gates per second on a 1Gbps LAN.Source: §4.5 · p. 11
  • Garbled circuits are described as the most common generic technique for two-party secure computation, first introduced by Yao and Goldreich et al..Source: §4.5 · p. 11

4.6 Private Information Retrieval

PIR lets clients retrieve or test database contents without revealing the requested item, with one-server and two-server designs trading off server computation and trust assumptions.

4.6 Private Information Retrieval

  • PIR is a private database query in which servers do not learn which item the client requests.Recent PIR reduces communication cost to logarithmic in database size.Source: §4.6 · p. 12

4.6.1 1-Server PIR

  • PIR lets a client retrieve DB[i] without revealing index i, using key generation, query, expansion, server answer, and client extraction.Single-server schemes use additive homomorphic encryption and require O(N) server operations; communication and computation trade off.Source: §4.6 · p. 12, §4.6.1 · p. 12

4.6.2 2-Server PIR

  • With two non-colluding servers, XOR-shared query keys hide the requested index while allowing the client to reconstruct DB[i].Communication is O(log(N)) bits and computation uses O(N) symmetric-key operations, faster than additive homomorphic operations.Source: §4.6.2 · p. 13

4.6.3 Keyword PIR

  • Keyword PIR lets a client test whether its item belongs to the server’s set without revealing the item itself.The paper considers keyword PIR based on both one-server and two-server PIR; a Cuckoo-hashing implementation costs approximately three times regular PIR.Source: §4.6.3 · p. 13

4.7 Private Set Intersection Cardinality

Private set intersection cardinality allows two parties to learn the size of the intersection of their private sets without revealing additional information.

4.7 Private Set Intersection Cardinality

  • PSI-CA lets one party learn the intersection size of two private sets without revealing any additional information.The paper presents the functionality in Figure 2.Source: §4.7 · p. 13

5 Our Epione System

Epione alerts users exposed to diagnosed individuals during an infection window by comparing locally received tokens with tokens regenerated from diagnosed users’ seeds. Its security discussion describes protections against linkage and false claims, while noting residual exposure from the intended match functionality and malicious queries.

5.1.1 Agreement and Setup Phase

  • Setup establishes the shared objective and security parameters, then gives users the server’s public key and each client a random PRG seed.The setup need not be repeated while the server configuration remains unchanged.Source: §5.1.1 · p. 14

5.1.2 Token Generation

  • Tokens are designed to look random without the user’s seed and to be reproducible for a given day and time slot.Users and the server must agree on token generation, time intervals, and day numbering.Source: §5.1.2 · p. 14

5.1.3 Contact

  • Nearby users exchange generated tokens, store received tokens locally, and discard tokens older than the infection window.Sent tokens can be regenerated from each user’s private seed rather than stored as a sent-token list.Source: §5.1.3 · pp. 14–15

5.1.4 Positive Diagnosis and Token Collection

  • Diagnosed users may consent to encrypting and submitting their PRG seeds through the healthcare provider, which lets the server regenerate their infection-window tokens.Two servers separate diagnosis status from sent tokens when the Epione server is untrusted; a healthcare-issued verification token does not prevent that server from linking a user to a positive diagnosis.Source: §5.1.4 · pp. 15–16

5.1.5 Query

  • Users compare their received tokens with diagnosed users’ sent tokens through PSI-CA and are notified if the intersection is nonempty.The user learns whether or how many tokens match; the server learns nothing about the user’s received tokens.Source: §5.1.5 · p. 16

5.2.1 Security Theorem

  • Epione securely implements its contact-tracing functionality in the semi-honest setting, assuming secure PSI-CA and a secure PRG.The paper omits the proof of this theorem.Source: §5.2.1 · p. 16

5.2.2 Defense against linkage attacks

  • The server cannot identify diagnosed users without healthcare-provider collusion, and PSI-CA prevents the server from learning users’ received tokens or social graph.Users learn only the number of matching tokens, while randomized tokens prevent tracking through Bluetooth beacons.Source: §5.2.2 · p. 17

5.2.3 Malicious User Queries

  • Arbitrary queries can expose diagnosed contacts; hash commitments with zero-knowledge proofs can check full-set queries, while rate limits and DRM make crafted queries impractical but not impossible.Even benign functionality can reveal an individual’s diagnosis when a user had only one contact; periodic commitments also mitigate retroactive false claims.Source: §5.2.3 · pp. 17–18

6 Cryptographic Gadgets

This section details the cryptographic tools used to implement Epione, emphasizing its PSI-CA design, PIR, and extensions.

6 Cryptographic Gadgets

  • The section details Epione’s cryptographic tools, with emphasis on PSI-CA, PIR, and extensions to those tools.Source: §6 · p. 18

6.1 PSI cardinality (PSI-CA) for asymmetric set sizes

Epione tailors PSI-CA to contact tracing, where a client has a small token set and the server holds a much larger one. Its DH-based construction lets clients learn intersection cardinality without revealing matching items.

6.1.1 Our technique

  • Using the same client exponent and shuffling server results lets the client count matches without learning which items intersect.The DH-based PSI protocol is extended to cardinality by using a common exponent; the shuffle hides the mapping to common items.Source: §6.1.1 · pp. 18–19
  • Contact tracing creates an asymmetric-set problem: clients have fewer than 500 new tokens per day, while servers may hold millions.The design targets client communication sub-linear in the server set size, with at most a few megabytes for mobile clients.Source: §6.1.1 · p. 19
  • Multi-query Keyword-PIR replaces the final PSI steps so clients can count matching queries without revealing their queried values to the server.The client learns no more about the server’s set than the number of matches.Source: §6.1.1 · p. 19

6.1.2 Protocol

  • Figure 5’s construction securely implements PSI-CA in the semi-honest setting, given the specified Multi-query Keyword PIR.The security argument relies on the DDH assumption in the cyclic group and a random oracle.Source: §6.1.2 · p. 20

6.1.3 PSI-CA Cost

  • Communication is O(n log(N)), client computation O(n), and server computation O(nN) for the PSI-CA protocol.The server-side cost comes from O(nN) additive homomorphic-encryption operations for Keyword-PIR.Source: §6.1.3 · p. 21
  • A two-server PIR variant can speed server computation by avoiding homomorphic-encryption operations.Source: §6.1.3 · p. 21

6.2 PSI-CA with 2-server PIR

The two-server extension uses independently operated PIR servers to reduce server-side computation. Its privacy guarantee depends on the servers not colluding.

6.2 PSI-CA with 2-server PIR

  • The second server can accelerate server-side computation by avoiding homomorphic-encryption operations.The primary server sends the dataset to the second server after computing it.Source: §6.2 · p. 21
  • The client sends PIR queries to both servers; neither learns the query as long as the servers do not collude.The primary server sends the dataset to the independently operated second server.Source: §6.2 · p. 21
  • Two-server PIR uses approximately 2N PRF calls and communicates O(log(N)) bits for PIR.Its PIR computation uses only symmetric-key operations.Source: §6.2 · p. 21

6.3 PSI-CA Extensions

The extensions consider threshold PSI-CA and defenses against malicious clients. The padding-based threshold approach has unresolved leakage parameters, while extending malicious-client security to full PSI-CA requires additional secure building blocks.

6.3.1 Potential approach from PSI-CA into threshold PSI-CA (t-PSI)

  • Revealing intersection size is acceptable for the contact-tracing application considered, but may be undesirable in other settings.Source: §6.3.1 · p. 22
  • Padding both sets with shared dummy items lets the client learn a masked intersection size, then a garbled circuit can test whether the true size exceeds a threshold.The client learns σ = |X ∩Y | + N′ but does not know N′.Source: §6.3.1 · p. 22
  • The padding approach’s coefficient for hiding the true intersection size is undetermined, and the authors say further analysis is needed.The client can infer a lower bound because |X ∩Y | = σ −N′ > σ −n′.Source: §6.3.1 · p. 22

6.3.2 Potential approach for extending to malicious client

  • A malicious client might compute DH messages incorrectly to learn which of its items appear in the server’s set.Source: §6.3.2 · p. 22
  • A zero-knowledge proof that the client computed its DH messages correctly is sufficient for malicious-client security of the DH-based PSI protocol.Source: §6.3.2 · pp. 22–23
  • Extending malicious-client security to PSI-CA requires malicious-secure Keyword-PIR and garbled circuits, plus a consistency check such as SPDZ MACs.The authors say they will explore this direction further.Source: §6.3.2 · p. 23

7 Implementation Choices and Performance Estimates

The section estimates Epione’s computation, communication, and storage costs under specified token and case assumptions, then considers implementation tradeoffs. Its estimates describe the system as feasible in practice, with configuration choices trading computation and network use against infrastructure needs and information leakage.

7.1 Parameters and token storage

  • Under the example assumptions, each client receives 1,120 tokens over 14 days, the server gets 5.6 million new tokens daily, client storage is 35 KiB, and 15-day server storage is 1.25 GiB.Storing only a seed for generated sent tokens can reduce client storage to 18 KiB; the server stores tokens by receipt day so clients can query only for tokens added since their previous check.Source: §7.1 · pp. 23–24

7.2 Implementation optimization: Database shape

  • The database is sharded into buckets padded with dummies, using transformed-token bits as shard and bucket addresses; the server learns shard-prefix bits, while clients cannot reverse the transformed, truncated bucket tokens.The example uses eight shards, 2^18 buckets per shard, and three transformed tokens per bucket; the authors argue that clients querying many tokens will usually query all shards.Source: §7.2 · p. 24

7.2.1 Single Server PIR Performance

  • With single-server PIR, caching reduces daily communication to 36 MiB; without that caching, estimated total communication is approximately 124 MiB.The estimates also give 1.06 seconds per shard for one-time preprocessing and 98 milliseconds for querying 80 new items with cached keys.Source: §7.2.1 · p. 25

7.2.2 2-Server PIR Performance

  • With two independently operated, non-colluding servers, client-side caching reduces the estimated query time to 7.42 seconds and database expansion takes 104 seconds before sharding.Sharding reduces estimated server expansion to 1.63 seconds; estimated network use is 288 KiB, and maintaining caches across both servers is considered impractical.Source: §7.2.2 · pp. 25–26

7.3 Token Transforms

  • Reusing the server exponent permits offline precomputation of 5.6 million token transforms in about five minutes, while client caching reduces online server transforms from 60 to 4.3 milliseconds per user.With cached transformed tokens, the client computes 80 new exponentiations in each of preprocessing and online phases, estimated at 4.32 milliseconds per phase; reusing the exponent also permits a client to test whether a chosen token is in the database.Source: §7.3 · pp. 26–27

7.4 Caching and Security

  • Caching can reveal to the server which transformed tokens are old, new, or removed, allowing a more precise estimate of daily token volume, though not the token values themselves.Adding dummies to equalize or randomize daily query sizes, or dropping caching, are presented as ways to address this leakage.Source: §7.4 · p. 27

7.5 Overall PSI-CA Performance Estimates

  • The 2-server approach reduces server computation and network bandwidth but requires an independent party; single-server queries are also considered feasible, with caching reducing traffic.The authors estimate about 35 seconds for a single-server query and 37 MiB of network traffic with query-key caching, and say database parameters can be tuned for different computation/network tradeoffs.Source: Table 2 · p. 27, Table 3 · p. 27, §7.5 · p. 28
Loading 2004.13293v3…