# Oblivious Transfer (OT)

## 1-out-of-$$n$$ Oblivious Transfer

Suppose $$A$$ has a list $$(x_1,...,x_n)$$, $$B$$ has $$i \in \{1,...,n\}$$.

We want a SFE protocol where $$F_A = 0, F_B = x_i$$, that is,

1. $$B$$ learns $$x_i$$ and nothing else

2. $$A$$ learns nothing about $$i$$

Theorem: [Kilian’87] 1-out-of-2 OT is universal for 2-party SFE

In other words, given a 1-out-of-2 OT protocol, one can do any 2-party SFE. (Yao’s construction requires a block cipher in addition to a 1-out-of-2 OT protocol.)

Note that oblivious transfer implies 2-party SFE, which implies key exchange, and hence 1-out-of-2 OT cannot be built from a blackbox one-way function. Instead, we build one using the DDH assumption [Bellare-Micali’92].

## Bellare-Micali Construction

Let $$G$$ be a group of prime order $$p$$, and let $$g \in G$$ be a generator, and $$H:G\rightarrow\{0,1\}^n$$ be a hash function.

Suppose $$A$$ has $$x_0,x_1 \in \{0,1\}^n$$, and $$B$$ has $$b\in\{0,1\}$$.

1. $$A$$ publishes a random $$c \leftarrow G$$, $$B$$ picks $$k\leftarrow\mathbb{Z}_p$$, sets $$PK_b=g^K, PK_{1-b}=c/g^k$$ and sends $$PK_0,PK_1$$ to $$A$$. $$A$$ checks $$PK_0 PK_1 = c$$.

2. $$A$$ encrypts $$x_0$$ with El Gamal using $$PK_0$$, i.e. sets $$C_0 = [g^{r_0}, H(PK_0^{r_0}) \oplus x_0]$$, encrypts $$x_1$$ using $$PK_1$$, and sends $$C_0, C_1$$ to $$B$$.

3. $$B$$ decrypts $$C_b$$ using $$K$$, i.e. if $$C_b = [V_1, V_2]$$, $$B$$ computes $$X_b = H(V_1^K) \oplus V_2$$.

Security: $$A$$ cannot learn anything about $$b$$ (information theoretic result).

If $$B$$ is honest-but-curious, then assuming DDH, $$B$$ can only decrypt one of $$C_0$$ or $$C_1$$.

If $$B$$ is malicious, then assuming DDH is not enough: conceivably $$B$$ could generate $$PK_0, PK_1$$ in such a way that $$B$$ knows partial information about their corresponding private keys, and perhaps $$B$$ can then learn partial information about both $$x_0$$ and $$x_1$$. However, if $$H$$ is a random oracle, then the protocol is secure under CDH.

## Naor-Pinkas Construction

[Naor, Pinkas '00] Let $$G$$ be a group of prime order $$q$$ and let $$g \in G$$ be a generator. Suppose $$A$$ has $$m_0, m_1$$ and $$B$$ has $$V \in \{0,1\}$$.

1. $$B$$ sends the tuple $$(g, x = g^a, y = g^b, z_0 = g^{c_0}, z_1 = g^{c_1}$$ to $$A$$, where $$a,b \leftarrow \mathbb{Z}_q$$, $$c_v = ab$$ and $$c_{1-v} \leftarrow \mathbb{Z}_q$$.

2. $$A$$ verifies that $$z_0 \ne z_1$$ and applies a partial DDH random self-reduction: $$(g,x,y,z_0)$$ becomes $$T_0 = (g,x,y_0,z'_0)$$, and $$(g,x,y,z_1)$$ becomes $$T_1 = (g,x,y_1,z'_1)$$.

3. $$A$$ encrypts $$m_0$$ using $$T_0$$ and $$m_1$$ using $$T_1$$, that is, $$A$$ sends to $$B$$ the ciphertexts $$(CT_0 = (y_0,mz'_0), CT_1 = (y_1, mz'_1))$$.

4. $$B$$ decrypts $$CT_v$$.

This protocol is information theoretically secure against $$B$$, and DDH secure against $$A$$. The random self-reduction destroys any partial information in the message $$B$$ sends to $$A$$. Note that this construction also generalizes to a 1-out-of-$$n$$ protocol.

## DDH Random Self-Reduction

Suppose we have a tuple $$g, g^x, g^y,g^z$$. Then to perform a random self-reduction, pick random $$a,b \leftarrow\mathbb{Z}_p^*$$, and output $$g, g^{(x+b)a}, g^y, g^{(z+by)a}$$.

Note that this transformation takes DH-tuples to DH-tuples, and non-DH-tuples to non-DH-tuples. Furthermore, the new exponents are independent of the originals. This is easy to see if we start with a DH tuple. On the other hand, if the tuple is not DH, then given any $$x',z'$$, there exists a unique $$a,b$$ such that $$(x+b)a = x', (z+by)a = z'$$ (we can solve to get $$a=(z' -x'y)/(z-xy)$$ and $$b$$ can be easily determined from $$a$$). As expected, these solutions are not well defined if $$z = xy$$, i.e. the original tuple is DH.

## 1-out-of-n From 1-out-of-2

We show how to construct a 1-out-of-$$n$$ OT protocol from any 1-out-of-2 OT protocol.

Suppose $$A$$ has $$m_0,...,m_N \in\{0,1\}^n$$ and $$B$$ has $$t \in \{0,...,N\}$$. Assume $$N = 2^l - 1$$ for some $$l$$.

1. $$A$$ prepares $$2l$$ keys $$(K_1^0, K_1^1),...,(K_l^0,K_l^1)$$.

2. Let $$F_k:\{0,1\}^l\rightarrow\{0,1\}^n$$ be a PRF. $$A$$ sends to $$B$$ the tuple $$(C_0,...,C_N)$$: view the message index as a bit string $$I=I_1...I_l \in \{0,1\}^l$$, and encrypt using

$$C_I = m_I \oplus \oplus_{i=1}^l F_{K_i^{I_i}}(I)$$

Note $$A$$ sends $$O(N)$$ bits to $$B$$.

3. Let $$t=t_1...t_l\in\{0,1\}^l$$. Then $$l$$ 1-out-of-2 OT’s are performed where during the $$j$$th OT, $$A$$ has $$(K_j^0,K_j^1)$$ and $$B$$ has $$t_j\in\{0,1\}$$.

4. $$B$$ now has $$K_1^{t_1},...,K_l^{t_l}$$ and can decrypt $$C_t$$ to get $$m_t$$.

Thus with $$\log N$$ 1-out-of-2 OT’s, a single 1-out-of-$$N$$ OT can be constructed, that has $$O(N)$$ communication complexity.

Ben Lynn blynn@cs.stanford.edu 💡