Provably Secure Contact Tracing with Conditional Private Set Intersection

The novel coronavirus COVID-19 spreads easily through personal contact, requiring the use of contact tracing to track the spread of the disease. Many existing approaches either trust a public health authority with private data, or publish patients’ data, leading to privacy breaches. Private Set Intersection based on Homomorphic Encryption is a promising solution, but it is limited because the management of keys is challenging and further filtering of contacts is not included. We present a protocol for secure and private conditional contact tracing, allowing the tracking of users’ contacts subject to extra conditions. We construct and apply our new primitive of Conditional Private Set Intersection and combine it with a Trusted Execution Environment (TEE) to construct a protocol with provable security and a high degree of functionality. Our approach moves the memory- and computation-intensive portions of contact tracing out of the TEE to a cloud server. We also present how multi-hop contact tracing can be done with minimal user communication. Our proof-of-concept implementation with Microsoft SEAL allows users to perform their computation in less than 9 min, and the cloud’s per-user computation can be as little as 11 min for a population of 50,000 users with 500 infected (assuming 40 contacts/user) in a day. With other HE libraries/schemes that allows customized parameter sets, our protocol will show much higher scalability.