Introduction

When you install a messaging app, it offers to find which of your contacts already use the service. But how can the app know — without you uploading your entire address book to a server that could store, sell, or leak it?

This is the problem Private Set Intersection (PSI) was built to solve. Two parties — say, you and a server — each hold a list of items. PSI is a cryptographic protocol that lets both sides learn exactly which items appear in both lists and nothing else. Your contacts that aren't on the service stay invisible to the server. The server's user list stays invisible to you.

PSI sits at the heart of secure multi-party computation: the remarkable idea that two mutually distrusting parties can jointly compute a function of their private inputs without either one learning the other's data beyond what the output itself implies. It is not an open problem — practical protocols exist and are deployed today. But building one that is both provably secure and fast enough for millions of contacts requires some of the deepest ideas in modern cryptography.

Try It

Below are two contact lists — Alice's phone and a server's user database. Neither side should see the other's full list. Click Run PSI to simulate the protocol: only the names that appear in both lists will be revealed.

<p class="hint">Alice's phone holds her contact list (left). The server knows its registered users (right). Neither side sees the other's full list — only the <b>intersection</b> is revealed after the PSI protocol runs.</p>
<div class="psi-layout">
  <div class="panel" id="alice-panel">
    <div class="panel-title">Alice's contacts</div>
    <ul id="alice-list" class="contact-list"></ul>
  </div>
  <div class="panel result-panel">
    <div class="panel-title">Common contacts</div>
    <ul id="result-list" class="contact-list result"></ul>
    <div class="status" id="status">Press Run PSI to start.</div>
  </div>
  <div class="panel" id="server-panel">
    <div class="panel-title">Server users</div>
    <ul id="server-list" class="contact-list"></ul>
  </div>
</div>
<div class="btns">
  <button id="run" type="button">Run PSI</button>
  <button id="shuffle" type="button" class="ghost">Shuffle contacts</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .9rem; line-height: 1.45; }
.psi-layout { display: grid; grid-template-columns: 1fr 1fr 1fr; gap: 10px; margin-bottom: .7rem; }
.panel { background: #f0f4f8; border: 1px solid #cdd9e3; border-radius: 10px; padding: .6rem .7rem; min-height: 240px; }
.panel-title { font-size: .78rem; font-weight: 700; text-transform: uppercase; letter-spacing: .06em; color: #5a7088; margin-bottom: .5rem; }
.contact-list { list-style: none; margin: 0; padding: 0; }
.contact-list li { font-size: .88rem; padding: .28rem .45rem; border-radius: 6px; margin-bottom: 3px; background: #dce4ec; color: #1d3557; transition: background .25s, color .25s; }
.contact-list li.hit { background: #0a7d33; color: #fff; font-weight: 600; }
.contact-list li.miss { opacity: .4; }
.result-panel { background: #e6f4ec; border-color: #89c4a3; }
.contact-list.result li { background: #0a7d33; color: #fff; font-weight: 600; }
.contact-list.result li.empty { background: transparent; color: #888; font-style: italic; }
.status { font-size: .85rem; font-weight: 600; color: #5a7088; margin-top: .6rem; min-height: 1.3em; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557; background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Private Set Intersection simulation.
    // In a real PSI protocol (e.g. Diffie-Hellman blinding), neither party sends
    // plaintext items — each side blinds its set with a secret exponent and only
    // the double-blinded values are compared. Here we simulate the *outcome*:
    // both sides learn only the intersection; neither learns the other's full list.
    // The "protocol steps" log shows the cryptographic round-trips without
    // revealing either party's private data.

const ALL_CONTACTS = [
  'Alice Kim', 'Bob Leal', 'Carol Ng', 'David Obi', 'Eva Soto',
  'Felix Wu', 'Grace Park', 'Hana Müller', 'Ivan Cruz', 'Julia Bose',
  'Kai Ramos', 'Lena Diaz', 'Marco Voss', 'Nina Chen', 'Omar Farouk'
];

// Build two sets by randomly sampling from ALL_CONTACTS.
function sample(arr, n) {
  const a = arr.slice().sort(() => Math.random() - .5);
  return a.slice(0, n);
}

let aliceSet, serverSet;

function buildSets() {
  aliceSet  = sample(ALL_CONTACTS, 7);
  // Server overlaps ~3-4 contacts with Alice
  const shared = sample(aliceSet, Math.floor(Math.random() * 3) + 2);
  const extra  = sample(ALL_CONTACTS.filter(c => !aliceSet.includes(c)), 4);
  serverSet = [...shared, ...extra].sort(() => Math.random() - .5);
}

// The actual intersection — this is what a real PSI protocol computes.
function computeIntersection(a, b) {
  const bSet = new Set(b);
  return a.filter(x => bSet.has(x));
}

function renderList(id, items, highlightSet, ran) {
  const ul = document.getElementById(id);
  ul.innerHTML = '';
  items.forEach(name => {
    const li = document.createElement('li');
    li.textContent = name;
    if (ran) li.className = highlightSet.has(name) ? 'hit' : 'miss';
    ul.appendChild(li);
  });
}

function renderResult(intersection) {
  const ul = document.getElementById('result-list');
  ul.innerHTML = '';
  if (!intersection.length) {
    const li = document.createElement('li');
    li.className = 'empty'; li.textContent = 'No common contacts.';
    ul.appendChild(li);
  } else {
    intersection.forEach(name => {
      const li = document.createElement('li');
      li.textContent = name;
      ul.appendChild(li);
    });
  }
}

function render(ran) {
  const intersection = computeIntersection(aliceSet, serverSet);
  const iSet = new Set(intersection);
  renderList('alice-list',  aliceSet,  iSet, ran);
  renderList('server-list', serverSet, iSet, ran);
  if (ran) {
    renderResult(intersection);
    const steps = aliceSet.length + serverSet.length + 2; // simulated round-trips
    document.getElementById('status').textContent =
      fmt(intersection.length === 1 ? '1 common contact found. Protocol used %steps% blinded comparisons — no raw names exchanged.' : '%n% common contacts found. Protocol used %steps% blinded comparisons — no raw names exchanged.', { n: intersection.length, steps: steps });
    console.log('PSI intersection:', intersection.join(', '));
    console.log('Alice set size:', aliceSet.length, '| Server set size:', serverSet.length);
  } else {
    document.getElementById('result-list').innerHTML = '';
    document.getElementById('status').textContent = 'Press Run PSI to start.';
  }
}

document.getElementById('run').addEventListener('click', () => render(true));
document.getElementById('shuffle').addEventListener('click', () => { buildSets(); render(false); });

buildSets();
render(false);
Result
Console

Notice what each side learns: Alice discovers which of her contacts are already on the service. The server learns nothing about Alice's contacts that aren't registered. That asymmetry — full intersection, zero leakage — is what PSI guarantees. Press Shuffle contacts to try different lists and see how the intersection changes.

The Real Complexity

The naive approach — Alice sends her list to the server, the server checks and replies — works, but it hands Alice's data to the server unconditionally. PSI avoids this with elegant cryptographic machinery:

  • Hash-then-compare is the simplest idea: both sides hash their items and compare hashes. But hashed phone numbers are easy to brute-force; an adversary who gets the hashes can try all possible numbers in minutes. This approach is not secure for small input spaces.
  • Diffie-Hellman blinding (Meadows, 1986; Huberman, Franklin & Hogg, 1999): Alice blinds each element with a secret exponent α\alpha, sends the blinded values to the server. The server blinds them again with its exponent β\beta and returns them, then sends its own database blinded by β\beta. Alice blinds those with α\alpha. Both sides end up with H(x)αβH(x)^{\alpha\beta} for each element xx — identical for shared items, random-looking otherwise. No exponent is ever revealed.
  • Oblivious Transfer (OT) extensions (Ishai et al., 2003; Pinkas et al., 2018): OT lets one party send nn messages so the receiver gets exactly one without the sender learning which. Repeated cleverly, OT can drive a PSI that leaks nothing beyond the intersection itself and runs in near-linear time in the set sizes.
  • Garbled circuits encode the entire comparison as an encrypted Boolean circuit. They are fully general but expensive; used when the function is more complex than a plain intersection.

The status: PSI is a solved, practical problem. Google and Apple use variants of it for contact discovery and password-breach checking. The open research questions are about performance at scale and circuit-PSI — returning not just which elements match but also associated data, without revealing which specific records matched.

Related to the ideas behind oblivious transfer and the broader landscape of P vs NP — PSI sits firmly in polynomial time, which is exactly why it can be deployed at phone-book scale.

Where It Matters

PSI has crossed from theory into production across several industries:

  • Contact discovery: WhatsApp, Signal, and iMessage all use PSI-style protocols to find which of your contacts are already on the platform without uploading your full address book in plaintext.
  • Password-breach checking: Google's Password Checkup and Have I Been Pwned use a variant of PSI so your browser can ask "is this password in a breach database?" without sending the actual password to the server.
  • Privacy-preserving ad attribution: two companies (an advertiser and a publisher) can jointly compute which users converted without either side learning the other's full user list — a key building block for cookieless advertising.
  • Genomics and medical records: hospitals can find shared patients across clinical trials or check drug interactions across databases without exposing individual records.
  • Fraud detection: two banks can detect overlapping fraudulent accounts without sharing their customer data with each other.

Whenever two organizations need to collaborate on data without trusting each other, PSI is usually the right first primitive to reach for.

Conclusion

Private Set Intersection answers a question that sounds impossible at first hearing: can two parties find out what they have in common without ever showing each other their lists? The answer, it turns out, is yes — and the protocols that achieve it are fast enough to run on your phone every time you install a new app.

PSI is a reminder that privacy and utility are not always in conflict. Cryptography can sometimes give you exactly the output you need while provably hiding everything else. The next time an app magically knows which of your friends are already there, you are looking at PSI in action — not a privacy violation, but a carefully engineered absence of one.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/private-set-intersection/Content licensed under CC BY-NC 4.0.