Oblivious transfer with a memory-bounded receiver

We propose a protocol for oblivious transfer that is unconditionally secure under the sole assumption that the memory size of the receiver is bounded. The model assumes that a random bit string slightly larger than the receiver's memory is broadcast (either by the sender or by a third party). In our construction, both parties need memory of size in theta(n(2-2 alpha)) for some alpha < 1/2, when a random string of size N = n(2-alpha-beta) is broadcast, for alpha > beta > 0, whereas a malicious receiver carl have up to gamma N bits of memory for ang gamma < 1. In the course of our analysis, we provide a direct study of an interactive hashing protocol closely related to that of Naor et al. [27].