Advertisement
Published in:
2005 | OriginalPaper | Chapter
Single-Database Private Information Retrieval with Constant Communication Rate
Authors : Craig Gentry, Zulfikar Ramzan
Published in: Automata, Languages and Programming
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We present a single-database private information retrieval (PIR) scheme with communication complexity
${\mathcal O}(k+d)$
, where
k
≥ log
n
is a security parameter that depends on the database size
n
and
d
is the bit-length of the retrieved database block. This communication complexity is better asymptotically than previous single-database PIR schemes. The scheme also gives improved performance for practical parameter settings whether the user is retrieving a single bit or very large blocks. For large blocks, our scheme achieves a constant “rate” (e.g., 0.2), even when the user-side communication is very low (e.g., two 1024-bit numbers). Our scheme and security analysis is presented using general groups with hidden smooth subgroups; the scheme can be instantiated using composite moduli, in which case the security of our scheme is based on a simple variant of the “Φ-hiding” assumption by Cachin, Micali and Stadler [2].