Efficient k-out-of-n oblivious transfer schemes

Cheng Kang Chu*, Wen-Guey Tzeng

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

17 Scopus citations


Oblivious transfer is an important cryptographic protocol in various security applications. For example, in on-line transactions, a k-out-of-n oblivious transfer scheme allows a buyer to privately choose k out of n digital goods from a merchant without learning information about other n - k goods. In this paper, we propose several efficient two-round k-out-of-n oblivious transfer schemes, in which the receiver R sends O(k) messages to the sender S, and S sends O(n) messages back to R. The schemes provide unconditional security for either sender or receiver. The computational security for the other side is based on the Decisional Diffie-Hellman (DDH) or Chosen-Target Computational Diffie-Hellman (CT-CDH) problems. Our schemes have the nice property of universal parameters, that is, each pair of R and S need not hold any secret before performing the protocol. The system parameters can be used by all senders and receivers without any trapdoor specification. In some cases, our OT n k schemes are the most efficient ones in terms of the communication cost, either in rounds or the number of messages. Moreover, one of our schemes is extended to an adaptive oblivious transfer scheme. In that scheme, S sends O(n) messages to R in one round in the commitment phase. For each query of R, only O(1) messages are exchanged and O(1) operations are performed. The preliminary version of this paper was published at PKC '05 [Chu and Tzeng 2005].

Original languageEnglish
Pages (from-to)397-415
Number of pages19
JournalJournal of Universal Computer Science
Issue number3
StatePublished - 2 Jun 2008


  • Electronic commerce
  • Oblivious transfer
  • Privacy protection

Fingerprint Dive into the research topics of 'Efficient k-out-of-n oblivious transfer schemes'. Together they form a unique fingerprint.

Cite this