Oblivious Transfer

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 \in \{0, 1\}$ and learns $m_b$ precisely — nothing about $m_{1-b}$, and the sender learns nothing about $b$.

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.

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">{{hint}}</p>
<div class="panels">
  <div class="panel sender-panel">
    <div class="panel-title">{{sender_title}}</div>
    <div class="msg-row">
      <span class="msg-label">{{msg0_label}}</span>
      <span class="msg-box hidden" id="msg0-display">?</span>
    </div>
    <div class="msg-row">
      <span class="msg-label">{{msg1_label}}</span>
      <span class="msg-box hidden" id="msg1-display">?</span>
    </div>
    <div class="sender-log" id="sender-log">{{waiting}}</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_title}}</div>
    <div class="choice-row">
      <span class="msg-label">{{choose_label}}</span>
      <button class="choice-btn" id="btn0" type="button">{{btn_msg0}}</button>
      <button class="choice-btn" id="btn1" type="button">{{btn_msg1}}</button>
    </div>
    <div class="received-box" id="received-box">
      <span class="received-label">{{received_label}}</span>
      <span class="received-value" id="received-value">—</span>
    </div>
  </div>
</div>
<div class="btns">
  <button id="reveal-btn" type="button" class="ghost">{{reveal_btn}}</button>
  <button id="reset-btn" type="button" class="ghost">{{reset_btn}}</button>
</div>
<div class="reveal-section" id="reveal-section" style="display:none">
  <b>{{secrets_heading}}</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; }

// Code not found

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.

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.

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-$n$ 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.

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.