Oblivious Transfer

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 $m_1$ and $m_2$ and Bob flips a coin $c$ that has value $0$ or $1$. Once Bob decides on flipping the coin to get value $c$, Alice should send $m_c$ without her learning $c$ or Bob learning which $m$ 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 $E$ that is of order $q$ and has a generator $G$. All calculations are done $\bmod\ q$ if not stated otherwise.

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

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

She then derives her public key $A$ by multiplying $a$ with the generator $G$:

This public key is then shared with Bob.

Bob will now toss a fair coin which results in an outcome $c$ that’s either $0$ or $1$ for “Heads” and “Tails” respectively:

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

Based on the outcome of $c$ he does one of two things:

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

Once done, Bob sends the resulting $B$ to Alice. Note that in either case ($c$ being $0$ or $1$) Alice can’t determine whether Bob sent her the masked or unmasked $B$.

When Alice receives $B$ she computes two values $k_0$ and $k_1$ as follows:

1. $k_0 = aB$ which is her following the regular Elliptic Curve Diffie-Hellman protocol.
2. $k_1 = a(B - A)$

Alice then continues by encrypting the two messages $m_0$ and $m_1$ with $k_0$ and $k_1$ respectively to get the two ciphertexts $c_0$ and $c_1$:

Those two ciphertexts are then sent to Bob.

Bob will now compute the shared secret $k$ by multiplying his private key $b$ with Alice’s public key $A$:

Bob now attempts to decrypt both ciphertexts $c_0$ and $c_1$ with $k$ of which only one decryption will be successful. This in turn allows him to access the message $m_c$.

Why it works

First, it’s important to note that Bob generating two potential values for $B$ (one of which might be a value that’s masked via Alice’s public key $A$) won’t allow Alice to determine which version of $B$ 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 $c_0$ or $c_1$ but he doesn’t know which is which.

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

$c = 0$

$c = 1$

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 = abG$. The other key includes the term $-aA$ or $+aA$ which won’t allow for a correct decryption because Bob doesn’t know $aA$.

Resources

• Wikipedia - Oblivious Transfer
• Nguyen Thoi Minh Quan - Intuitive Advanced Cryptography