PEPSI: Practically Efficient Private Set Intersection in the Unbalanced Setting
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913470352457728 |
|---|---|
| author | Mahdavi, Rasoul Akhavan Lukas, Nils Ebrahimianghazani, Faezeh Humphries, Thomas Kacsmar, Bailey Premkumar, John Li, Xinda Oya, Simon Amjadian, Ehsan Kerschbaum, Florian |
| author_facet | Mahdavi, Rasoul Akhavan Lukas, Nils Ebrahimianghazani, Faezeh Humphries, Thomas Kacsmar, Bailey Premkumar, John Li, Xinda Oya, Simon Amjadian, Ehsan Kerschbaum, Florian |
| contents | Two parties with private data sets can find shared elements using a Private Set Intersection (PSI) protocol without revealing any information beyond the intersection. Circuit PSI protocols privately compute an arbitrary function of the intersection - such as its cardinality, and are often employed in an unbalanced setting where one party has more data than the other. Existing protocols are either computationally inefficient or require extensive server-client communication on the order of the larger set. We introduce Practically Efficient PSI or PEPSI, a non-interactive solution where only the client sends its encrypted data. PEPSI can process an intersection of 1024 client items with a million server items in under a second, using less than 5 MB of communication. Our work is over 4 orders of magnitude faster than an existing non-interactive circuit PSI protocol and requires only 10% of the communication. It is also up to 20 times faster than the work of Ion et al., which computes a limited set of functions and has communication costs proportional to the larger set. Our work is the first to demonstrate that non-interactive circuit PSI can be practically applied in an unbalanced setting. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_14565 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | PEPSI: Practically Efficient Private Set Intersection in the Unbalanced Setting Mahdavi, Rasoul Akhavan Lukas, Nils Ebrahimianghazani, Faezeh Humphries, Thomas Kacsmar, Bailey Premkumar, John Li, Xinda Oya, Simon Amjadian, Ehsan Kerschbaum, Florian Cryptography and Security Two parties with private data sets can find shared elements using a Private Set Intersection (PSI) protocol without revealing any information beyond the intersection. Circuit PSI protocols privately compute an arbitrary function of the intersection - such as its cardinality, and are often employed in an unbalanced setting where one party has more data than the other. Existing protocols are either computationally inefficient or require extensive server-client communication on the order of the larger set. We introduce Practically Efficient PSI or PEPSI, a non-interactive solution where only the client sends its encrypted data. PEPSI can process an intersection of 1024 client items with a million server items in under a second, using less than 5 MB of communication. Our work is over 4 orders of magnitude faster than an existing non-interactive circuit PSI protocol and requires only 10% of the communication. It is also up to 20 times faster than the work of Ion et al., which computes a limited set of functions and has communication costs proportional to the larger set. Our work is the first to demonstrate that non-interactive circuit PSI can be practically applied in an unbalanced setting. |
| title | PEPSI: Practically Efficient Private Set Intersection in the Unbalanced Setting |
| topic | Cryptography and Security |
| url | https://arxiv.org/abs/2310.14565 |