popets-2023-0091.pdf (1.02 MB)

Private Collection Matching Protocols

Download (1.02 MB)
conference contribution
posted on 2024-04-08, 08:37 authored by Kasra EdalatNejad, Mathilde Raynal, Wouter LueksWouter Lueks, Carmela Troncoso
We introduce Private Collection Matching (PCM) problems, in which a client aims to determine whether a collection of sets owned by a server matches their interests. Existing privacy-preserving cryptographic primitives 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.


Primary Research Area

  • Trustworthy Information Processing

Name of Conference

Privacy Enhancing Technologies Symposium (PETS)


Proceedings on Privacy Enhancing Technologies



Page Range



Privacy Enhancing Technologies Symposium Advisory Board

Open Access Type

  • Hybrid


@inproceedings{EdalatNejad:Raynal:Lueks:Troncoso:2023, title = "Private Collection Matching Protocols", author = "EdalatNejad, Kasra" AND "Raynal, Mathilde" AND "Lueks, Wouter" AND "Troncoso, Carmela", year = 2023, month = 7, journal = "Proceedings on Privacy Enhancing Technologies", number = "3", pages = "446--468", publisher = "Privacy Enhancing Technologies Symposium Advisory Board", issn = "2299-0984", doi = "10.56553/popets-2023-0091" }