Private Set Union

Imagine two hospitals, each holding a list of patients. They want to know the full combined list — but privacy laws forbid them from swapping records. Is there any way to get the union without revealing who belongs only to one hospital?

The answer is yes, and the field that studies this is called secure multiparty computation (MPC). The specific problem — computing $A \cup B$ while keeping $A$ and $B$ private — is Private Set Union (PSU).

PSU sits in a remarkable niche: the result itself is public (or shared), yet neither party learns anything about the other party's private items beyond what the union already reveals. Alice learns Bob's elements only when they appear in the final union; Bob learns Alice's only the same way. Everything else stays hidden.

The protocol is not magic — it rests on concrete mathematical tools: oblivious transfer, pseudorandom functions, and homomorphic hashing. Together they let two mutually distrusting parties merge their lists honestly, with a cryptographic guarantee that no party can cheat and learn more than allowed.

Two parties — Alice and Bob — each hold a private set. Click items to toggle them into each party's set, then run the protocol. The union forms, but neither side learns which items were exclusively in the other's private set until they appear in the result.

<!-- {{c_intro}} -->
<div class="parties">
  <div class="party" id="alice-panel">
    <div class="party-label">{{label_alice}}</div>
    <div class="party-hint">{{hint_alice}}</div>
    <div class="items" id="alice-items"></div>
  </div>
  <div class="party" id="bob-panel">
    <div class="party-label">{{label_bob}}</div>
    <div class="party-hint">{{hint_bob}}</div>
    <div class="items" id="bob-items"></div>
  </div>
</div>
<div class="btns">
  <button id="run" type="button">{{btn_run}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div class="status" id="status"></div>
<div class="result-area" id="result-area" style="display:none">
  <div class="result-label">{{label_result}}</div>
  <div class="result-items" id="result-items"></div>
  <div class="privacy-note" id="privacy-note"></div>
</div>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.parties { display: flex; gap: 1rem; margin-bottom: .8rem; flex-wrap: wrap; }
.party { flex: 1 1 200px; background: #f0f4f8; border-radius: 10px; padding: .8rem 1rem; }
#alice-panel { border-top: 3px solid #1d3557; }
#bob-panel { border-top: 3px solid #457b9d; }
.party-label { font-weight: 700; font-size: 1rem; margin-bottom: .25rem; }
.party-hint { font-size: .82rem; color: #555; margin-bottom: .5rem; }
.items { display: flex; flex-wrap: wrap; gap: .4rem; }
.item { padding: .3rem .65rem; border-radius: 20px; font-size: .88rem; font-weight: 600;
        cursor: pointer; border: 2px solid transparent; transition: all .12s; user-select: none; }
.item.alice-off { background: #dce8f5; color: #1d3557; border-color: #aac4e0; }
.item.alice-on  { background: #1d3557; color: #fff; border-color: #1d3557; }
.item.bob-off   { background: #d6eaf6; color: #457b9d; border-color: #90c0da; }
.item.bob-on    { background: #457b9d; color: #fff; border-color: #457b9d; }
.item:hover { opacity: .82; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .6rem; }
button { font: 600 14px system-ui; padding: .45rem .9rem; border-radius: 8px; cursor: pointer;
         border: 1px solid #1d3557; background: #1d3557; color: #fff; }
button.ghost { background: #fff; color: #1d3557; }
.status { font-size: .95rem; font-weight: 600; min-height: 1.4em; margin-bottom: .4rem; }
.status.err { color: #c92f3c; }
.result-area { background: #eafaea; border-radius: 10px; padding: .8rem 1rem; border-top: 3px solid #2a9d4a; }
.result-label { font-weight: 700; margin-bottom: .4rem; color: #1a6630; }
.result-items { display: flex; flex-wrap: wrap; gap: .4rem; margin-bottom: .5rem; }
.result-item { padding: .3rem .65rem; border-radius: 20px; font-size: .88rem; font-weight: 600; color: #fff; }
.both  { background: #2a7d4a; }
.alice-only { background: #1d3557; }
.bob-only   { background: #457b9d; }
.privacy-note { font-size: .8rem; color: #444; line-height: 1.45; }
.legend { display: flex; gap: .8rem; flex-wrap: wrap; font-size: .78rem; margin-top: .5rem; }
.legend-dot { width: 10px; height: 10px; border-radius: 50%; display: inline-block; margin-right: 3px; }

// Code not found

Notice: when an element belongs to both parties, both already knew it existed. The only new information either learns is what items the other contributed to the union — and that is precisely what the real protocol allows. Items that are in neither set remain completely hidden.

How hard is it to compute a private union, really?

• Naive sharing is easy but wrong. Alice sends her set to Bob; Bob takes the union and sends it back. Result correct, privacy destroyed — Bob sees everything Alice owns.
• A correct protocol must be oblivious. No party should learn more than what the final union directly reveals. This is formalized by simulation-based security: a protocol is secure if everything a party sees during the run could have been generated by a simulator that only knows the party's own input and the output.
• The core building block is Oblivious Transfer (OT). In a 1-out-of-2 OT, a sender holds two messages; the receiver picks one without the sender learning which, and without the receiver learning the other. Stacking many OTs allows Bob to "look up" each of Alice's elements in an oblivious way.
• Pseudorandom functions (PRFs) map private items to random-looking values. By comparing PRF outputs instead of raw items, neither party reveals the plaintext during the protocol.
• Communication cost scales as $O((m + n) \cdot \lambda)$ where $m$ and $n$ are the set sizes and $\lambda$ is the security parameter (typically 128 bits). Modern PSU protocols (Kolesnikov et al., 2019; Jia et al., 2022) achieve near-linear time with only a constant number of OT rounds.
• Security models: the semi-honest model assumes both parties follow the protocol but try to infer extra information from transcripts. The stronger malicious model allows arbitrary cheating; achieving it typically costs a $3\times$–$5\times$ overhead.

PSU is closely related to Private Set Intersection (PSI) — both are instances of Secure Function Evaluation, where the function being computed is kept from each party. The difference is the output: PSI reveals $A \cap B$, while PSU reveals $A \cup B$, which leaks slightly more (each party infers which elements the other contributed).

Any setting where two or more organizations want to combine data without exposing private records is a candidate for PSU:

• Healthcare: hospitals merge patient lists to coordinate care for shared patients. Neither hospital learns who is not shared — only the joint list is revealed.
• Fraud detection: banks pool blacklists of suspicious accounts without exposing their full fraud databases to competitors.
• Contact tracing: public health agencies combine exposure logs from different regions while preserving individual privacy.
• Supply-chain integrity: manufacturers check whether their supplier lists overlap with a sanctions list, without revealing the full supplier roster.
• Ad-tech and data clean-rooms: advertisers and publishers reconcile user identifiers to measure campaign reach across platforms, with no raw ID exchange.

The pattern is always the same: two parties each hold a set, the union is useful to both, but exposing either raw set is unacceptable. PSU is the tool that breaks this deadlock.

PSU is a sibling of Private Set Intersection, and both sit inside the broader landscape of secure multiparty computation — the field that asks which functions can be computed jointly without trust.

Private Set Union is one of those results that seems impossible until you understand it: two parties, no trust, yet a correct union — with a mathematical proof that no extra information leaks.

The protocol is not just a theoretical curiosity. Modern PSU schemes run in time linear in the set sizes, make only a constant number of communication rounds, and have been implemented in real systems protecting real data. The cryptographic tools underneath — oblivious transfer, pseudorandom functions, simulation-based security — are the same workhorses that power private set intersection, private information retrieval, and much of modern applied cryptography.

The next time you wonder whether two organizations could collaborate without trusting each other, the answer may well be yes — because mathematicians and cryptographers already solved the hard part.