Anzeige
Erschienen in:
2005 | OriginalPaper | Buchkapitel
Single-Database Private Information Retrieval with Constant Communication Rate
verfasst von : Craig Gentry, Zulfikar Ramzan
Erschienen in: Automata, Languages and Programming
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. 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].