Introduction

Imagine a sender holding two sealed envelopes — Message 0 and Message 1 — and a receiver who wants exactly one of them. The catch: the receiver must not learn the contents of the envelope they did not choose, and the sender must not learn which envelope the receiver took.

Both requirements sound contradictory. How can anyone hand over a message without knowing who is receiving it? This is the paradox at the heart of oblivious transfer (OT), a two-party cryptographic protocol with an almost magical guarantee.

Michael O. Rabin introduced the first version in 1981: a sender transmits a message that the receiver gets with probability one-half, and the sender never knows if delivery succeeded. Shimon Even, Oded Goldreich and Abraham Lempel sharpened this into the 1-out-of-2 form (1985) that is standard today: the receiver picks bit b∈{0,1}b \in \{0, 1\} and learns mbm_b precisely — nothing about m1−bm_{1-b}, and the sender learns nothing about bb.

What makes OT remarkable is not just its elegance. In 1988, Joe Kilian proved that oblivious transfer is complete for secure computation: any function two parties want to compute jointly without revealing their private inputs can be built from OT alone. It is the hydrogen of cryptographic primitives — everything else is assembled from it.

Try It

Here is a simplified simulation of 1-out-of-2 oblivious transfer. The sender has hidden two secret messages. You are the receiver — choose which one you want. You will see exactly that message; the sender's log will show only that some transfer happened, never your choice.

<p class="hint">The <b>Sender</b> holds two secret messages. You are the <b>Receiver</b> — pick which one you want. You learn exactly that message; the sender's log stays blind to your choice. This two-way privacy is the essence of 1-out-of-2 OT.</p>
<div class="panels">
  <div class="panel sender-panel">
    <div class="panel-title">Sender</div>
    <div class="msg-row">
      <span class="msg-label">Message 0:</span>
      <span class="msg-box hidden" id="msg0-display">?</span>
    </div>
    <div class="msg-row">
      <span class="msg-label">Message 1:</span>
      <span class="msg-box hidden" id="msg1-display">?</span>
    </div>
    <div class="sender-log" id="sender-log">Waiting for receiver…</div>
  </div>
  <div class="arrow-col">
    <div class="arrow" id="arrow">→</div>
    <div class="arrow-label" id="arrow-label">no transfer yet</div>
  </div>
  <div class="panel receiver-panel">
    <div class="panel-title">Receiver</div>
    <div class="choice-row">
      <span class="msg-label">Choose:</span>
      <button class="choice-btn" id="btn0" type="button">Message 0</button>
      <button class="choice-btn" id="btn1" type="button">Message 1</button>
    </div>
    <div class="received-box" id="received-box">
      <span class="received-label">Received:</span>
      <span class="received-value" id="received-value">—</span>
    </div>
  </div>
</div>
<div class="btns">
  <button id="reveal-btn" type="button" class="ghost">Reveal both (break OT)</button>
  <button id="reset-btn" type="button" class="ghost">Reset</button>
</div>
<div class="reveal-section" id="reveal-section" style="display:none">
  <b>Sender's actual secrets:</b>
  <span id="reveal0"></span>
  <span id="reveal1"></span>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .8rem; line-height: 1.45; }
.panels { display: flex; align-items: center; gap: .5rem; flex-wrap: wrap; }
.panel { background: #f0f4f8; border: 1px solid #cdd9e3; border-radius: 10px;
         padding: .8rem 1rem; min-width: 170px; flex: 1; }
.sender-panel { border-color: #457b9d; }
.receiver-panel { border-color: #2a9d8f; }
.panel-title { font: 700 13px system-ui; letter-spacing: .04em; text-transform: uppercase;
               margin-bottom: .5rem; color: #1d3557; }
.msg-row { display: flex; align-items: center; gap: .4rem; margin-bottom: .35rem; }
.msg-label { font-size: .85rem; color: #555; min-width: 75px; }
.msg-box { background: #c9ccd1; border-radius: 6px; padding: .2rem .5rem;
           font: 600 13px ui-monospace, monospace; color: #333; min-width: 70px; text-align: center; }
.msg-box.hidden { color: transparent; background: #c9ccd1; border: 1px dashed #adb1b8; }
.sender-log { margin-top: .5rem; font-size: .82rem; background: #e0e8f0;
              border-radius: 6px; padding: .35rem .5rem; color: #333; min-height: 2.2em; }
.arrow-col { display: flex; flex-direction: column; align-items: center; gap: .15rem;
             flex: 0 0 auto; padding: 0 .2rem; }
.arrow { font-size: 2rem; color: #457b9d; transition: color .3s; }
.arrow.active { color: #e63946; }
.arrow-label { font-size: .72rem; color: #888; text-align: center; max-width: 70px; }
.choice-row { display: flex; align-items: center; gap: .4rem; flex-wrap: wrap; margin-bottom: .5rem; }
.choice-btn { font: 600 13px system-ui; padding: .3rem .65rem; border: 1px solid #2a9d8f;
              background: #fff; color: #2a9d8f; border-radius: 7px; cursor: pointer;
              transition: all .15s; }
.choice-btn:hover { background: #2a9d8f; color: #fff; }
.choice-btn.selected { background: #2a9d8f; color: #fff; }
.choice-btn:disabled { opacity: .4; cursor: default; }
.received-box { background: #e0f5f2; border: 1px solid #2a9d8f; border-radius: 8px;
                padding: .5rem .7rem; display: flex; align-items: center; gap: .4rem; }
.received-label { font-size: .82rem; color: #2a9d8f; font-weight: 700; }
.received-value { font: 700 15px ui-monospace, monospace; color: #1d3557; word-break: break-all; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-top: .8rem; }
button { font: 600 13px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.reveal-section { margin-top: .6rem; background: #fff3cd; border: 1px solid #e0a800;
                  border-radius: 8px; padding: .45rem .7rem; font-size: .85rem; }
.reveal-section span { margin-left: .5rem; font: 600 13px ui-monospace, monospace; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// 1-out-of-2 Oblivious Transfer simulation.
// The SENDER holds two messages: m[0] and m[1].
// The RECEIVER chooses bit b in {0,1} and learns m[b] ONLY.
// The SENDER learns nothing about b.
//
// In a real OT (e.g., using RSA trapdoor) the blinding is cryptographic.
// Here we simulate the *interface* and *information flow* faithfully:

const MESSAGES = [
  'The quick brown fox',
  'Pack my box with five'
];

let choiceMade = false;
let chosenBit = -1;

function senderTransfer(bit) {
  // Sender API: receives only the ENCRYPTED selection (simulated here as
  // "some transfer happened"). Returns m[bit] to the receiver.
  // In this simulation sender never inspects `bit`.
  logSender('Transfer executed. Choice: [HIDDEN]');
  return MESSAGES[bit];
}

function logSender(msg) {
  document.getElementById('sender-log').textContent = msg;
}

function doChoice(bit) {
  if (choiceMade) return;
  choiceMade = true;
  chosenBit = bit;

  document.getElementById('btn0').disabled = true;
  document.getElementById('btn1').disabled = true;
  document.getElementById('btn' + bit).classList.add('selected');

  const arrow = document.getElementById('arrow');
  const arrowLabel = document.getElementById('arrow-label');
  arrow.classList.add('active');
  arrowLabel.textContent = 'transferring…';

  // Simulate a short delay to make the transfer feel real
  setTimeout(() => {
    const received = senderTransfer(bit);
    document.getElementById('received-value').textContent = received;
    arrowLabel.textContent = 'transfer done';
    arrow.classList.remove('active');

    // Verify: sender log must not mention the bit
    console.assert(
      !document.getElementById('sender-log').textContent.includes(String(bit)),
      'VIOLATION: sender log reveals the choice bit!'
    );
    console.log(fmt('OT complete. Receiver got m[%bit%]. Sender log:', { bit: bit }), document.getElementById('sender-log').textContent);
  }, 600);
}

function revealBoth() {
  const sec = document.getElementById('reveal-section');
  sec.style.display = 'block';
  document.getElementById('reveal0').textContent = fmt('M0: "%v%"', { v: MESSAGES[0] });
  document.getElementById('reveal1').textContent = " " + fmt('| M1: "%v%"', { v: MESSAGES[1] });
}

function reset() {
  choiceMade = false;
  chosenBit = -1;
  ['btn0','btn1'].forEach(id => {
    const b = document.getElementById(id);
    b.disabled = false;
    b.classList.remove('selected');
  });
  document.getElementById('received-value').textContent = '—';
  document.getElementById('sender-log').textContent = 'Waiting for receiver…';
  document.getElementById('arrow').classList.remove('active');
  document.getElementById('arrow-label').textContent = 'no transfer yet';
  document.getElementById('reveal-section').style.display = 'none';
}

document.getElementById('btn0').addEventListener('click', () => doChoice(0));
document.getElementById('btn1').addEventListener('click', () => doChoice(1));
document.getElementById('reveal-btn').addEventListener('click', revealBoth);
document.getElementById('reset-btn').addEventListener('click', reset);

// Verify core OT property: receiver learns m[b], not m[1-b].
// Run this assertion in console to confirm correctness.
(function selfTest() {
  for (let b = 0; b <= 1; b++) {
    const result = MESSAGES[b];
    const other  = MESSAGES[1 - b];
    console.assert(result !== other, 'Messages must be distinct');
    console.assert(result === MESSAGES[b], fmt('OT delivers correct message for b=%b%', { b: b }));
  }
  console.log(fmt('OT self-test passed: m[0]="%v%", m[1]="%v2%"', { v: MESSAGES[0], v2: MESSAGES[1] }));
})();
Result
Console

Notice the asymmetry. The receiver sees the chosen message in full. The sender's log records only a transfer event — it is completely blind to which message you picked. This privacy in both directions simultaneously is what makes OT so powerful, and so non-trivial to construct from simpler assumptions.

The Real Complexity

Oblivious transfer occupies a unique position in complexity and cryptography.

  • Status: proven constructible (assuming standard cryptographic hardness). OT can be built from any trapdoor permutation (such as RSA) or from elliptic-curve Diffie-Hellman. The construction is not conjectured — it is a theorem, conditional on those hardness assumptions.
  • The Kilian completeness theorem (1988). Joe Kilian proved that OT is complete for two-party secure computation: any Boolean function can be computed by two mutually distrusting parties, each learning only the output, using OT as the only primitive. Later work (Ishai et al., 2003) extended this to multiparty computation as well.
  • OT extension. A key efficiency result: a small number of base OTs (using public-key cryptography) can be extended into millions of cheap symmetric-key OTs (Beaver, 1996; IKNP, 2003). This is why practical systems can afford OT at scale.
  • Relation to P vs NP. OT requires computational assumptions — it cannot be built from information-theoretic assumptions alone (two-party OT is impossible in the information-theoretic model). Its hardness is tied to the same one-way-function landscape that underlies all of modern cryptography.

The verdict: OT is not an open problem. It is a solved primitive whose existence follows from standard assumptions, whose universality is proven, and whose efficiency is well-understood. The open questions today are about making it faster and more quantum-resistant.

Where It Matters

Because OT is complete for secure computation, it appears — usually hidden inside larger protocols — wherever two parties need to compute jointly without trusting each other:

  • Garbled circuits: Yao's garbled-circuit protocol uses OT so that a receiver can obtain the wire labels for their private inputs without the garbler learning which labels were chosen. Every practical two-party computation inherits this OT step.
  • Private set intersection: two companies check which customers they have in common without either party exposing their full customer list. OT-based PSI protocols dominate in practice.
  • Private database queries: a client retrieves a record from a server's database without the server learning which record was retrieved — a direct application of 1-out-of-nn OT.
  • Secure voting and auctions: tallying encrypted votes or sealed bids without a trusted third party reduces to secure multiparty computation, which reduces to OT.
  • Machine learning on private data: federated learning and private inference protocols use OT extension to evaluate neural networks on encrypted inputs.

In each case, OT does the same job: it lets one party choose among the other's secrets while both privacy guarantees hold simultaneously.

Conclusion

Oblivious transfer encapsulates one of cryptography's deepest insights: privacy and computation are compatible. A sender can hand over exactly one of two secrets without ever knowing which one was taken — and from that single guarantee, all of secure multiparty computation follows.

Rabin's 1981 thought experiment, sharpened by Even, Goldreich and Lempel, and crowned by Kilian's 1988 completeness proof, gives us a clean ladder: assume a hard mathematical problem, construct OT, build every secure protocol on top. The next time you hear about private machine learning, secure voting, or contact-tracing without a privacy leak, look under the hood — somewhere in the protocol stack, oblivious transfer is doing the quiet work of keeping both sides honest.

Share this article

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

Comments

Loading comments...

https://www.kipuhub.com/en/article/oblivious-transfer/Content licensed under CC BY-NC 4.0.