# Oblivious Transfer with a Memory-Bounded Receiver

## Christian Cachin and Claude Cr{é}peau and Julien Marcil

```
```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 $ q(n^{2-2 a})$ for
some $ a<\frac{1}{2}$, when a random string of size $N=n^{2- a- b}$ is
broadcast, for $ a> b>0$, whereas a malicious receiver can have up to $ g N$
bits of memory for any $ g<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. NOVY98.