UCL logo

UCL Discovery

UCL home » Library Services » Electronic resources » UCL Discovery

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

Groth, J; Kiayias, A; Lipmaa, H; (2010) Multi-query Computationally-Private Information Retrieval with Constant Communication Rate. In: Nguyen, PQ and Pointcheval, D, (eds.) PUBLIC KEY CRYPTOGRAPHY - PKC 2010, PROCEEDINGS. (pp. 107 - 123). SPRINGER-VERLAG BERLIN

Full text not available from this repository.

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 CRIR protocol allows a client to extract in records of a database containing n l-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 CM problem optimally up to a constant factor.

Type:Proceedings paper
Title:Multi-query Computationally-Private Information Retrieval with Constant Communication Rate
Event:13th International Conference on Practice and Theory in Public Key Cryptograhy
Location:Ecole Normale Superieure, Paris, FRANCE
Dates:2010-05-26 - 2010-05-28
ISBN-13:978-3-642-13012-0
Keywords:Computationally private information retrieval, multi-query CPIR, lower bound on communication
UCL classification:UCL > School of BEAMS > Faculty of Engineering Science > Computer Science

Archive Staff Only: edit this record