# How to implement 1-out-of-n OT from 1-out-of-2 OT?

How can I implement a 1-out-of-$n$ oblivious transfer protocol from 1-out-of-2 OT protocol which is resistant against passive corruption? Assume we can access 1-out-of-2 OT $n$ times.

Approach 1

The simplest way of doing this is for the receiver, with choice $j \in \{1,\dots,n\}$, to input $1$ in the $j$-th 1-out-of-2 OT and $0$ elsewhere. The sender, with input $(x_1, \dots, x_n)$, inputs $(0,x_i)$ in the $i$-th OT.

Approach 2

An alternative protocol (that just came out of a discussion with a colleague, and seems to be actively secure) is for the sender to sample $n$ random strings $r_1,\dots,r_n$. Now run $n$ 1-out-of-2 OTs where the sender inputs:

\begin{aligned} (r_1, \,& x_1) \\ (r_2, \,& r_1 \oplus x_2) \\ (r_3, \,& r_1 \oplus r_2 \oplus x_3) \\ &\vdots \\ (r_n, \,& r_1 \oplus r_2 \oplus r_3 \oplus \dots \oplus r_{n-1} \oplus x_n) \\ \end{aligned}

Now, it should be easy to see how the receiver gets the right choice. The advantage here is that a cheating receiver cannot easily learn any other choices, as each $x_i$ is masked by a fresh random value.

Approach 3 (using $\log n$ OTs)

Naor and Pinkas gave a protocol using just $\log_2 n$ 1-out-of-2 OTs on $k$-bit strings (for security parameter $k$). The sender inputs $\log{n}$ random pairs of strings to the 1-out-of-2 OTs, and the receiver inputs their choice represented as $\log n$ bits.

Now for each $i \in \{1,\dots,n\}$, let $b_1^i b_2^i \cdots b_{\log n}^i$ denote the bits of $i$. The $i$-th sender's string is defined as

$$x_i = H(s^1_{b_1^i}\|\cdots\|s^{\log n}_{b_{\log n^i}})$$

where $s^j_0,s^j_1$ are the random strings used in the $j$-th 1-out-of-2 OT. This gets a 1-out-of-$n$ OT on random strings, which can be easily converted to chosen strings by sending the XOR.

(Note that the Naor-Pinkas protocol used a PRF, but if $H$ is modelled as a random oracle then this works too)

Tung Chou and Claudio Orlandi created the most efficient 1-out-of-n OT protocol to date, based on an 1-out-of-2 OT protocoln, named The Simplest Protocol for Oblivious Transfer. You can read more about it here.

• Providing sources is nice but far from enough to be a decent answer. Could you please elaborate / summarize the paper ? – Biv Apr 18 '16 at 8:04
• Actually, it's not the most efficient 1-out-of-n OT protocol known; to do it, it uses $O(n)$ modular exponentiations; Naor and Pinkas showed how that can be done with $O(\log n)$ 1-out-of-2 OT's. This will be more efficient for sufficiently large $n$. – poncho Apr 18 '16 at 14:47