Skip to main content

Oblivious Transfer

Oblivious Transfer is a cryptographic technique in which a sender and a receiver engage in a series of messages between one another such that a sender has messages which a receiver can request, the receiver makes a choice, and prepares a response which the sender consumes and applies to the messages being sent but is unaware of the choice made by the receiver, then responds with the choice-applied message data such that upon receipt by the receiver, they are able to consume the intended message, but gain no awareness of the contents of the other messages.

We begin by explaining some base concepts of oblivious transfer protocols such that it becomes easier to follow along in the broader construction.

Simplest OT

In "The Simplest Protocol for Oblivious Transfer", Chou and Orlandi defined a new approach to oblivious transfer in which the construction relied only on the same assumptions as Diffie-Hellman. The approach is summarized below:

Simplest OT:
  1. Given a sender has two messages, m0, m1, and a receiver has a choice bit c, both parties sample a random private scalar x ← 𝔽p The sender’s private scalar will be denoted as a, the receiver’s private scalar will be denoted as b.
  2. The sender calculates the point A = a · G, and sends this to the receiver.
  3. If the receiver’s choice bit is 0, the receiver replies with B = b · G. If 1, the receiver replies with B = A + (b · G).
  4. The sender calculates two keys, k0 = H(a · B), and k1 = H(a · (B − A)), then encrypts m0 with k0, m1 with k1, and sends both encrypted messages to the receiver.
  5. The receiver calculates kc = H(b · A), and then uses this value to decrypt their chosen message.

Because neither party has the other party’s private scalar, provided the discrete logarithm assumption holds, it is impossible for the receiver to calculate the other message’s key, and impossible for the sender to calculate the receiver’s choice.

Simplest OT is capable of only delivering a singular choice of two messages, and has to be re-evaluated from scratch for each subsequent bit of information learned. Because of this, it is a poor system to directly construct oblivious protocols, however it is exceptionally useful to build on top of as a base OT seed for extension.

Correlated OT

Correlated oblivious transfer is a variant of oblivious transfer where instead of sending a singular choice, the choices themselves are implicitly correlated. The traditional extension approach involves a Random OT base, where the initial choice is random, and then pseudo-random extensions of the random seeds enable larger correlated constructions with many bits being able to be transferred based on the correlation without the cost of doing a singular OT for every bit. This is utilized in many MPC protocols, and further extended in subsequent papers such as "Actively Secure OT Extension with Optimal Overhead". At the lower level, correlated OT looks like the following:

Correlated OT (COT):
  1. The receiver obtains a ∆ ∈ 𝔽2κ from the sender.
  2. For every extension:
    1. Sample v ← 𝔽ℓ2κ. If the sender is corrupted, instead receive v ← 𝔽ℓ2κ from the adversary.
    2. Sample u ← 𝔽ℓ2 and compute w := v + u · ∆ ∈ 𝔽ℓ2κ. If the receiver is corrupted, instead receive u ← 𝔽ℓ2 and w ← 𝔽ℓ2κ from the adversary, and recompute w := v + u · ∆ ∈ 𝔽ℓ2κ.

Correlated OT Extension over LPN

In "Ferret: Fast Extension for Correlated OT with Small Communication", the authors contributed improvements to this protocol have sufficiently made COT feasible for general computability at speed. In short, the speed improvements are nearly over 200 times faster per correlation. For brevity, we list only the functions relevant to Quilibrium’s instantiation of Ferret, from the article:

Multi-Point Correlated OT (MPCOT):
  1. Given a family of efficiently-computable functions Φ = {Φn,t}n,t ∈ ℕ such that for any n,t ∈ ℕ with t ≤ n, Φn,t takes as an input a sorted subset of [n] of size t and outputs another subset of [m] with the same size for some integer t ≤ m ≤ n.
  2. The receiver obtains a ∆ ∈ 𝔽2κ from the sender.
  3. For extension, the receiver and sender agree to n, t, and the receiver sends Q = {a0, ..., at−1} where Q ⊆ [n] is a sorted set:
    1. Sample v ← 𝔽n2κ. If the sender is corrupted, instead receive v ← 𝔽n2κ from the adversary.
    2. Define an n-sized bit vector u := 𝕴(n, Q), and compute w := v + u · ∆ ∈ 𝔽n2κ. If the receiver is corrupted, instead receive u ← 𝔽n2 and w ← 𝔽n2κ from the adversary, and recompute w := v + u · ∆ ∈ 𝔽n2κ.
  4. Compute the set T = {β0, ..., βt−1} := Φn,t({α0, ..., αt−1}).
  5. Wait for the adversary to input m sets I0, ..., Im−1 ⊆ [n] ∪ {−1}.
  6. Check that αi ∈ Iβi for all i ∈ [t] and −1 ∈ Ij for all j ∈ [m] \ T. If the check fails, the process aborts.
Deal COT/MPCOT:
  1. Given a family of efficiently-computable functions Φ = {Φn,t}n,t ∈ ℕ such that for any n,t ∈ ℕ with t ≤ n, Φn,t takes as an input a sorted subset of [n] of size t and outputs another subset of [m] with the same size for some integer t ≤ m ≤ n.
  2. The receiver obtains a ∆ ∈ 𝔽2κ from the sender.
  3. To COT Extend: Call Correlated OT, receive ℓ random COT correlations.
  4. To MPCOT Extend: Call MPCOT, receive a multi-point COT of length n.
Deal COT/MPCOT:
  1. Given LPN parameters (n, k, t) and code generator C such that C(k, n, 𝔽) outputs a matrix A ∈ 𝔽k×n2.
  2. Both parties initialize once, sender samples a uniform ∆ ∈ 𝔽2κ and both parties invoke the Deal initialization step.
  3. Both parties invoke the COT extend functionality of Deal, returning v ← 𝔽k2κ to sender, (u, w) ∈ 𝔽k2 × 𝔽k2κ to the receiver such that w := v + u · ∆.
  4. To Extend:
    1. The receiver samples A ← C(k, n, 𝔽2) and e ← HWt, then sends A to the sender. Let Q = {a0, ..., at−1} ⊆ [n] be the sorted indices of non-zero entries in e.
    2. The sender and receiver invokes the Deal MPCOT functionality, returning s ∈ 𝔽n2κ to the sender and r ∈ 𝔽n2κ to the receiver, where r + s = e · ∆. If either party aborts, this protocol aborts.
    3. The sender computes y := v · A + s ∈ 𝔽n2κ and the receiver computes x := u · A + e ∈ 𝔽n2 and z := w · A + r ∈ 𝔽n2κ.
    4. The sender updates vector v := y[0 : k] ∈ 𝔽k2κ, and outputs a vector y′ := y[k : n] ∈ 𝔽l2κ. The receiver updates vectors (u, w) := (x[0 : k], z[0 : k]) ∈ 𝔽k2 × 𝔽k2κ and outputs two vectors (x′, z′) := (x[k : n], z[k : n]) ∈ 𝔽l2 × 𝔽l2κ.