Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|improve this question
up vote 3 down vote accepted

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)

share|improve this answer

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.

share|improve this answer
    
Providing sources is nice but far from enough to be a decent answer. Could you please elaborate / summarize the paper ? – Biv Apr 18 at 8:04
1  
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 at 14:47

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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