Cryptography

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].

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

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

1. $A$ publishes a random $c\leftarrow G$, $B$ picks $k\leftarrow {\mathbb{Z}}_p$, sets ${\mathrm{PK}}_b=g^K,{\mathrm{PK}}_{1-b}=c/g^k$ and sends ${\mathrm{PK}}_0,{\mathrm{PK}}_1$ to $A$. $A$ checks ${\mathrm{PK}}_0{\mathrm{PK}}_1=c$.

2. $A$ encrypts $x_0$ with El Gamal using ${\mathrm{PK}}_0$, i.e. sets $C_0=[g^{r_0},H({\mathrm{PK}}_0^{r_0})\oplus x_0]$, encrypts $x_1$ using ${\mathrm{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 ${\mathrm{PK}}_0,{\mathrm{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 '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 \{\mathrm{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=\mathrm{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{\prime }_0)$, and $(g,x,y,z_1)$ becomes $T_1=(g,x,y_1,z{\prime }_1)$.

3. $A$ encrypts $m_0$ using $T_0$ and $m_1$ using $T_1$, that is, $A$ sends to $B$ the ciphertexts $({\mathrm{CT}}_0=(y_0,\mathrm{mz}{\prime }_0),{\mathrm{CT}}_1=(y_1,\mathrm{mz}{\prime }_1))$.

4. $B$ decrypts ${\mathrm{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.

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+\mathrm{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\prime ,z\prime$, there exists a unique $a,b$ such that $(x+b)a=x\prime ,(z+\mathrm{by})a=z\prime$ (we can solve to get $a=(z\prime -x\prime y)/(z-\mathrm{xy})$ and $b$ can be easily determined from $a$). As expected, these solutions are not well defined if $z=\mathrm{xy}$, i.e. the original tuple is DH.

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 \{\mathrm{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:\{\mathrm{0,1}{\}}^l\to \{\mathrm{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 \{\mathrm{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 \{\mathrm{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 \{\mathrm{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.