Abstract. In this presentation, we introduce a new class of problems called Private Collection Matching (PCM), in which clients aim to determine whether a collection of sets owned by a server matches their interests. This class of problems is closely linked to an existing cryptographic primitive called Private Set Intersection (PSI), as interest in server sets is often determined based on a function of their intersection with the client's set. However, we show that existing privacy-preserving cryptographic primitives, including PSI, cannot solve PCM problems efficiently without harming privacy. We propose a modular framework that enables designers to build privacy-preserving PCM systems that output one bit: whether a collection of server sets matches the client's set. The communication cost of our protocols scales linearly with the size of the client's set and is independent of the number of server elements. We demonstrate the potential of our framework by designing and implementing novel solutions for two real-world PCM problems: determining whether a dataset has chemical compounds of interest, and determining whether a document collection has relevant documents. Our evaluation shows that we offer a privacy gain with respect to existing works at a reasonable communication and computation cost.
Joint work with: Mathilde Raynal (EPFL), Wouter Lueks (CISPA Helmholtz Center for Information Security), Carmela Troncoso (EPFL)
WPEC 2024: NIST Workshop on Privacy-Enhancing Cryptography 2024. Virtual, 2024-Sep-24–26.
NIST Workshop on Privacy-Enhancing Cryptography 2024
Starts: September 24, 2024Virtual
Security and Privacy: cryptography