Course contentsShow
← Security
Lesson 2925 of 3,05254. Privacy EngineeringFree lesson

Private Set Intersection

Techniques for computing the intersection of datasets without revealing non-overlapping elements to parties.

Private Set Intersection

What you'll learn: How two parties can discover which elements their datasets have in common without revealing anything else about their data.

The Privacy Problem with Set Comparison

Imagine two hospitals want to identify patients who visited both facilities (perhaps for research coordination), but neither wants to reveal their full patient list to the other. Or two companies want to find shared customers without exposing their entire customer databases to competitors.

Traditional set intersection is simple: just compare the lists. But that requires each party to see the other's complete dataset—a privacy disaster.

How Private Set Intersection Works

Private Set Intersection (PSI) uses cryptographic protocols—often building on secure multi-party computation or homomorphic encryption techniques you've learned—to compute the intersection without revealing non-overlapping elements.

The basic approach:

  1. Each party holds a private set of elements (e.g., email addresses, IDs)
  2. They engage in a cryptographic protocol where data is encrypted or hashed in special ways
  3. Only matching elements are revealed to one or both parties
  4. Non-matching elements remain completely hidden from the other party

Common Techniques

  • Hash-based protocols: Using commutative encryption or oblivious pseudorandom functions
  • Public-key approaches: Encrypting set elements so only matches decrypt properly
  • Garbled circuits: Encoding the comparison logic itself as an encrypted computation
  • Homomorphic encryption: Performing set operations on encrypted data directly

The result: Hospital A learns only the shared patient IDs, never seeing Hospital B's unique patients, and vice versa.

Key Takeaway: Private Set Intersection enables parties to find common elements in their datasets while cryptographically guaranteeing that non-overlapping data remains completely private—essential for privacy-preserving data collaboration.