Syllabus Lesson 135 of 156 · Privacy tech beyond blocking
Privacy tech beyond blocking

Private Set Intersection

Why it matters Companies often want to know which customers they share, for a joint offer or to measure whether an ad worked. The easy way is to swap customer lists, which means your email lands in another company's database. Private Set Intersection lets them find the overlap without either side handing over its list. Knowing how it works lets you tell real privacy from "we only shared hashed emails".

Teaching crypto, not secure: the numbers in this module's labs are small enough to read and the randomness is seeded so grading is repeatable. Real systems use vetted libraries and far larger numbers. Never copy teaching code into a product.

The problem

A shop and an app each have a list of customer emails. They want the emails on both lists, and nothing else: the shop must not learn the app's other users, and the app must not learn the shop's other customers.

Set intersection: the items two lists have in common. Private Set Intersection (PSI): a way for two parties to compute it while revealing nothing else about their lists.

Why "just hash it" fails

Hash: a function that turns text into a fixed-length scramble (SHA-256 is a common one). The same input always gives the same output, and you cannot run it backwards directly.

"We swap hashed emails, so nobody sees the real ones" sounds safe. But emails are guessable. Anyone holding a list of likely emails can hash every guess and look for matches, like trying every key on a big key ring. Your naive_reverse function will do exactly that with the practice world's 200 synthetic emails. Hashing hides data only when the inputs cannot be guessed, and emails, phone numbers and names can be.

The two-locks trick

Remember from the maths lesson: putting secret a on, then secret b, gives the same as b then a. Picture each email as a box. Alice puts her own lock on each of her boxes and sends them to Bob. Bob adds his lock and sends them back. Bob also locks his own boxes and sends them to Alice, who adds her lock. Now every box has both locks, and two boxes with the same email inside look identical, whichever lock went on first.

In numbers, with the practice group from watched.leg7a_privacy (P, hash_to_group, random_secret):

  1. Alice sends blind(alice_items, a): each item hashed into the group then raised to a.
  2. Bob raises those to b (reblind) and sends them back in the same order.
  3. Bob sends blind(bob_items, b).
  4. Alice raises Bob's values to a. Any of her double-locked values that appear in Bob's double-locked set is a shared item. Because she kept the order, she knows which of her items each one is.

Why is this safe where hashing failed? To test a guess, you need both secrets, and each side keeps its own. Bob only ever sees Alice's values with her secret on, which look like random numbers.

Diffie-Hellman PSI: this protocol's name, after the 1976 key-exchange idea it borrows (two parties combining secret exponents). Real versions use elliptic curves (a different kind of group, with the same "order does not matter" property and much shorter numbers) and careful hashing.

The answer is itself a disclosure

Even perfect PSI tells Alice that a particular person is Bob's customer. If Bob is a clinic or a debt adviser, that is sensitive. Often a company only needs how many customers are shared. In PSI cardinality Bob shuffles his reply in step 2, so Alice can count matches but cannot tell which of her items they belong to. Ask for the least that answers the question.

In other languages

The blinding step in JavaScript with BigInt (using a powMod helper like the one in the maths lesson):

const blind = (items, secret) => items.map(x => powMod(hashToGroup(x), secret, P));
const reblind = (values, secret) => values.map(v => powMod(v, secret, P));

And in Go with math/big:

func reblind(values []*big.Int, secret, p *big.Int) []*big.Int {
    out := make([]*big.Int, len(values))
    for i, v := range values {
        out[i] = new(big.Int).Exp(v, secret, p)
    }
    return out
}

For real products, use an audited PSI library rather than writing your own.

Recap

  • Hashed emails are easy to reverse with a list of guesses, so "we only shared hashes" is not privacy.
  • Diffie-Hellman PSI double-locks every item with two secrets whose order does not matter, so matches show up without either list being revealed.
  • Keeping the order reveals which items match; shuffling (PSI cardinality) reveals only how many.
  • The intersection is itself personal data, so ask for the least that answers the question.
Your turn

Write five functions. naive_reverse(hashes, candidates) returns the sorted list of candidates whose SHA-256 hex digest (hashlib.sha256(c.encode()).hexdigest()) is in hashes. blind(items, secret) returns [pow(hash_to_group(x), secret, P) for x in items]. reblind(values, secret) raises each value to secret modulo P, keeping the order. psi(alice_items, bob_items, a_secret, b_secret) follows the four steps of the lesson using blind and reblind, and returns the sorted list of Alice's items that Bob also has. psi_cardinality(alice_items, bob_items, a_secret, b_secret, rng) does the same but shuffles Bob's reply with rng.shuffle and returns only the number of shared items.

Spotted a problem in this lesson? Report it

Code · runs in your browser
Output

        

      

      
      

        Back