Please enable JavaScript.
Coggle requires JavaScript to display documents.
Private Set Intersection (PSI) - Coggle Diagram
Private Set Intersection (PSI)
Main Technical Approaches
Public Key Cryptography
Diffie-Hellman based (Commutative Encryption)
RSA-based PSI
Oblivious Transfer (OT)
OT-Extension (High efficiency)
Garbled Circuits (Generic but slower)
Homomorphic Encryption (HE)
Fully Homomorphic Encryption (FHE)
Labeled PSI (Associating data with items)
Unbalanced PSI
One party has a massive set (e.g., Google/Apple), one has a small set (User).
Core Concept
Goal: Two parties (Alice and Bob) compute the intersection of their private sets
Privacy Guarantee: Neither party learns anything about the elements not in the intersection.
Analogy: Finding mutual friends on a social app without sharing your entire contact list.
Key Components/Primitives
Hashing Functions
Cuckoo Hashing (Optimizing storage/lookup)
Bloom Filters (Probabilistic intersection)
Oblivious PRF (OPRF)
The "gold standard" for modern, fast PSI.
Polynomial Encoding
Representing sets as roots of a polynomial.
Security & Threat Models
Semi-Honest (Honest-but-Curious)
Parties follow the protocol but try to learn more from the transcript.
Malicious
Parties may provide fake inputs or deviate from steps.
Side-Channel Attacks
Leakage via timing or communication volume.
Real-World Use Cases
Contact Discovery (Signal, WhatsApp)
Ad Conversion Tracking (Google/Meta measuring clicks without sharing user IDs)
Data Clean Rooms (Collaborative research between banks or hospitals)
Password Breach Checking (Checking if your password is in a leaked database)