Oblivious Transfer: The 1-of-2 Primitive That Powers MPC

The problem: choosing without revealing the choice

Imagine two mutually distrusting parties. A sender has two messages, m0 and m1. A receiver has a private choice bit b and wants m_b. The seemingly contradictory requirements are:

• Receiver privacy: the sender must not learn b (which message was taken).
• Sender privacy: the receiver must learn only m_b and gain zero information about m_{1-b}.

No trusted third party is allowed. This is the definition of 1-out-of-2 oblivious transfer. It sounds paradoxical because a naive solution — send both messages — leaks m_{1-b}, while asking the receiver "which do you want?" leaks b.

Rabin's original 1981 formulation was subtly different: an erasure channel where the receiver gets the single message with probability 1/2 and the sender never learns whether it arrived. Crépeau proved in 1987 that Rabin OT and 1-of-2 OT are equivalent. The 1-of-2 form is the one that plugs directly into higher protocols, which is why it became the standard.

How it works: the Chou-Orlandi simplest OT, step by step

The cleanest concrete construction is the Chou-Orlandi (2015) "simplest OT", secure under Computational Diffie-Hellman in the random-oracle model. Work in a group of prime order q with generator G and a hash H.

Setup: sender picks secret a, sends A = a*G to receiver.

Receiver (choice bit b):
  pick random r
  if b == 0:  B = r*G
  if b == 1:  B = A + r*G
  send B
  compute k_R = H( r*A )        // = H(a*r*G)

Sender:
  k0 = H( a*B )                 // = H(a*r*G) when b=0
  k1 = H( a*(B - A) )           // = H(a*r*G) when b=1
  send e0 = Enc(k0, m0), e1 = Enc(k1, m1)

Receiver: decrypt e_b with k_R -> m_b

Why it works: the receiver can derive only one of {k0, k1} because computing the other would require the discrete log of A (i.e., a). The sender computes both keys but cannot tell which B encodes, because B is uniformly random in both cases — that hides b perfectly.

Complexity and a worked key-agreement trace

Base OT cost. Chou-Orlandi needs one setup message (A) plus, per OT instance, a few group exponentiations: the sender computes 2 scalar mults for k0/k1 and 1 encryption; the receiver does ~2 scalar mults. That is O(1) public-key operations per OT and 2 rounds of communication. Public-key operations are expensive (microseconds each), so doing millions of them naively is the bottleneck.

OT extension changes the asymptotics. The IKNP extension (2003) performs only κ base OTs (κ = security parameter, e.g. 128), then produces an unbounded number of extended OTs using just ~2 hash evaluations each. So m OTs cost O(κ) public-key ops + O(m) symmetric ops — effectively amortized O(1) symmetric-key work per OT.

Trace (b = 1):

a = 7          A = 7G
r = 4, b=1  -> B = A + 4G = 11G
sender: k0 = H(7*11G)=H(77G),  k1 = H(7*(11G-7G))=H(7*4G)=H(28G)
receiver: k_R = H(4*A)=H(4*7G)=H(28G)  == k1  ✓ (m1 recovered)
receiver cannot form H(77G) without discrete-log of A.

Where it's used in real systems

OT is invisible to end users but sits under a growing stack of privacy technology:

• Garbled circuits (Yao): the evaluator uses one OT per input wire to fetch the garbled label for its private input bit without revealing that bit. Every secure two-party computation over Boolean circuits runs OT at the input layer.
• GMW protocol: multiplication gates over secret shares are evaluated with OT, making OT the arithmetic engine of the GMW MPC framework.
• Private Set Intersection (PSI): contact-discovery and ad-conversion measurement systems use OT-based PSI so two parties learn only their shared elements.
• Threshold signing & key management: MPC wallets (Fireblocks, Coinbase-style custody) use OT-based multiplication for ECDSA/threshold signatures.
• Private ML inference: frameworks such as CrypTen, ABY/ABY3, and secure-inference systems use OT for the nonlinear (ReLU, comparison) layers.

Modern deployments rely on silent OT / VOLE (Boyle et al., 2019+) to generate correlated OTs with near-zero communication, pushing OT into practical large-scale MPC.

Compared to its cousins: the tradeoff

OT is often confused with adjacent primitives; the distinctions are concrete.

• vs. Private Information Retrieval (PIR): PIR hides the receiver's index into a database but does not protect the unqueried records — the receiver may learn more. OT enforces both directions (sender privacy too). PIR optimizes for sublinear communication over huge databases; OT is a fixed 1-of-n unit.
• vs. Homomorphic encryption (FHE): FHE lets one party compute on another's ciphertext non-interactively but with heavy per-gate cost. OT is interactive and round-heavy but far cheaper per operation; MPC-via-OT usually beats FHE on wall-clock for circuits of moderate depth.
• vs. plain public-key encryption: PKE moves a message to a known recipient. OT adds the oblivious choice — the sender doesn't know which of two payloads was delivered.

The fundamental tradeoff: OT cannot be built from one-way functions alone (Impagliazzo-Rudich 1989, black-box separation) — it requires public-key-strength assumptions. You buy MPC-completeness at the price of number-theoretic hardness.

Pitfalls, failure modes, and why it matters

Malicious vs. semi-honest security. Basic protocols like plain IKNP are semi-honest secure — a cheating receiver who deviates from the protocol can break sender privacy. Production systems need actively-secure OT extension (Keller-Orsini-Scholl 2015) with consistency checks; forgetting this is a classic real-world break.

Selective-failure attacks. A malicious sender can encode m_{1-b} so that decryption failure reveals b — leaking the receiver's choice. Correct constructions must make both branches indistinguishable regardless of b.

• Correlation-robust hash: IKNP's security rests on the hash being correlation-robust; using a plain PRG or a broken hash silently voids the guarantee.
• Nonce/randomness reuse: reusing the receiver's r or the sender's a across instances collapses privacy — the same failure class as nonce reuse in ECDSA.
• Quantum: DDH/CDH-based OT falls to Shor's algorithm; post-quantum OT uses LWE/isogeny/code-based assumptions.

Why it matters: Kilian (1988) proved OT is complete for secure computation — with OT and a one-way function you can securely evaluate any function. That single result makes OT the load-bearing primitive of the entire MPC field.

OT variants and constructions: cost, assumptions, and where each fits

Construction / variant	Cost per OT	Assumption	Notes
Rabin OT (1981)	1 RSA op	RSA / factoring	Erasure channel: receiver gets message w.p. 1/2; equivalent to 1-of-2 OT
EGL 1-of-2 OT (1985)	O(1) public-key ops	Trapdoor permutation	Canonical form; receiver picks 1 of 2 messages
Chou-Orlandi 'simplest OT' (2015)	~3 exponentiations	CDH / gap-DH in ROM	Base-OT of choice; 2 rounds, very few group ops
IKNP OT extension (2003)	~2 hash evals (amortized)	Correlation-robust hash + κ base OTs	Turns κ base OTs into millions; symmetric-key speed
1-of-n OT	O(n) or O(log n) comm.	Same as underlying OT	Generalizes 1-of-2; used in PIR-style lookups
Correlated OT (COT)	~1 hash (amortized)	IKNP-style	Outputs correlated pairs; backbone of modern silent-OT/VOLE