Oblivious transfer with a memory-bounded receiver
Christian Cachin, Claude Crépeau, J. Marcil · 2002
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 /spl theta/(n/sup 2-2/spl alpha//) for some /spl alpha//spl beta/>0, whereas a malicious receiver can have up to /spl gamma/N bits of memory for any /spl gamma/<1. In the course of our analysis, we provide a direct study of an interactive hashing protocol closely related to that of M. Naor et al. (1998).