Oblivious Transfers

Introduction

In this post we’re going to get to know one of the most fundamental constructions in cryptography known as Oblivious Transfer or OT for short. It has been used in wide spectrum of topics in cryptography, and as such I must admit that I’m very excited to finally to get write about it!

Let’s start with a real life scenario¹! Say we have Alice and Bob, where Alice has two messages $m_0,m_1$ and Bob has a bit $b \in \lbrace 0,1 \rbrace$ such that Bob wants to retreive message $m_b$, how can Bob and Alice do this? Well, if Bob doesn’t care much about his privacy, he could send Alice the bit $b$ and Alice would send him $m_b$ in return. But what if Bob does care about his privacy? Of course Alice can send Bob both $m_0,m_1$ and Bob will simply pick $m_b$, but this also violates the privacy of Alice! So, if both parties care about their privacy we want Bob to learn $m_b$ without Alice learning $b$ and without Bob learning $m_{1-b}$. While this may sound impossible and paradoxical at this point, it is actually possible and if you finish reading this post you’ll probably be surprised by how simple it is. If Alice is tranferring $m_b$ to Bob while preserving all these privacy constraints, we say Alice Obliviously Transfers $m_b$ to Bob.

Without getting into the the technical details we can already say that Oblivious-Transfer is a general name for protocols with which one party can obliviously transfer data to another party. By “general name” I mean that just like sorting is a “general name” for various algorithms that sort data, OT is a name for protocols that obliviously transfer data. This also means that OT protocols take place between two parties: A sender who offers messages to be sent and a receiver who selects to receive one of the offered messages.

Let’s start with a short history of the problem.

History

The first appearance of Oblivious-Transfer was in a paper by Michael (Oser) Rabin from 1981 and it didn’t even match the definition we have given here. In the original version the sender had a single message $m$ and at the end of the protocol the receiver may either learn $m$ with probability $1/2$ or learn nothing with probability $1/2$ without the sender knowing if $m$ was indeed learned or not.

Cool Fact: The original paper was manually written! Tal Rabin noticed that the copies were becoming hard to find and decided to upload a scanner version. You can find the original manuscript as well as a typeset version on ePrint. (Paper link)

Cool Fact 2: Tal is Michael’s daughter.

A few years later, in 1985, Even, Goldreich and Lempel have given a construction to the OT as we have seen here, where one-of-two messages is being retreived. (Paper link)

Since then, various constructions have been proposed to OT, one of them, titled “The Simplest Protocol for Oblivious Transfer” by Chou and Orlandi published in 2015 is what we will see today in greater detail.

The OG OT

In this section we’ll see the original construction of Michael Rabin for “OT”, we put the “OT” in quotes since it doesn’t really match our definition for OT. I start with it both as a nice historical lesson and because it gives a good sense on the underlying concepts from which OT can built!

In this “OT” protocol we will have two parties, Alice and Bob. At the beginning of the protocol Alice holds a message $m$ while Bob has no input. At the end of the protocol we want Bob to learn $m$ with probability $1/2$ and learn nothing with probability $1/2$ without Alice knowing whether Bob did learn or didn’t learn $m$ eventually!

The construction of the protocol relies on RSA groups, so first let’s recall what RSA groups are.

RSA Groups

Given two distinct primes $p,q$ we call $N=pq$ an RSA-modulus. We denote by $\mathbb{Z}_N^*$ the set of numbers between $1$ and $N-1$ that are coprime to $N$. Notice that each number dividing $N$ has to divide at least one of it’s prime factors which are $p$ and $q$ so $\mathbb{Z}^*_N$ is the set of all numbers between $1$ and $N-1$ that are neither a multiple of $p$ nor $q$.

An RSA group is a group whose elements are $\mathbb{Z}^*_N$ for some RSA-modulus $N$ and the group operation is modular multiplcation modulo $N$.

Let’s have an example. Let $p=3$ and $q=5$ we have $N=15$ so $\mathbb{Z}^*_N={1,2,4,7,8,11,13,14}$. Our RSA group operation will take two numbers from $\mathbb{Z}^*_N$ and multiply them modulo $15$, for example $4*7=28 \equiv 13 \mod 15$. So if we apply the group operation on $4$ and $7$ we get $13$.

One characteristic of groups is that each element should have an inverse. We say that $a,b$ are inverse if $a*b=1$ according to the group operations. For example $2*8=16 \equiv 1 \mod 15$ so $2$ and $8$ are the inverse of each other!

One question you may ask is: “Given a number $a$ in $\mathbb{Z}_N^*$, how fast can we find its inverse?”. According to a popular theorem called the Chinese Remainder Theorem finding the inverse of $a$ in the RSA group can be done very efficiently if we know $p,q$, the factors of $N$. But what if we don’t know them and instead we are just given $N$? Well, we don’t really know but we assume that it is very hard and for sufficiently large $p,q$ it can take very long time. This assumption is the RSA assumption and that is what Rabin has also assumed while constructing his original OT.

Square Roots in RSA Groups