12d-oblivious-transfer.ipynb

Kernel: SageMath 10.5

Notebook 12d: Oblivious Transfer

Module 12: Multi-Party Computation

---

Motivating Question. In Yao's garbled circuits, the evaluator (Bob) needs wire labels for his input bits, but the garbler (Alice) can't hand them over directly, because that would reveal both labels and thus the bit values. Can we design a protocol where Bob receives exactly one of two messages, Alice doesn't learn which one Bob chose, and Bob doesn't learn the other?

---

Prerequisites. You should be comfortable with:

• Discrete logarithms and Diffie-Hellman (Module 05)

• RSA encryption (Module 04)

• Garbled circuits (Notebook 12c)

Learning objectives. By the end of this notebook you will be able to:

1. Define the ideal functionality of 1-of-2 Oblivious Transfer.

2. Implement a DH-based OT protocol from scratch.

3. Explain both sender privacy and receiver privacy.

4. Connect OT to Yao's garbled circuits as the missing building block.

5. Understand how OT extension makes millions of OTs practical.

1. The OT Ideal Functionality

Bridge from Notebook 12c. In garbled circuits, Alice garbles the circuit and sends it to Bob along with her input labels. But Bob still needs labels for his input wires. If Alice sends both labels for a wire, Bob learns both bit values. If Bob tells Alice which label he wants, Alice learns Bob's input. Oblivious Transfer solves this dilemma.

1-of-2 Oblivious Transfer involves two parties:

Party	Holds	Learns
Sender	Two messages $m_0, m_1$	Nothing about $b$
Receiver	Choice bit $b \in \{0, 1\}$	Only $m_b$ (nothing about $m_{1-b}$)

With a trusted third party, this is trivial:

def ideal_ot(m0, m1, choice):
    """Ideal OT functionality, what a trusted third party would do."""
    # Third party receives m0, m1 from sender and b from receiver.
    # Hands m_b to receiver.  Tells sender nothing.
    return m0 if choice == 0 else m1

# Demonstrate
m0, m1 = 42, 99
print(f"Sender's messages: m0 = {m0}, m1 = {m1}")
print(f"Receiver (b=0) gets: {ideal_ot(m0, m1, 0)}")
print(f"Receiver (b=1) gets: {ideal_ot(m0, m1, 1)}")
print()
print("Goal: achieve this WITHOUT a trusted third party.")

Checkpoint 1. Make sure you can state the two security properties: (1) sender privacy, the receiver learns nothing about $m_{1-b}$; (2) receiver privacy, the sender learns nothing about $b$. Both must hold simultaneously.

2. Diffie-Hellman-Based OT

The key insight: in a Diffie-Hellman key exchange, two parties create a shared secret $g^{ab}$. We'll exploit this so the receiver can create a shared secret for one of two possible messages, but not both.

The Protocol

Public parameters: prime $p$, generator $g$ of $\mathbb{F}_p^*$.

Step	Who	Action
1	Sender	Pick random $a$, publish $A = g^a$
2	Receiver (bit $b$)	Pick random $r$. If $b=0$: send $B = g^r$. If $b=1$: send $B = A \cdot g^r$
3	Sender	Compute keys $k_0 = B^a$ and $k_1 = (B/A)^a$. Encrypt $e_i = m_i + k_i$
4	Receiver	Compute $k = A^r = g^{ar}$. Decrypt $m_b = e_b - k$

Why it works: Regardless of $b$, the receiver can compute $A^r = g^{ar}$.

• If $b = 0$: $k_0 = B^a = (g^r)^a = g^{ra} = A^r$ ✓

• If $b = 1$: $k_1 = (B/A)^a = (g^r)^a = g^{ra} = A^r$ ✓

The receiver's key always matches exactly one of $\{k_0, k_1\}$.

# Setup: same prime field as our secret sharing notebooks
p = 1009
F = GF(p)
g = F.multiplicative_generator()

print(f"Field: GF({p})")
print(f"Generator: g = {g}")
print(f"Order of g: {g.multiplicative_order()}")
print(f"\nNote: these parameters are tiny (for teaching). Real OT uses")
print(f"256-bit elliptic curve groups where DDH is hard.")

Step 1: Sender publishes $A = g^a$

# Step 1: Sender
a = ZZ.random_element(1, p - 1)
A = g^a

print(f"Sender's secret: a = {a}")
print(f"Sender publishes: A = g^{a} = {A}")

Step 2: Receiver's clever blinding trick

The receiver picks a random $r$ and sends either $B = g^r$ (if $b=0$) or $B = A \cdot g^r$ (if $b=1$). Since $r$ is uniformly random, both cases produce a uniformly random group element, the sender cannot distinguish them.

# Step 2: Receiver
choice = 1  # Bob wants m1
r = ZZ.random_element(1, p - 1)

if choice == 0:
    B = g^r
else:
    B = A * g^r    # = g^(a+r)

print(f"Receiver's choice: b = {choice}")
print(f"Receiver's random: r = {r}")
print(f"Receiver sends: B = {B}")
print(f"\nSender sees B = {B}")
print(f"Can the sender tell if b = 0 or b = 1?  No!")
print(f"B is uniformly random in both cases.")

Step 3: Sender computes both keys and encrypts

# Step 3: Sender computes two keys
k0 = B^a           # g^(ra)  if b=0,  g^(a^2 + ra)  if b=1
k1 = (B / A)^a     # g^(ra - a^2)  if b=0,  g^(ra)  if b=1

# Sender's messages
m0, m1 = 42, 99

# Encrypt by adding the key (mod p)
e0 = (m0 + int(k0)) % p
e1 = (m1 + int(k1)) % p

print(f"Sender's messages: m0 = {m0}, m1 = {m1}")
print(f"Keys: k0 = {k0}, k1 = {k1}")
print(f"Encrypted: e0 = {e0}, e1 = {e1}")
print(f"\nSender sends (e0, e1) to the receiver.")

Step 4: Receiver decrypts the chosen message

# Step 4: Receiver computes shared key and decrypts
k_recv = A^r   # = g^(ar) , always equals k_b

print(f"Receiver computes: A^r = {k_recv}")
print(f"This matches k{choice}: {k_recv == (k0 if choice == 0 else k1)}")
print()

# Decrypt the chosen message
e_chosen = e0 if choice == 0 else e1
m_received = (e_chosen - int(k_recv)) % p

expected = m0 if choice == 0 else m1
print(f"Receiver decrypts: m_{choice} = {m_received}")
print(f"Correct? {m_received == expected}")

Checkpoint 2. Trace through the case $b = 0$. Verify: $k_0 = B^a = (g^r)^a = g^{ra}$ and $A^r = (g^a)^r = g^{ar}$, so $k_0 = A^r$. Then verify $k_1 = (B/A)^a = (g^{r-a})^a = g^{ra - a^2} \neq A^r$ (the receiver can't compute this without knowing $a$).

3. Complete OT Implementation

Let's package the protocol into clean functions and test exhaustively.

def dh_ot_sender_setup():
    """Sender generates keypair."""
    a = ZZ.random_element(1, p - 1)
    A = g^a
    return a, A

def dh_ot_receiver_choose(A, choice):
    """Receiver creates blinded value based on choice bit."""
    r = ZZ.random_element(1, p - 1)
    if choice == 0:
        B = g^r
    else:
        B = A * g^r
    return r, B

def dh_ot_sender_encrypt(a, A, B, m0, m1):
    """Sender computes keys and encrypts both messages."""
    k0 = B^a
    k1 = (B / A)^a
    e0 = (m0 + int(k0)) % p
    e1 = (m1 + int(k1)) % p
    return e0, e1

def dh_ot_receiver_decrypt(A, r, e0, e1, choice):
    """Receiver decrypts the chosen message."""
    k = A^r
    e_b = e0 if choice == 0 else e1
    return (e_b - int(k)) % p

# Quick sanity check
for b in [0, 1]:
    a, A = dh_ot_sender_setup()
    r, B = dh_ot_receiver_choose(A, b)
    e0, e1 = dh_ot_sender_encrypt(a, A, B, 42, 99)
    result = dh_ot_receiver_decrypt(A, r, e0, e1, b)
    expected = 42 if b == 0 else 99
    print(f"OT(choice={b}): got {result}, expected {expected} {'✓' if result == expected else '✗'}")

# Exhaustive test: 50 random message pairs × both choices
all_correct = True
for trial in range(50):
    m0 = ZZ.random_element(0, p)
    m1 = ZZ.random_element(0, p)
    for choice in [0, 1]:
        a, A = dh_ot_sender_setup()
        r, B = dh_ot_receiver_choose(A, choice)
        e0, e1 = dh_ot_sender_encrypt(a, A, B, m0, m1)
        result = dh_ot_receiver_decrypt(A, r, e0, e1, choice)
        expected = m0 if choice == 0 else m1
        if result != expected:
            print(f"FAIL: m0={m0}, m1={m1}, b={choice}, got={result}")
            all_correct = False

print(f"100 random OT executions: {'all correct ✓' if all_correct else 'FAILURES'}")

4. Security Analysis

Sender Privacy (Receiver learns only $m_b$)

The receiver knows $A = g^a$ and their own $r$. They can compute $A^r = g^{ar}$, which is the key for their chosen message.

To decrypt the other message, they would need:

• If $b = 0$: need $k_1 = g^{ar - a^2}$, which requires knowing $a$

• If $b = 1$: need $k_0 = g^{a^2 + ar}$, which requires knowing $a$

Computing $a$ from $A = g^a$ is the discrete logarithm problem, hard by assumption.

# Sender privacy: receiver can't compute the other key
a, A = dh_ot_sender_setup()
choice = 0
r, B = dh_ot_receiver_choose(A, choice)

# Receiver's key
k_recv = A^r

# The actual k1 (computed using secret a, receiver doesn't know a)
k1_actual = (B / A)^a

print(f"Receiver's key (k0 = A^r): {k_recv}")
print(f"Other key (k1 = (B/A)^a):  {k1_actual}  ← receiver can't compute this")
print(f"\nTo compute k1, receiver would need a = {a}")
print(f"But all they see is A = g^a = {A}")
print(f"Finding a requires solving the discrete log problem.")

Receiver Privacy (Sender learns nothing about $b$)

The sender sees $B$, which is either $g^r$ or $A \cdot g^r = g^{a+r}$. Since $r$ is uniformly random:

• $g^r$ is uniformly distributed over the group

• $g^{a+r}$ is also uniformly distributed (shifting by $a$ is a bijection)

Both distributions are identical, the sender gains zero information about $b$.

# Receiver privacy: B looks the same for both choices
a, A = dh_ot_sender_setup()

# Collect B values for both choices
B_vals_0 = set()
B_vals_1 = set()
for _ in range(500):
    _, B0 = dh_ot_receiver_choose(A, choice=0)
    _, B1 = dh_ot_receiver_choose(A, choice=1)
    B_vals_0.add(int(B0))
    B_vals_1.add(int(B1))

print(f"Distinct B values for choice=0: {len(B_vals_0)}")
print(f"Distinct B values for choice=1: {len(B_vals_1)}")
print(f"Overlap: {len(B_vals_0 & B_vals_1)} values appear in both")
print(f"\nBoth choices produce the same uniform distribution over GF({p})*.")
print(f"The sender cannot distinguish b=0 from b=1.")

Misconception alert. "The sender knows $a$, so can't they check whether $B = g^r$ or $B = g^{a+r}$?" No! The sender doesn't know $r$. They would have to try every possible $r$, which is exhaustive search, equivalent to brute-forcing the discrete log.

5. RSA-Based OT

Bridge from Module 04. The first OT construction (Even, Goldreich, Lempel, 1985) used RSA rather than Diffie-Hellman. The RSA blinding trick hides the receiver's choice.

Protocol:

1. Sender generates RSA key $(n, e, d)$ and random values $x_0, x_1$

2. Receiver picks random $k$, computes $v = x_b + k^e \bmod n$

3. Sender computes $k_i' = (v - x_i)^d \bmod n$ for $i = 0, 1$

4. Sender sends $c_i = m_i + k_i' \bmod n$

5. Receiver recovers $m_b = c_b - k \bmod n$ (since $k_b' = k$)

def rsa_ot(m0, m1, choice):
    """RSA-based 1-of-2 OT (EGL construction)."""
    # Sender generates small RSA key
    p_rsa, q_rsa = 61, 53
    n = p_rsa * q_rsa               # 3233
    phi_n = (p_rsa - 1) * (q_rsa - 1)
    e_rsa = 17
    d_rsa = inverse_mod(e_rsa, phi_n)
    
    # Sender picks random x0, x1
    x0 = ZZ.random_element(2, n)
    x1 = ZZ.random_element(2, n)
    
    # Receiver blinds chosen x value
    k = ZZ.random_element(2, n)
    x_b = x0 if choice == 0 else x1
    v = (x_b + power_mod(k, e_rsa, n)) % n
    
    # Sender computes both possible keys
    k0_prime = power_mod((v - x0) % n, d_rsa, n)
    k1_prime = power_mod((v - x1) % n, d_rsa, n)
    c0 = (m0 + k0_prime) % n
    c1 = (m1 + k1_prime) % n
    
    # Receiver decrypts
    c_b = c0 if choice == 0 else c1
    m_received = (c_b - k) % n
    return m_received

# Test
for b in [0, 1]:
    result = rsa_ot(42, 99, b)
    expected = 42 if b == 0 else 99
    print(f"RSA OT (choice={b}): got {result}, expected {expected} {'✓' if result == expected else '✗'}")

print()
print("Key insight: v = x_b + k^e looks random regardless of b,")
print("because k^e (RSA encryption of random k) is itself random.")

Checkpoint 3. In the RSA-based OT, why does $k_b' = k$? Because $k_b' = (v - x_b)^d = (k^e)^d = k \bmod n$ by the RSA correctness property. The other key $k_{1-b}' = ((x_b - x_{1-b}) + k^e)^d$ has no simple form without knowing $d$.

6. OT Completes Yao's Protocol

Bridge from Notebook 12c. Remember Alice's garbled circuit: Bob needs one wire label per input wire, but Alice holds both labels. OT is exactly the right tool.

For each of Bob's input wires:

• Alice (sender) offers $(\text{label}_0, \text{label}_1)$ for that wire

• Bob (receiver) has his input bit $b$

• After OT: Bob gets $\text{label}_b$, Alice doesn't learn $b$

import os

def random_label():
    """Random 128-bit wire label."""
    return os.urandom(16)

# Alice has two labels per input wire for Bob
bob_wire_0 = (random_label(), random_label())  # (label_for_0, label_for_1)
bob_wire_1 = (random_label(), random_label())

# Bob's actual input bits
bob_bits = [1, 0]

# Run OT for each of Bob's input wires
# We use DH-OT, encoding labels as integers mod p
print("=== OT for Bob's Input Labels ===")
print()
for i, (wire_labels, bit) in enumerate(zip([bob_wire_0, bob_wire_1], bob_bits)):
    # Encode labels as integers (first 4 bytes)
    label_int_0 = int.from_bytes(wire_labels[0][:4], 'big') % p
    label_int_1 = int.from_bytes(wire_labels[1][:4], 'big') % p
    
    # Run OT: Alice offers both label-ints, Bob picks by his bit
    a, A = dh_ot_sender_setup()
    r, B = dh_ot_receiver_choose(A, bit)
    e0, e1 = dh_ot_sender_encrypt(a, A, B, label_int_0, label_int_1)
    received = dh_ot_receiver_decrypt(A, r, e0, e1, bit)
    
    expected = label_int_0 if bit == 0 else label_int_1
    print(f"Wire {i}: Bob's bit = {bit}")
    print(f"  Alice offered: label_0 = {label_int_0}, label_1 = {label_int_1}")
    print(f"  Bob received:  {received} {'✓' if received == expected else '✗'}")
    print(f"  Alice learned: nothing about b = {bit}")
    print()

For a garbled circuit where Bob has $k$ input bits, we need $k$ independent OT executions.

Application	Bob's input bits	OTs needed
1-bit comparison	1	1
AES circuit	128	128
SHA-256 circuit	256	256
Millionaire's problem (32-bit)	32	32

Public-key OT is expensive (~1 ms per instance). For large circuits, this becomes a bottleneck.

7. OT Extension

OT extension (Ishai, Kilian, Nissim, Petrank, 2003) is a remarkable result:

A small number of "base" OTs (using public-key crypto) can be extended to millions of OTs using only symmetric-key operations (hashing).

With $\kappa$ base OTs (where $\kappa$ is a security parameter, e.g., 128), we can perform an unlimited number of OTs:

	Base OT	Extended OT
Crypto	Public-key (DH/RSA)	Symmetric (SHA-256)
Cost per OT	~1 ms	~1 μs
Number needed	$\kappa$ (e.g., 128)	Unlimited

This 1000× speedup is what makes garbled circuits practical for real-world secure computation.

Crypto foreshadowing. OT is not just for garbled circuits. In the next notebook, we'll see how the SPDZ protocol uses correlated OT to generate Beaver triples for multiplication, the same Beaver triples we met in Notebook 12b, but generated without any trusted dealer.

8. Exercises

Exercise 1 (Worked): Verify the Key Equations

Problem. Trace through the DH-based OT for both choice values. For each case, verify that exactly one of $\{k_0, k_1\}$ equals $A^r$.

Solution:

# Exercise 1: Verify key equations
a, A = dh_ot_sender_setup()

for choice in [0, 1]:
    r, B = dh_ot_receiver_choose(A, choice)
    
    # Sender's keys
    k0 = B^a
    k1 = (B / A)^a
    
    # Receiver's key
    k_recv = A^r   # = g^(ar) in both cases
    
    print(f"=== Choice b = {choice} ===")
    print(f"  B = {'g^r' if choice == 0 else 'A · g^r'} = {B}")
    print(f"  k0 = B^a     = {k0}  {'← matches A^r ✓' if k0 == k_recv else ''}")
    print(f"  k1 = (B/A)^a = {k1}  {'← matches A^r ✓' if k1 == k_recv else ''}")
    print(f"  A^r          = {k_recv}")
    print(f"  Receiver can decrypt m_{choice}, not m_{1 - choice}")
    print()

Exercise 2 (Guided): String Transfer via OT

Problem. Use OT to transfer a multi-character string one character at a time. The sender holds two strings of equal length; the receiver picks one.

Hint: run one OT per character position, encoding each character as its ASCII value mod $p$.

# Exercise 2: fill in the TODOs
msg0 = "HELLO"
msg1 = "WORLD"
choice = 1  # Receiver wants msg1

received_chars = []
for i in range(len(msg0)):
    # Encode characters as integers
    c0 = ord(msg0[i])
    c1 = ord(msg1[i])
    
    # TODO: Run DH-OT for this character
    # a, A = dh_ot_sender_setup()
    # r, B = dh_ot_receiver_choose(A, choice)
    # e0, e1 = dh_ot_sender_encrypt(a, A, B, c0, c1)
    # result = dh_ot_receiver_decrypt(A, r, e0, e1, choice)
    # received_chars.append(chr(result))
    pass

# TODO: Reconstruct the string
# received_string = ''.join(received_chars)
# expected = msg0 if choice == 0 else msg1
# print(f"Received: '{received_string}'")
# print(f"Expected: '{expected}'")
# print(f"Correct? {received_string == expected}")

Exercise 3 (Independent): What if the Receiver Cheats?

Problem. What happens if a malicious receiver sends $B = g^{r_1} \cdot A^2$ instead of the honest $B = g^r$ or $B = A \cdot g^r$?

1. Compute what $k_0$ and $k_1$ become in this case.

2. Can the receiver decrypt either $m_0$ or $m_1$? Both? Neither?

3. What does this tell you about the security model of this OT protocol?

# Exercise 3: experiment here

Summary

Concept	Key Fact
OT ideal functionality	Receiver gets $m_b$; sender learns nothing about $b$; receiver learns nothing about $m_{1-b}$
DH-based OT	Receiver sends $B = g^r$ or $B = A \cdot g^r$; both are uniformly random
Sender privacy	Computing the other key requires solving the discrete log problem
Receiver privacy	$B$ is uniform regardless of choice, sender gains zero information
RSA-based OT	Blinding trick: $v = x_b + k^e$ hides the choice via RSA one-wayness
OT + garbled circuits	One OT per input wire gives Bob his labels without revealing his bits
OT extension	128 base OTs → millions of OTs using only hashing

Oblivious Transfer is one of the most fundamental primitives in cryptography. It is both necessary and sufficient for secure computation, any function can be computed securely given only OT as a building block.

---

Next: 12e: The SPDZ Protocol, achieving malicious security with MACs and Beaver triple preprocessing.