Communication-efficient distributed oblivious transfer

Amos Beimel, Yeow Meng Chee, Huaxiong Wang, Liang Feng Zhang*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)


Distributed oblivious transfer (DOT) was introduced by Naor and Pinkas (2000) [31], and then generalized to (k,l)-DOT-(n1) by Blundo et al. (2007) [8] and Nikov et al. (2002) [34]. In the generalized setting, a (k,l)-DOT-(n1) allows a sender to communicate one of n secrets to a receiver with the help of l servers. Specifically, the transfer task of the sender is distributed among l servers and the receiver interacts with k out of the l servers in order to retrieve the secret he is interested in. The DOT protocols we consider in this work are information-theoretically secure. The known (k,l)-DOT-(n1) protocols require linear (in n) communication complexity between the receiver and servers. In this paper, we construct (k,l)-DOT-(n1) protocols which only require sublinear (in n) communication complexity between the receiver and servers. Our constructions are based on information-theoretic private information retrieval. In particular, we obtain both a specific reduction from (k,l)-DOT-(n1) to polynomial interpolation-based information-theoretic private information retrieval and a general reduction from (k,l)-DOT-(n1) to any information-theoretic private information retrieval. The specific reduction yields (t,τ)-private (k,l)-DOT-(n1) protocols of communication complexity O(n1 /⌋(k-τ-1)/t⌊) between a semi-honest receiver and servers for any integers t and τ such that 1≤t≤k-1 and 0≤τ≤k-1-t. The general reduction yields (t,τ)-private (k,l)-DOT-(n1) protocols which are as communication-efficient as the underlying private information retrieval protocols for any integers t and τ such that 1≤t≤k-2 and 0≤τ≤k-1-t.

Original languageEnglish
Pages (from-to)1142-1157
Number of pages16
JournalJournal of Computer and System Sciences
Issue number4
Publication statusPublished - Jul 2012


  • Communication complexity
  • Distributed oblivious transfer
  • Private information retrieval


Dive into the research topics of 'Communication-efficient distributed oblivious transfer'. Together they form a unique fingerprint.

Cite this