Private set intersection

Private set intersection is a secure multiparty computation cryptographic technique that allows two parties holding sets to compare encrypted versions of these sets in order to compute the intersection.

Uses your system voice; voice and rate in settings.

Snapshot

≈ 5 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

Private set intersection is a secure multiparty computation cryptographic technique[1] that allows two parties holding sets to compare encrypted versions of these sets in order to compute the intersection. In this scenario, neither party reveals anything to the counterparty except for the elements in the intersection.

Other variants of this exist, such as the server-client scenario, in which only the client learns the intersection of her set with the set of the server, without the server learning intersection of his set with the clients. [2]

For the comparison of data sets by cryptographic hashes on a small or predictable domain, precautions should be taken to prevent dictionary attacks.[3]

Apple uses this technique in Password Monitoring.[4] It has proposed using the technology for its announced Expanded Protections for Children [5]

In general, PSI protocols can be categorized into two broad categories: (1) traditional PSI and (2) delegated PSI. In the traditional PSI category, the data owners interact directly with each other and need to have a copy of their set at the time of the computation, e.g.,.[6] In the delegated PSI the computation of PSI and/or the storage of sets can be delegated to a third-party server (that is itself might be a passive or active adversary). The delegated PSI category can be further divided into two classes: (a) those that support one-off delegation, and (b) those that support repeated delegation. The PSI protocols that support one-off delegation require the data owner to re-encode its data and send the encoded data to the server for each computation, e.g.,.[7] Those that support repeated delegation allow the data owners to upload their (encrypted) data to the server only once, and then re-use it many times for each computation carried out but the server, e.g.,[8]

Recently, researchers have proposed a variant of PSI protocol (in both traditional and delegated categories) that support data update, e.g., .[9][10] This type of PSI protocol lets data owners insert/delete set elements into/from their data with low overheads and in a privacy-preserving manner.

Educational example

edit edit source

This educational example demonstrated the key idea of PSI, but does not provide real-world cryptographic security (hence should not be used with real-world data).

# Example sets party_a_set = {"apple", "banana", "cherry"} party_b_set = {"banana", "orange", "apple"} # Hashing the elements in both sets hashed_party_a_set = {hash(e) for e in party_a_set} hashed_party_b_set = {hash(e) for e in party_b_set} # Finding the intersection of the hashed sets intersection = hashed_party_a_set.intersection(hashed_party_b_set) # Printing hashed intersection for demonstration print(intersection)

References

edit edit source
  1. ^ Chen, Hao; Laine, Kim; Rindal, Peter (2018-05-16). Fast Private Set Intersection from Homomorphic Encryption. Association for Computing Machinery. ISBN 9781450349468. Wikipedia revision 1322645903, retrieved 2026-11-18
  2. ^ Pinkas, Benny. Private Set Intersection (PDF). Wikipedia revision 1322645903, retrieved 2026-11-18
  3. ^ Ihle, Cornelius; Schubotz, Moritz; Meuschke, Norman; Gipp, Bela (2020-08-02). "A First Step Towards Content Protecting Plagiarism Detection". Proceedings of the ACM/IEEE Joint Conference on Digital Libraries in 2020. Virtual Event China: ACM. pp. 341–344. arXiv:2005.11504. doi:10.1145/3383583.3398620. ISBN 978-1-4503-7585-6. Wikipedia revision 1322645903, retrieved 2026-11-18
  4. ^ "Password Monitoring". Retrieved 8 August 2021. Wikipedia revision 1322645903, retrieved 2026-11-18
  5. ^ "Child Safety". Retrieved 8 August 2021. Wikipedia revision 1322645903, retrieved 2026-11-18
  6. ^ Freedman, Michael J; Nissim, Kobbi; Pinkas, Benny (2004). "Efficient private matching and set intersection" (PDF). International Conference on the Theory and Applications of Cryptographic Techniques'04: Proceedings. Lecture Notes in Computer Science. Vol. 3027. pp. 1–19. doi:10.1007/978-3-540-24676-3_1. ISBN 978-3-540-21935-4. S2CID 10184294. Wikipedia revision 1322645903, retrieved 2026-11-18
  7. ^ Kamara, Seny; Mohassel, Payman; Raykova, Mariana; Sadeghian, Saeed (2014). "Scaling private set intersection to billion-element sets" (PDF). International Conference on Financial Cryptography and Data Security'14: Proceedings: 195–215. Wikipedia revision 1322645903, retrieved 2026-11-18
  8. ^ Abadi, Aydin; Terzis, Sotirios; Dong, Changyu (2016). "VD-PSI: verifiable delegated private set intersection on outsourced private datasets" (PDF). International Conference on Financial Cryptography and Data Security'16: Proceedings: 149–168. Wikipedia revision 1322645903, retrieved 2026-11-18
  9. ^ Abadi, Aydin; Dong, Changyu; Murdoch, Steven J; Terzis, Sotirios (2022). "Multi-party Updatable Delegated Private Set Intersection" (PDF). International Conference on Financial Cryptography and Data Security'22: Proceedings. Wikipedia revision 1322645903, retrieved 2026-11-18
  10. ^ Badrinarayanan, Saikrishna; Miao, Peihan; Xie, Tiancheng (2022). "Updatable Private Set Intersection" (PDF). Privacy Enhancing Technologies'22:Proceedings. 2022 (2): 378–406. doi:10.2478/popets-2022-0051. S2CID 239000070. Wikipedia revision 1322645903, retrieved 2026-11-18

Text derived from https://en.wikipedia.org/w/index.php?oldid=1322645903 under CC BY-SA 4.0; modifications have been made.