Oblivious transfer — the universal 2PC primitive

Why this matters

If you have oblivious transfer, you have 2-party MPC. Every 2PC protocol in this course — garbled circuits, GMW, SPDZ — ultimately bottoms out in OT calls. A 1-of-2 OT lets a sender give two messages (m_0, m_1) to a receiver who picks one via a secret bit b, with the guarantee: sender learns nothing about b, receiver learns only m_b. It's simple to state and surprisingly non-trivial to build — and vast swathes of cryptographic engineering (OT extensions, silent OT, correlated OT) exist to make OT fast enough to be practical.

Demo

A simplified Diffie-Hellman–based OT protocol (Naor-Pinkas). Not constant-time, not production — illustrative. Production OT lives in libraries like libOTe and EMP-toolkit.

# Naor-Pinkas 1-of-2 OT over a toy DLP group.
# WARNING: educational only. Uses small parameters and no constant-time ops.
import secrets
from hashlib import sha256

# Small toy group: safe prime p = 2q+1, generator g of order q.
P = 170141183460469231731687303715884105727  # Mersenne; don't use in prod.
G = 5

def pow_mod(b: int, e: int, m: int) -> int: return pow(b, e, m)
def kdf(x: int) -> bytes: return sha256(str(x).encode()).digest()

def ot_send(m0: bytes, m1: bytes):
    # Sender picks a random c (serves as the "other" DH value).
    c = secrets.randbelow(P - 1) + 1
    return c

def ot_recv(c: int, b: int):
    # Receiver picks secret k, computes pk_b = g^k, pk_{1-b} = c / pk_b.
    k = secrets.randbelow(P - 1) + 1
    pk_b = pow_mod(G, k, P)
    pk_0, pk_1 = (pk_b, c * pow_mod(pk_b, P - 2, P) % P) if b == 0 else (c * pow_mod(pk_b, P - 2, P) % P, pk_b)
    return (pk_0, pk_1), k

def ot_send_encrypt(c: int, pk_0: int, pk_1: int, m0: bytes, m1: bytes):
    r = secrets.randbelow(P - 1) + 1
    g_r = pow_mod(G, r, P)
    k0 = kdf(pow_mod(pk_0, r, P))
    k1 = kdf(pow_mod(pk_1, r, P))
    e0 = bytes(a ^ b for a, b in zip(m0.ljust(32, b"\0"), k0))
    e1 = bytes(a ^ b for a, b in zip(m1.ljust(32, b"\0"), k1))
    return g_r, e0, e1

def ot_recv_decrypt(g_r: int, e_b: bytes, k: int) -> bytes:
    shared = pow_mod(g_r, k, P)
    key = kdf(shared)
    return bytes(a ^ b for a, b in zip(e_b, key))

# Run protocol.
m0, m1 = b"you chose zero", b"you chose one"
b = 1  # receiver's hidden choice
c = ot_send(m0, m1)
(pk_0, pk_1), k = ot_recv(c, b)
g_r, e0, e1 = ot_send_encrypt(c, pk_0, pk_1, m0, m1)
plaintext = ot_recv_decrypt(g_r, e1 if b == 1 else e0, k)
print(plaintext.rstrip(b"\0"))  # -> b'you chose one'
# Sender never learned b; receiver never learned m0.

Try it yourself

1. Run the Python OT with b=0 and b=1 separately. In both cases the sender's code is identical — the sender literally cannot tell from its local state which message was received. That asymmetric-information property is the whole point.
2. Count the number of exponentiations per OT: 2 for receiver, 3 for sender. For 128-bit security over a real group, one exp takes ~100μs. A single OT is ~500μs. A million OTs is 8+ minutes — that's the bandwidth/compute wall OT extensions fix (next task).
3. Trace what the sender sees across the three rounds and verify the sender's view is independent of b. Specifically: (pk_0, pk_1) is a uniformly distributed pair of group elements regardless of which side the receiver picked.
4. What breaks if the receiver cheats by picking both pk_0 and pk_1 as known-exponent values? The protocol would leak both messages — this is why Naor-Pinkas ties one of them to the sender's c via division.
5. Find the OT chapter in Evans-Kolesnikov-Rosulek and skim the security proof. Locate the simulator — what does it need to extract from the receiver to simulate honest behavior?

Prompt your AI

Use these three in order. Each builds on the one before.

1. Basics & terminology

Explain 1-of-2 oblivious transfer to someone who's familiar with Diffie-Hellman but has never heard of OT. What problem is being solved, and why is it called 'oblivious'?

2. Why it works (the mechanism)

Walk me through Naor-Pinkas OT step by step, naming what each party computes and what each party knows after each message. Prove informally that the sender cannot distinguish b=0 from b=1 and the receiver cannot decrypt m_{1-b}. Name the hardness assumption each claim rests on.

3. Advanced — application & what's next

A million OTs per session is routine in modern MPC. One Naor-Pinkas OT costs ~3 exponentiations. Given typical 2^30-cycle-per-exp cost, a million OTs would take minutes. Explain how OT extensions (IKNP, silent OT) break that wall — specifically, what sub-linear-in-the-number-of-OTs trick do they use, and at what security cost?

References

• Naor & Pinkas — Efficient Oblivious Transfer Protocols
• Ishai, Kilian, Nissim, Petrank — IKNP OT extensions
• swanky — Rust OT + OT-extension library