On the Feasibility of Extending Oblivious Transfer

Download Now Date Added: Jun 2012
Format: PDF

Oblivious transfer is one of the most basic and important building blocks in cryptography. As such, understanding its cost is of prime importance. Beaver (STOC 1996) showed that it is possible to obtain poly(n) oblivious transfers given only n actual oblivious transfer calls and using one-way functions, where n is the security parameter. In addition, the author showed that it is impossible to extend oblivious transfer information theoretically. The notion of extending oblivious transfer is important theoretically (to understand the complexity of computing this primitive) and practically (since oblivious transfers can be expensive and thus extending them using only one-way functions is very attractive).