Introduction

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∪BA \cup B while keeping AA and BB 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.

Try It

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.

<!-- Private Set Union demo: two parties compute A ∪ B without revealing their private elements. -->
<div class="parties">
  <div class="party" id="alice-panel">
    <div class="party-label">Alice’s private set</div>
    <div class="party-hint">Click items to toggle. These are Alice’s private elements.</div>
    <div class="items" id="alice-items"></div>
  </div>
  <div class="party" id="bob-panel">
    <div class="party-label">Bob’s private set</div>
    <div class="party-hint">Click items to toggle. These are Bob’s private elements.</div>
    <div class="items" id="bob-items"></div>
  </div>
</div>
<div class="btns">
  <button id="run" type="button">Run protocol</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>
<div class="status" id="status"></div>
<div class="result-area" id="result-area" style="display:none">
  <div class="result-label">Union result (A ∪ B)</div>
  <div class="result-items" id="result-items"></div>
  <div class="privacy-note" id="privacy-note"></div>
</div>

/* Layout and color scheme for the PSU demo. */
* { 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; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Shared universe of possible items (both parties know this label space).
const UNIVERSE = ['A','B','C','D','E','F','G','H'];
// Default private sets: Alice={A,B,C,D}, Bob={C,D,E,F}.
const aliceSet = new Set(['A','B','C','D']);
const bobSet   = new Set(['C','D','E','F']);

function renderParty(containerId, universe, activeSet, cssOff, cssOn) {
  // Render one party’s item toggles.
  const el = document.getElementById(containerId);
  el.innerHTML = '';
  for (const item of universe) {
    const d = document.createElement('span');
    d.className = 'item ' + (activeSet.has(item) ? cssOn : cssOff);
    d.textContent = item;
    d.addEventListener('click', () => {
      activeSet.has(item) ? activeSet.delete(item) : activeSet.add(item);
      renderParty(containerId, universe, activeSet, cssOff, cssOn);
      document.getElementById('result-area').style.display = 'none';
      document.getElementById('status').textContent = '';
    });
    el.appendChild(d);
  }
}

function runProtocol() {
  // Simulate the PSU protocol: compute union, reveal it, but annotate what was private.
  if (aliceSet.size === 0 && bobSet.size === 0) {
    const s = document.getElementById('status');
    s.textContent = 'Select at least one item in a set before running.'; s.className = 'status err'; return;
  }
  document.getElementById('status').textContent = '';
  const union = new Set([...aliceSet, ...bobSet]);
  const ri = document.getElementById('result-items');
  ri.innerHTML = '';
  for (const item of UNIVERSE) {
    if (!union.has(item)) continue;
    const d = document.createElement('span');
    const inA = aliceSet.has(item), inB = bobSet.has(item);
    d.className = 'result-item ' + (inA && inB ? 'both' : inA ? 'alice-only' : 'bob-only');
    d.textContent = item;
    ri.appendChild(d);
  }
  // Count items each party held exclusively (the other party did not know these before).
  const alicePrivate = [...aliceSet].filter(x => !bobSet.has(x)).length;
  const bobPrivate   = [...bobSet].filter(x => !aliceSet.has(x)).length;
  document.getElementById('privacy-note').innerHTML =
    i18nFmt('Alice has %ap% item(s) not in Bob’s set; Bob has %bp% item(s) not in Alice’s set. Each party learns only which of its private items appear in the union — nothing else about the other’s set.', { ap: alicePrivate, bp: bobPrivate }) +
    '<div class="legend">' +
    '<span><span class="legend-dot" style="background:#2a7d4a"></span>In both sets</span>' +
    '<span><span class="legend-dot" style="background:#1d3557"></span>Alice only</span>' +
    '<span><span class="legend-dot" style="background:#457b9d"></span>Bob only</span>' +
    '</div>';
  document.getElementById('result-area').style.display = 'block';
}

function resetAll() {
  // Restore default sets and hide the result panel.
  aliceSet.clear(); ['A','B','C','D'].forEach(x => aliceSet.add(x));
  bobSet.clear();   ['C','D','E','F'].forEach(x => bobSet.add(x));
  renderParty('alice-items', UNIVERSE, aliceSet, 'alice-off', 'alice-on');
  renderParty('bob-items',   UNIVERSE, bobSet,   'bob-off',   'bob-on');
  document.getElementById('result-area').style.display = 'none';
  document.getElementById('status').textContent = '';
}

document.getElementById('run').addEventListener('click', runProtocol);
document.getElementById('reset').addEventListener('click', resetAll);
renderParty('alice-items', UNIVERSE, aliceSet, 'alice-off', 'alice-on');
renderParty('bob-items',   UNIVERSE, bobSet,   'bob-off',   'bob-on');
Result
Console

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.

The Real Complexity

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)⋅λ)O((m + n) \cdot \lambda) where mm and nn 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×3\times–5×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∩BA \cap B, while PSU reveals A∪BA \cup B, which leaks slightly more (each party infers which elements the other contributed).

Where It Matters

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.

Conclusion

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.

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-union/Content licensed under CC BY-NC 4.0.