Paper 2024/1183
Updatable Private Set Intersection from Structured Encryption
Abstract
Many efficient custom protocols have been developed for two-party private set intersection (PSI), that allow the parties to learn the intersection of their private sets. However, these approaches do not yield efficient solutions in the dynamic setting when the parties’ sets evolve and the intersection has to be computed repeatedly. In this work we propose a new framework for this problem of updatable PSI — with elements being inserted and deleted — in the semihonest model based on structured encryption. The framework reduces the problem of updatable PSI to a new variant of structured encryption (StE) for an updatable set datatype, which may be of independent interest. Our final construction is a constant round protocol with worst-case communication and computation complexity that grows linearly in the size of the updates and only poly-logarithmically with the size of the accumulated sets. Our protocol is the first to support arbitrary inserts and deletes for updatable PSI.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- private set intersectionstructured encryption
- Contact author(s)
-
archita agarwal @ mongodb com
davidcash @ uchicago edu
marilyn george @ mongodb com
seny kamara @ mongodb com
tarik moataz @ mongodb com
sing1361 @ purdue edu - History
- 2024-07-25: approved
- 2024-07-22: received
- See all versions
- Short URL
- https://ia.cr/2024/1183
- License
-
CC BY-NC-SA
BibTeX
@misc{cryptoeprint:2024/1183,
author = {Archita Agarwal and David Cash and Marilyn George and Seny Kamara and Tarik Moataz and Jaspal Singh},
title = {Updatable Private Set Intersection from Structured Encryption},
howpublished = {Cryptology {ePrint} Archive, Paper 2024/1183},
year = {2024},
url = {https://eprint.iacr.org/2024/1183}
}