Paper 2004/036

Single Database Private Information Retrieval with Logarithmic Communication

Yan-Cheng Chang


In this paper, we study the problem of single database private information retrieval, and present schemes with only logarithmic server-side communication complexity. Previously the best result could only achieve polylogarithmic communication, and was based on certain less well-studied assumptions in number theory \cite{CMS99}. On the contrary, our construction is based on Paillier's cryptosystem \cite{P99}, which along with its variants have drawn extensive studies in recent cryptographic researches \cite{PP99,G00,CGGN01,DJ01,CGG02,CNS02,ST02,GMMV03,KT03}, and have many important applications (e.g., the Cramer-Shoup CCA2 encryption scheme in the standard model \cite{CS02}). Actually, our schemes can be directly used to implement $1$-out-of-$N$ {\em $\ell$-bit string} oblivious transfer with $O(\ell)$ sender-side communication complexity (against semi-honest receivers and malicious senders). Note the sender-side communication complexity is independent of $N$, the constant hidden in the big-$O$ notation is in fact small, and $\ell$ is unrestricted. Moreover, We also show a way to do communication balancing between the sender-side and the receiver-side. In addition, we show how to handle malicious receivers with small communication overheads, which itself is a non-trivial result.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Unknown where it was published
Contact author(s)
ycchang @ eecs harvard edu
2004-02-16: received
Short URL
Creative Commons Attribution


      author = {Yan-Cheng Chang},
      title = {Single Database Private Information Retrieval with Logarithmic Communication},
      howpublished = {Cryptology ePrint Archive, Paper 2004/036},
      year = {2004},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.