Paper 2025/1071
PICS: Private Intersection over Committed (and reusable) Sets
Abstract
Private Set Intersection (PSI) enables two parties to compute the intersection of their private sets without revealing any additional information. While maliciously secure PSI protocols prevent many attacks, adversaries can still exploit them by using inconsistent inputs across multiple sessions. This limitation stems from the definition of malicious security in secure multiparty computation, but is particularly problematic in PSI because: (1) real-world applications---such as Apple’s PSI protocol for CSAM detection and private contact discovery in messaging apps---often require multiple PSI executions over consistent inputs, and (2) the PSI functionality makes it relatively easy for adversaries to infer additional information. We propose {\em Private Intersection over Committed Sets (PICS)}, a new framework that enforces input consistency across multiple sessions via committed sets. Building on the state-of-the-art maliciously secure PSI framework (i.e., VOLE-PSI [EUROCRYPT 2021]), we present an efficient instantiation of PICS % in the random oracle model using lightweight cryptographic tools. We implement our protocol to demonstrate concrete efficiency. Compared to VOLE-PSI, for input sets of size $2^{24}$, our communication overhead is as low as $1.1\%$. Our end-to-end performance overhead is $130\%$ in the LAN setting and decreases to $80\%-10\%$ in the WAN setting with bandwidths ranging from $200$ to $5$ Mbps.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- PSIPolynomial CommitmentsVOLE
- Contact author(s)
-
aarushi @ purdue edu
peihan_miao @ brown edu
phuoc_pham_van_long @ brown edu
sing1745 @ purdue edu - History
- 2025-06-09: approved
- 2025-06-07: received
- See all versions
- Short URL
- https://ia.cr/2025/1071
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2025/1071, author = {Aarushi Goel and Peihan Miao and Phuoc Van Long Pham and Satvinder Singh}, title = {{PICS}: Private Intersection over Committed (and reusable) Sets}, howpublished = {Cryptology {ePrint} Archive, Paper 2025/1071}, year = {2025}, url = {https://eprint.iacr.org/2025/1071} }