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

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?

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.