# Information Security and Cryptography Research Group

## Oblivious Transfer with a Memory-Bounded Receiver

### Christian Cachin, Claude Crépeau, and Julien Marcil

Proceedings of the 39th Annual Symposium on Foundations of Computer Science — FOCS '98, IEEE, pp. 493–502, Nov 1998.

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.

## BibTeX Citation

@inproceedings{CaCrMa98,
author       = {Christian Cachin and Claude Crépeau and Julien Marcil},
title        = {Oblivious Transfer with a Memory-Bounded Receiver},
booktitle    = {Proceedings of the 39th Annual Symposium on Foundations of Computer Science --- FOCS~'98},
pages        = {493--502},
year         = {1998},
month        = {11},
publisher    = {IEEE},
}