Skip to content

Oblivious Transfer

Table of contents

Open Table of contents

What it is

An Oblivious Transfer allows a sender to send one of many different messages to a receiver so that the receiver doesn’t know which one of the messages the sender decided to send.

As an example, let’s assume that Alice has two messages m1m_1 and m2m_2 and Bob flips a coin cc that has value 00 or 11. Once Bob decides on flipping the coin to get value cc, Alice should send mcm_c without her learning cc or Bob learning which mm Alice sent

How it works

The following Oblivious Transfer protocol is based on the Elliptic Curve Diffie-Hellman protocol which is worthwhile to revisit before continuing.

Throughout this writeup We’ll be using an Elliptic Curve EE that is of order qq and has a generator GG.

In our setup Alice acts as the sender who wants to ensure that Bob, the receiver gets access to only one of two messages m0m_0 and m1m_1 without learning which one he got access to.

As a first step, Alice generates her private key aa by sampling a random value from Zq\mathbb{Z}_q:

a$Zqa \overset{{\scriptscriptstyle\$}}{\leftarrow} \mathbb{Z}_q

She then derives her public key AA by multiplying aa with the generator GG:

A=aGA = aG

This public key is then shared with Bob.

Bob will now toss a fair coin which results in an outcome cc that’s either 00 or 11 for “Heads” and “Tails” respectively:

c${0,1}c \overset{{\scriptscriptstyle\$}}{\leftarrow} \{0, 1\}

He also generates his private key bb by sampling a random value from Zq\mathbb{Z}_q:

b$Zqb \overset{{\scriptscriptstyle\$}}{\leftarrow} \mathbb{Z}_q

Based on the outcome of cc he does one of two things:

  1. If c=0c = 0 he sets his public key BB to B=bGB = bG which is him following the regular Elliptic Curve Diffie-Hellman protocol.
  2. If c=1c = 1 he sets BB to B=bG+AB = bG + A which is him adding Alice’s public key to his derived his “masked” public key.

Once done, Bob sends the resulting BB to Alice. Note that in either case (cc being 00 or 11) Alice can’t determine whether Bob sent her the masked or unmasked BB.

When Alice receives BB she computes two values k0k_0 and k1k_1 as follows:

  1. k0=aBk_0 = aB which is her following the regular Elliptic Curve Diffie-Hellman protocol.
  2. k1=a(BA)k_1 = a(B - A)

Alice then continues by encrypting the two messages m0m_0 and m1m_1 with k0k_0 and k1k_1 respectively to get the two ciphertexts c0c_0 and c1c_1:

c0=Ek0(m0)c1=Ek1(m1)c_0 = E_{k_0}(m_0) \\ c_1 = E_{k_1}(m_1)

Those two ciphertexts are then sent to Bob.

Bob will now compute the shared secret kk by multiplying his private key bb with Alice’s public key AA:

k=bA=baG\begin{aligned} k &= bA \\ &= baG \end{aligned}

Bob now attempts to decrypt both ciphertexts c0c_0 and c1c_1 with kk of which only one decryption will be successful. This in turn allows him to access the message mcm_c.

Oblivious Transfer

Why it works

First, it’s important to note that Bob generating two potential values for BB (one of which might be a value that’s masked via Alice’s public key AA) won’t allow Alice to determine which version of BB she got, since both will look like a random value to her.

Next, Bob will only be able to decrypt one of the two ciphertexts c0c_0 or c1c_1 but he doesn’t know which is which.

Only one decryption will work because as outlined in the following equations.

c=0c = 0

B=bGk0=aB=abGk1=a(BA)=a(bGA)=abGaA\begin{aligned} B &= bG \\ k_0 &= aB \\ &= \boxed{abG} \\ k_1 &= a(B - A) \\ &= a(bG - A) \\ &= abG - aA \end{aligned}

c=1c = 1

B=bG+Ak0=aB=a(bG+A)=abG+aAk1=a(BA)=a(bG+AA)=a(bG+AA)=abG\begin{aligned} B &= bG + A \\ k_0 &= aB \\ &= a(bG + A) \\ &= abG + aA \\ k_1 &= a(B - A) \\ &= a(bG + A - A) \\ &= a(bG + \cancel{A} - \cancel{A}) \\ &= \boxed{abG} \end{aligned}

As one can see, only one of the two keys resolves to the shared secret Bob is also able to compute via k=bA=baG=abGk = bA = baG = abG. The other key includes the term aA-aA or +aA+aA which won’t allow for a correct decryption because Bob doesn’t know aAaA.

Resources