Cryptology ePrint Archive: Report 2008/140

Reducing Complexity Assumptions for Oblivious Transfer

K.Y. Cheong and Takeshi Koshiba

Abstract: 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.

Category / Keywords: cryptographic protocols / oblivious transfer, trapdoor one-way functions

Date: received 29 Mar 2008

Contact author: kaiyuen at tcs ics saitama-u ac jp

Available format(s): PDF | BibTeX Citation

Version: 20080331:141800 (All versions of this report)

Short URL: ia.cr/2008/140

Discussion forum: Show discussion | Start new discussion