Oblivious Transfer (OT)
1outof\(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,

\(B\) learns \(x_i\) and nothing else

\(A\) learns nothing about \(i\)
Theorem: [Kilian’87] 1outof2 OT is universal for 2party SFE
In other words, given a 1outof2 OT protocol, one can do any 2party SFE. (Yao’s construction requires a block cipher in addition to a 1outof2 OT protocol.)
Note that oblivious transfer implies 2party SFE, which implies key exchange, and hence 1outof2 OT cannot be built from a blackbox oneway function. Instead, we build one using the DDH assumption [BellareMicali’92].
BellareMicali 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\}\).

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

\(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\).

\(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 honestbutcurious, 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.
NaorPinkas 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\}\).

\(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_{1v} \leftarrow \mathbb{Z}_q\).

\(A\) verifies that \(z_0 \ne z_1\) and applies a partial DDH random selfreduction: \((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)\).

\(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))\).

\(B\) decrypts \(CT_v\).
This protocol is information theoretically secure against \(B\), and DDH secure against \(A\). The random selfreduction destroys any partial information in the message \(B\) sends to \(A\). Note that this construction also generalizes to a 1outof\(n\) protocol.
DDH Random SelfReduction
Suppose we have a tuple \(g, g^x, g^y,g^z\). Then to perform a random selfreduction, 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 DHtuples to DHtuples, and nonDHtuples to nonDHtuples. 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)/(zxy)\) 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.
1outofn From 1outof2
We show how to construct a 1outof\(n\) OT protocol from any 1outof2 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\).

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

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\).

Let \(t=t_1...t_l\in\{0,1\}^l\). Then \(l\) 1outof2 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\}\).

\(B\) now has \(K_1^{t_1},...,K_l^{t_l}\) and can decrypt \(C_t\) to get \(m_t\).
Thus with \(\log N\) 1outof2 OT’s, a single 1outof\(N\) OT can be constructed, that has \(O(N)\) communication complexity.