3
$\begingroup$

If computationally unbounded parties $A$ and $B$ have only a noiseless channel between them, why is information-theoretic oblivious transfer impossible even for the passive cheating setting?

Intuitively, the noiseless channel makes the views of $A$ and $B$ almost identical except for the private randomness that $A$ and $B$ use. An unbounded passive cheater shouldn't be able to guess this randomness. How do we provably rule out some clever usage of private randomness that allows the sender to hide one of their bits and the receiver to hide her choice bit?

Improve this question
$\endgroup$
2
$\begingroup$

Information theoretic OT cannot be achieved because OT can compute any function in a two party setting, that is, OT is complete (meaning, it is among the hardest problems in its complexity class) as shown by Kilian[0]. We know that there are functions that cannot be information theoretic securely in a two party setting[1]. Hence, information theoretic OT is impossible.

[0] https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.92.9265&rep=rep1&type=pdf

[1] https://eprint.iacr.org/2006/183.pdf

Improve this answer
$\endgroup$
2
  • $\begingroup$ To clarify more directly for noiseless communication channels impossibility: knowledge symmetry says that the receiver learns the bit of choice as a function of whatever sender sends and whatever the receiver sends. An unbounded passive sender can therefore compute whatever the receiver learns with only its own view, breaking privacy for the receiver. $\endgroup$ – Tom Ridley Sep 1 '20 at 18:40
  • $\begingroup$ A follow-up to my own initial question is that perhaps my initial statement that private randomness shouldn't be able to be guessed is wrong for unbounded adversaries. More specifically for unbounded adversaries, the only private information are their respective inputs. If this is the case, then of course OT in the information theoretic sense cannot be achieved by noiseless communication. $\endgroup$ – Tom Ridley Sep 1 '20 at 18:46

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.