Until recently, the existence of collection of trapdoor permutations (TDP) was believed (and claimed) to imply oblivious transfer (OT). It was recently realized, however, that the commonly accepted general definition of TDP needs to be strengthened slightly in order to make the security proofs of TDP-based OT go through. In particular, Goldreich (Foundations of Cryptography - Volume 2) presented a TDP-based implementation of OT assuming an enhancement of the hardness assumption (of the collection). We present an implementation of OT based on any TDP, where we required that the permutation domains are polynomially dense in the set of all strings of a particular length.
Submitted to the Feinberg Graduate School of the Weizmann Institute of Science, January 2004.
Available: the thesis (in PS file).
Back to Oded Goldreich's homepage.