Research Article
Provably Secure Contact Tracing with Conditional Private Set Intersection
@INPROCEEDINGS{10.1007/978-3-030-90019-9_18, author={Jonathan Takeshita and Ryan Karl and Alamin Mohammed and Aaron Striegel and Taeho Jung}, title={Provably Secure Contact Tracing with Conditional Private Set Intersection}, proceedings={Security and Privacy in Communication Networks. 17th EAI International Conference, SecureComm 2021, Virtual Event, September 6--9, 2021, Proceedings, Part I}, proceedings_a={SECURECOMM}, year={2021}, month={11}, keywords={Contact tracing Lattice-based cryptography Private set intersection Trusted execution environment}, doi={10.1007/978-3-030-90019-9_18} }- Jonathan Takeshita
Ryan Karl
Alamin Mohammed
Aaron Striegel
Taeho Jung
Year: 2021
Provably Secure Contact Tracing with Conditional Private Set Intersection
SECURECOMM
Springer
DOI: 10.1007/978-3-030-90019-9_18
Abstract
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.
