Can we upgrade OT(oblivious transfer) from 1-out-of-2 protocol to 1-out-of-N protocol directly?

Question

Reading paper: ‘even s. A randomized protocol for signing contracts [J]. ACM SIGACT news, 1983’, there has been a question why this scheme cannot be directly extended from 1-out-of-2 OT to 1-out-of-n OT. The OT extension in the later paper adopts very complex methods to expand.

Brief description of the original scheme: Alice is the sender and Bob is the receiver. Alice has messages M0, M1; Bob has choice bit: $b \in \{0, 1\}$；

1. Alice generates random numbers x0, x1 and sends them to Bob;

2. Bob generates a random number k and calculates $c_b = x_b + ENC_{PKA}(k)$, and send $c_b$ to Alice;

3. Alice calculates $k0 = DEC_{ska}(c_b - x0)，k1 = DEC_{ska}(c_b - x1)$, and then calculates $e0 = M0 \bigoplus k0$, $e1 = M1 \bigoplus k1$, and sends e0, e1 to Bob;

4. Bob calculate the result: $Mb = eb \bigoplus k$.

I understand that this protocol should be directly extended to 1-out-of-N OT protocol by: Alice is the sender and Bob is the receiver. Alice has messages M1,M2,..., Mn; Bob has choice number $b \in [1, n]$;

1. Alice generates random number x1, ..., xn, and send all of them to Bob;

2. Bob generates a random number k and calculates $c_b = x_b + ENC_{PKA}(k)$，and send $c_b$ to Alice;

3. Alice calculates: $k1 = DEC_{ska}(c_b - x1),..., kn = DEC_{ska}(c_b - xn)$, and then calculates $e1 = M1 \bigoplus k1, ..., en = Mn \bigoplus kn$, and sends e1,...en to Bob;

4. Bob calculate the result: $Mb = eb \bigoplus k$.

My question is, why do the subsequent papers not do this, but usually use very complex methods to achieve 1-out-of-N OT? Is it for safety or efficiency?

Answer 1

You might be misunderstanding the purpose of OT extension (e.g., IKNP). The purpose of it is to do a lot of 1-2 OT, using only a few 1-2 OT.

It is easy to obtain a 1-n OT from $n$ 1-2 OT just by letting the receiver set the corresponding bit to 1 and the rest to 0 in all the 1-2 OT. The sender just sets $(\perp, m_i)$ for $i \in [n]$. Of course, this only works in the semi-honest setting.