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

PSI-CA Private Set Intersection Cardinality

Updateable PSI

Fuzzy PSI

Structure Aware PSI

Multi-party Private Set Intersection (MPSI)

Asymmetric PSI (Unbalanced PSI)

Labelled PSI

Circuit PSI

PSI-WCA

PSI with weighted cardinality (I learnt about it from [1])

Surveys

[2]