0
$\begingroup$

I was reading Oblivious Transfer (Wikipedia) and the 1-2 oblivious transfer. I was confused why RSA was needed. Why wouldn't this work?:

A:m1, m0

A:x1, x2 -> B

B:k, b

B:Xb+k -> v -> A

A:Xb+k-X1, Xb+k-X2 -> k1, k2

A:m0+k0, m1+k1 -> m'1, m'2 -> B

B:m'b-k -> mb

$\endgroup$
1
$\begingroup$

A:Xb+k-X1, Xb+k-X2 -> k1, k2

A:m0+k0, m1+k1 -> m'1, m'2 -> B

B knows Xb+k (transmitted it in a previous message), X1, X2 (A sent those), hence he can compute k1, k2.

Hence, he can reconstruct both m0, m1, hence the protocol doesn't have the security properties we're looking at...

Now, you don't have to use RSA, however you really do have to use something that has some cryptographical properties. After all, Oblivious Transfer is provably impossible between two computationally-unbounded entities, hence for OT to be possible, we need to use something that a real entity can't solve (but an unbounded entity can); RSA is one such problem (but certainly not the only one).

$\endgroup$
  • $\begingroup$ So how does RSA help to prevent this and how does the original protocol works. $\endgroup$ – John Hao Dec 5 '19 at 5:19
  • $\begingroup$ @JohnHao: it works because (assuming $b=1$) the Bob receives $m'_1 = m_1 + (k^e + x_0 - x_1)^d$, but $k^e + x_0 - x_1$ is essentially a random number, and so Bob cannot recover the e'th root of it (this is the RSA problem). $\endgroup$ – poncho Dec 5 '19 at 14:42

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.