Oblivious Transfer in the Bounded Storage Model

Building on a previous important work of Cachin, Crépeau, and Marcil [15], we present a provably secure and more efficient protocol for (2₁)-Oblivious Transfer with a storage-bounded receiver. A public random string of n bits long is employed, and the protocol is secure against any receiver who can store γn bits, γ < 1. Our work improves the work of CCM [15] in two ways. First, the CCM protocol requires the sender and receiver to store O(nc) bits, c ~ 2/3. We give a similar but more efficient protocol that just requires the sender and receiver to store O(√kn) bits, where k is a security parameter. Second, the basic CCM Protocol was proved in [15] to guarantee that a dishonest receiver who can store O(n) bits succeeds with probability at most O(n™d), d ~ 1/3, although repitition of the protocol can make this probability of cheating exponentially small [20]. Combining the methodologies of [24] and [15], we prove that in our protocol, a dishonest storage-bounded receiver succeeds with probability only 2™O(k), without repitition of the protocol. Our results answer an open problem raised by CCM in the affirmative.