CryptoDB
Single Database Private Information Retrieval with Logarithmic Communication
Authors: | |
---|---|
Download: | |
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. |
BibTeX
@misc{eprint-2004-12012, title={Single Database Private Information Retrieval with Logarithmic Communication}, booktitle={IACR Eprint archive}, keywords={cryptographic protocols /}, url={http://eprint.iacr.org/2004/036}, note={ ycchang@eecs.harvard.edu 12459 received 10 Feb 2004}, author={Yan-Cheng Chang}, year=2004 }