Paper 2012/333

On the Feasibility of Extending Oblivious Transfer

Yehuda Lindell and Hila Zarosim

Abstract

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, he 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). Despite its importance, very little is known about the feasibility of extending oblivious transfer, beyond the fact that it is impossible information theoretically. Specifically, it is not known whether or not one-way functions are actually necessary for extending oblivious transfer, whether or not it is possible to extend oblivious transfers with adaptive security, and whether or not it is possible to extend oblivious transfers when starting with just a few. In this paper, we address these questions and provide almost complete answers to all of them. We show that the existence of any oblivious transfer extension protocol with security for static semi-honest adversaries implies one-way functions, that an oblivious transfer extension protocol with adaptive security implies oblivious transfer with static security, and that the existence of an oblivious transfer extension protocol from only $O(\log n)$ oblivious transfers implies oblivious transfer itself.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Unknown where it was published
Keywords
oblivious transferextending oblivious transferfeasibility studyadaptive security
Contact author(s)
zarosih @ cs biu ac il
History
2013-01-23: revised
2012-06-22: received
See all versions
Short URL
https://ia.cr/2012/333
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/333,
      author = {Yehuda Lindell and Hila Zarosim},
      title = {On the Feasibility of Extending Oblivious Transfer},
      howpublished = {Cryptology ePrint Archive, Paper 2012/333},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/333}},
      url = {https://eprint.iacr.org/2012/333}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.