Catalic: Delegated PSI Cardinality with Applications to Contact Tracing

Thai Duong, Duong Hieu Phan, Ni Trieu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

51 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology – ASIACRYPT 2020 - 26th International Conference on the Theory and Application of Cryptology and Information Security, 2020, Proceedings
EditorsShiho Moriai, Huaxiong Wang
PublisherSpringer Science and Business Media Deutschland GmbH
Pages870-899
Number of pages30
ISBN (Print)9783030648398
DOIs
StatePublished - 2020
Event26th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2020 - Daejeon, Korea, Republic of
Duration: Dec 7 2020Dec 11 2020

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12493 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference26th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2020
Country/TerritoryKorea, Republic of
CityDaejeon
Period12/7/2012/11/20

Keywords

  • Contact tracing
  • Linkage attack
  • Private Set Intersection Cardinality

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Catalic: Delegated PSI Cardinality with Applications to Contact Tracing'. Together they form a unique fingerprint.

Cite this