4
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

(Caveat: I've only thought very briefly about this and am not 100% sure about its active security)

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)

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Providing sources is nice but far from enough to be a decent answer. Could you please elaborate / summarize the paper ? $\endgroup$ – Biv Apr 18 '16 at 8:04
  • 1
    $\begingroup$ 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$. $\endgroup$ – poncho Apr 18 '16 at 14:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.