The bounded storage model, introduced by Maurer, is an alternative to the standard complexity based model for cryptography. In contrast to the complexity based model, the bounded storage model assumes that the adversary is space-bounded, and provides provable information-theoretic security by employing a public random string R whose length exceeds the space bound. Security is guaranteed against a malicious adversary who remembers almost all information about R, while an honest party is only required to store a small fraction of R. Oblivious transfer is a fundamental cryptographic primitive on which many two-party and multi-party cryptographic protocols can be based. It involves two parties, Alice who has two secrets s_0 and s_1, and Bob who has a secret bit b. Roughly speaking, in a secure oblivious transfer protocol, Alice sends s_0 and s_1 to Bob in such a way that (1) Bob receives s_b but learns nothing about the other secret, and (2) Alice learns nothing about b. We construct a 5-round protocol for oblivious transfer in the bounded storage model. This improves on previous works that required polynomially many rounds. Our protocol also significantly improves upon the previous ones in terms of total bit communication complexity. The main ingredients of our construction are powerful tools from pseudo randomness, an area that is concerned with generating "random looking" objects with no or little randomness. In particular, our construction uses randomness extractors, averaging samplers, and almost t-wise independent permutations. This talk will be self-contained, and assume no previous knowledge in cryptography and pseudo randomness. This is joint work with Danny Harnik, Alon Rosen and Ronen Shaltiel.
