Multi-query Computationally-Private Information Retrieval with Constant Communication Rate

Jens Groth, Aggelos Kiayias, Helger Lipmaa

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

A fundamental privacy problem in the client-server setting is the retrieval of a record from a database maintained by a server so that the computationally bounded server remains oblivious to the index of the record retrieved while the overall communication between the two parties is smaller than the database size. This problem has been extensively studied and is known as computationally private information retrieval (CPIR). In this work we consider a natural extension of this problem: a multi-query CPIR protocol allows a client to extract m records of a database containing n ℓ-bit records. We give an information-theoretic lower bound on the communication of any multi-query information retrieval protocol. We then design an efficient non-trivial multi-query CPIR protocol that matches this lower bound. This means we settle the multi-query CPIR problem optimally up to a constant factor.
Original languageEnglish
Title of host publicationPublic Key Cryptography - PKC 2010
Subtitle of host publication13th International Conference on Practice and Theory in Public Key Cryptography, Paris, France, May 26-28, 2010. Proceedings
PublisherSpringer
Pages107-123
Number of pages17
ISBN (Electronic)978-3-642-13013-7
ISBN (Print)978-3-642-13012-0
DOIs
Publication statusPublished - 2010

Publication series

NameLecture Notes in Computer Science (LNCS)
PublisherSpringer Berlin Heidelberg
Volume6056
ISSN (Print)0302-9743

Fingerprint

Dive into the research topics of 'Multi-query Computationally-Private Information Retrieval with Constant Communication Rate'. Together they form a unique fingerprint.

Cite this