Private Set Intersection

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.

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">{{hint}}</p>
<div class="psi-layout">
  <div class="panel" id="alice-panel">
    <div class="panel-title">{{alice_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">{{status_initial}}</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">{{btn_run}}</button>
  <button id="shuffle" type="button" class="ghost">{{btn_shuffle}}</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; }

// Code not found

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 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)^{\alpha\beta}$ for each element $x$ — 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 $n$ 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.

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.

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.