Helger Lipmaa's publications

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

Jens Groth, Aggelos Kiayias and Helger Lipmaa. Multi-Query Computationally-Private Information Retrieval with Constant Communication Rate. In Phong Q. Nguyen and David Pointcheval, editors, PKC 2010, volume 6056 of Lecture Notes in Computer Science, pages 107--123, Paris, France, May 26--28, 2010. Springer, Heidelberg.

File: [.pdf (231 KB)] pdf recommended.


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 eetrieval (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 $ $\ell$-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 thus we settle the multiquery CPIR problem optimally up to a constant factor..

Keywords: Computationally private information retrieval, multi-query CPIR, lower bound on communication.



Page by Helger Lipmaa. Send your inqueries to <helger.lipmaa><at>gmail.com.