0
$\begingroup$

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\}$

-Step 1: Alice generates random numbers x0, x1 and sends them to Bob;

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

-Step 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;

-Step 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]$;

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

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

-Step 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;

-Step 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?

$\endgroup$

1 Answer 1

0
$\begingroup$

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.

$\endgroup$

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.