TY - GEN
T1 - Catalic
T2 - 26th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2020
AU - Duong, Thai
AU - Phan, Duong Hieu
AU - Trieu, Ni
N1 - Funding Information:
Acknowledgments. We thank all anonymous reviewers and Ling Ren for insightful feedback. Ni Trieu was partially supported by NSF award #2031799 and Duong Hieu Phan was partially supported by the ANR ALAMBIC (ANR16-CE39-0006). Research conducted in part while Ni Trieu at University of California, Berkeley and Duong Hieu Phan at University of Limoges.
Publisher Copyright:
© 2020, International Association for Cryptologic Research.
PY - 2020
Y1 - 2020
N2 - Private Set Intersection Cardinality (PSI-CA) allows two parties, each holding a set of items, to learn the size of the intersection of those sets without revealing any additional information. To the best of our knowledge, this work presents the first protocol that allows one of the parties to delegate PSI-CA computation to untrusted servers. At the heart of our delegated PSI-CA protocol is a new oblivious distributed key PRF (Odk-PRF) abstraction, which may be of independent interest. We explore in detail how to use our delegated PSI-CA protocol to perform privacy-preserving contact tracing. It has been estimated that a significant percentage of a given population would need to use a contact tracing app to stop a disease’s spread. Prior privacy-preserving contact tracing systems, however, impose heavy bandwidth or computational demands on client devices. These demands present an economic disincentive to participate for end users who may be billed per MB by their mobile data plan or for users who want to save battery life. We propose Catalic (ContAct TrAcing for LIghtweight Clients), a new contact tracing system that minimizes bandwidth cost and computation workload on client devices. By applying our new delegated PSI-CA protocol, Catalic shifts most of the client-side computation of contact tracing to untrusted servers, and potentially saves each user hundreds of megabytes of mobile data per day while preserving privacy.
AB - Private Set Intersection Cardinality (PSI-CA) allows two parties, each holding a set of items, to learn the size of the intersection of those sets without revealing any additional information. To the best of our knowledge, this work presents the first protocol that allows one of the parties to delegate PSI-CA computation to untrusted servers. At the heart of our delegated PSI-CA protocol is a new oblivious distributed key PRF (Odk-PRF) abstraction, which may be of independent interest. We explore in detail how to use our delegated PSI-CA protocol to perform privacy-preserving contact tracing. It has been estimated that a significant percentage of a given population would need to use a contact tracing app to stop a disease’s spread. Prior privacy-preserving contact tracing systems, however, impose heavy bandwidth or computational demands on client devices. These demands present an economic disincentive to participate for end users who may be billed per MB by their mobile data plan or for users who want to save battery life. We propose Catalic (ContAct TrAcing for LIghtweight Clients), a new contact tracing system that minimizes bandwidth cost and computation workload on client devices. By applying our new delegated PSI-CA protocol, Catalic shifts most of the client-side computation of contact tracing to untrusted servers, and potentially saves each user hundreds of megabytes of mobile data per day while preserving privacy.
KW - Contact tracing
KW - Linkage attack
KW - Private Set Intersection Cardinality
UR - http://www.scopus.com/inward/record.url?scp=85097866547&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85097866547&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-64840-4_29
DO - 10.1007/978-3-030-64840-4_29
M3 - Conference contribution
AN - SCOPUS:85097866547
SN - 9783030648398
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 870
EP - 899
BT - Advances in Cryptology – ASIACRYPT 2020 - 26th International Conference on the Theory and Application of Cryptology and Information Security, 2020, Proceedings
A2 - Moriai, Shiho
A2 - Wang, Huaxiong
PB - Springer Science and Business Media Deutschland GmbH
Y2 - 7 December 2020 through 11 December 2020
ER -