Welcome to the resource topic for 2004/036
Title:
Single Database Private Information Retrieval with Logarithmic Communication
Authors: 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.
ePrint: https://eprint.iacr.org/2004/036
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .