Cryptology ePrint Archive: Report 2004/036

Single Database Private Information Retrieval with Logarithmic Communication

Yan-Cheng Chang

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

Category / Keywords: cryptographic protocols /

Date: received 10 Feb 2004

Contact author: ycchang at eecs harvard edu

Available formats: Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20040216:095052 (All versions of this report)

Discussion forum: Show discussion | Start new discussion