OT ⇒ OT extension (IKNP)

Fully-black-box reduction · random oracle model · IKNP03 · security loss: additive: of order κ q / 2^κ for q random-oracle queries, plus κ times the base-OT advantage

Statement

In the random-oracle model, $\kappa$ base oblivious transfers of $\kappa$-bit strings, stretched to $m$ bits with the hash as a generator, yield any polynomial number $m$ of 1-out-of-2 transfers of $\ell$-bit strings secure against semi-honest adversaries, with $O(m)$ hash evaluations and $O(m(\kappa +\ell ))$ bits of communication — IKNP03.

Sketch

The receiver, with choice bits $r\in \{0,1{\}}^m$, samples a uniform matrix $T\in \{0,1{\}}^{m\times \kappa }$; the sender samples $s\in \{0,1{\}}^{\kappa }$. In $\kappa$ base transfers with the roles reversed, the sender obtains, for each column $j$, the column $t^j$ if $s_j=0$ and $t^j\oplus r$ if $s_j=1$, so the $i$-th row of its matrix $Q$ is $q_i=t_i\oplus r_{i}s$. It sends $y_i^b:=x_i^b\oplus H(i,q_i\oplus bs)$ for $b\in \{0,1\}$, and the receiver outputs $y_i^{r_i}\oplus H(i,t_i)$. The value $H(i,q_i\oplus (1\oplus r_i)s)=H(i,t_i\oplus s)$ masking the other message stays hidden because $s$ is uniform and unknown to the receiver — IKNP03.

\begin{algorithm}
\algname{Algorithm}
\caption{IKNP extension, transfer $i$}
\begin{algorithmic}
\State Receiver: $t_i \gets$ row $i$ of $T$
\Comment{After the base transfers the sender holds $q_i = t_i \oplus r_i s$}
\State Sender: $y_i^0 \gets x_i^0 \oplus H(i, q_i)$; $y_i^1 \gets x_i^1 \oplus H(i, q_i \oplus s)$
\State Receiver: \Return $y_i^{r_i} \oplus H(i, t_i)$
\end{algorithmic}
\end{algorithm}

Notes

• Efficiency: after $\kappa$ public-key transfers, each extended transfer costs a constant number of hash evaluations and $O(\kappa +\ell )$ bits of communication — IKNP03.
• Without a random oracle, Beaver’s extension needs only a one-way function, but uses its code — Bea96.
• Malicious security adds only a small overhead to the semi-honest protocol — KOS15.