Paper 2023/371

PACIFIC: Privacy-preserving automated contact tracing scheme featuring integrity against cloning

Scott Griffy, Brown University
Anna Lysyanskaya, Brown University

To be useful and widely accepted, automated contact tracing / expo- sure notification schemes need to solve two problems at the same time: they need to protect the privacy of users while also protecting the users’ from the behavior of a malicious adversary who may potentially cause a false alarm. In this paper, we provide, for the first time, an exposure notification construction that guarantees the same levels of privacy as ex- isting schemes (notably, the same as CleverParrot of [CKL+20]), which also provides the following integrity guarantees: no malicious user can cause exposure warnings in two locations at the same time; and any up- loaded exposure notifications must be recent, and not previously used. We provide these integrity guarantees while staying efficient by only re- quiring a single broadcast message to complete multiple contacts. Also, a user’s upload remains linear in the number of contacts, similar to other schemes. Linear upload complexity is achieved with a new primitive: zero knowledge subset proofs over commitments. Our integrity guarantees are achieved with a new primitive as well: set commitments on equivalence classes. Both of which are of independent interest.

Available format(s)
Publication info
Contact author(s)
scott_griffy @ brown edu
anna_lysyanskaya @ brown edu
2023-04-02: revised
2023-03-14: received
See all versions
Short URL
Creative Commons Attribution


      author = {Scott Griffy and Anna Lysyanskaya},
      title = {PACIFIC: Privacy-preserving automated contact tracing scheme featuring integrity against cloning},
      howpublished = {Cryptology ePrint Archive, Paper 2023/371},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.