Private Set Intersection

TODO Definition

An attempt at capturing the dimensions of PSI:

  • Parties
    • 2 or multiparty?
  • Set Assumptions
    • Does the protocol assume any imbalance in the set sizes? (Unbalanced or balanced)
  • Correctness
  • Soundness
  • Privacy
    • Does the protocol reveal the set sizes? (Size-hiding or not)
    • Does the

Questions to ask when reading the paper

  • Number of parties: 2 or multiple
  • Is it one-sided or multi-sided? (Everyone gets the output or a specified party)
  • Corruption Model (Semi-honest, Malicious, Malicious and Helper)

Notes

  • First introduced by Meadows 1985 S&P
  • Typically \(\lambda = 40\) and the failure probability expected is \(2^{-40}\).

TODO Best Semi-honest 2-party implementation

TODO Best Semi-honest multi-party implementation

TODO Best Malicious 2-party implementation

TODO Best Malicious multi-party implementation

TODO Best Malicious multiparty-with-helper implementation

Variations of the problem

[BROKEN LINK: 62a2fc2a-4af1-47da-a048-68c502d32554]

[BROKEN LINK: 984997b8-639b-46b7-a3a4-8e4deb1158ac]

[BROKEN LINK: 182af966-e6c7-4cea-8f2d-7f7353f05d5b]

[BROKEN LINK: b5f480ee-a18d-4714-bd7a-5fb64ca3dad1]

[BROKEN LINK: 5fa7ee52-ca87-4146-8f62-5f905c9e4361]

Asymmetric PSI (Unbalanced PSI)

Labelled PSI

Circuit PSI

PSI-WCA

PSI with weighted cardinality (I learnt about it from Streaming and Unbalanced PSI from Function Secret Sharing. Samuel Dittmer, Yuval Ishai, Steve Lu, Rafail Ostrovsky, Mohamed Elsabagh, Nikolaos Kiourtis, Brian Schulte, and Angelos Stavrou. 2022)

Surveys

  • SoK: Collusion-resistant Multi-party Private Set Intersections in the Semi-honest Model. Jelle Vos, Mauro Conti, and Zekeriya Erkin. 2024