International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

A Linear Lower Bound on the Communication Complexity of Single-Server Private Information Retrieval

Authors:
Iftach Haitner
Jonathan J. Hoch
Gil Segev
Download:
URL: http://eprint.iacr.org/2007/351
Search ePrint
Search Google
Abstract: We study the communication complexity of single-server Private Information Retrieval (PIR) protocols that are based on fundamental cryptographic primitives in a black-box manner. In this setting, we establish a tight lower bound on the number of bits communicated by the server in any polynomially-preserving construction that relies on trapdoor permutations. More specifically, our main result states that in such constructions $\Omega(n)$ bits must be communicated by the server, where $n$ is the size of the server's database, and this improves the $\Omega(n / \log n)$ lower bound due to Haitner, Hoch, Reingold and Segev (FOCS '07). Therefore, in the setting under consideration, the naive solution in which the user downloads the entire database turns out to be optimal up to constant multiplicative factors. We note that the lower bound we establish holds for the most generic form of trapdoor permutations, including in particular enhanced trapdoor permutations. Technically speaking, this paper consists of two main contributions from which our lower bound is obtained. First, we derive a tight lower bound on the number of bits communicated by the sender during the commit stage of any black-box construction of a statistically-hiding bit-commitment scheme from a family of trapdoor permutations. This lower bound asymptotically matches the upper bound provided by the scheme of Naor, Ostrovsky, Venkatesan and Yung (CRYPTO '92). Second, we improve the efficiency of the reduction of statistically-hiding commitment schemes to low-communication single-server PIR, due to Beimel, Ishai, Kushilevitz and Malkin (STOC '99). In particular, we present a reduction that essentially preserves the communication complexity of the underlying single-server PIR protocol.
BibTeX
@misc{eprint-2007-13631,
  title={A Linear Lower Bound on the Communication Complexity of Single-Server Private Information Retrieval},
  booktitle={IACR Eprint archive},
  keywords={foundations / Black-Box Reductions, Single-Server Private Information Retrieval},
  url={http://eprint.iacr.org/2007/351},
  note={TCC '08 gil.segev@weizmann.ac.il 13859 received 5 Sep 2007, last revised 12 Dec 2007},
  author={Iftach Haitner and Jonathan J. Hoch and Gil Segev},
  year=2007
}