Paper 2008/140

Reducing Complexity Assumptions for Oblivious Transfer

K. Y. Cheong and Takeshi Koshiba


Reducing the minimum assumptions needed to construct various cryptographic primitives is an important and interesting task in theoretical cryptography. Oblivious Transfer, one of the most basic cryptographic building blocks, is also studied under this scenario. Reducing the minimum assumptions for Oblivious Transfer seems not an easy task, as there are a few impossibility results under black-box reductions. Until recently, it is widely believed that Oblivious Transfer can be constructed with trapdoor permutations but not trapdoor functions in general. In this paper, we enhance previous results and show one Oblivious Transfer protocol based on a collection of trapdoor functions with some extra properties. We also provide reasons for adding the extra properties and argue that the assumptions in the protocol are nearly minimum.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Unknown where it was published
oblivious transfertrapdoor one-way functions
Contact author(s)
kaiyuen @ tcs ics saitama-u ac jp
2008-03-31: received
Short URL
Creative Commons Attribution


      author = {K. Y.  Cheong and Takeshi Koshiba},
      title = {Reducing Complexity Assumptions for Oblivious Transfer},
      howpublished = {Cryptology ePrint Archive, Paper 2008/140},
      year = {2008},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.