Paper 2007/351
A Linear Lower Bound on the Communication Complexity of Single-Server Private Information Retrieval
Iftach Haitner, Jonathan J. Hoch, and Gil Segev
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
Metadata
- Available format(s)
-
PDF PS
- Category
- Foundations
- Publication info
- Published elsewhere. TCC '08
- Keywords
- Black-Box ReductionsSingle-Server Private Information Retrieval
- Contact author(s)
- gil segev @ weizmann ac il
- History
- 2007-12-12: revised
- 2007-09-13: received
- See all versions
- Short URL
- https://ia.cr/2007/351
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2007/351, author = {Iftach Haitner and Jonathan J. Hoch and Gil Segev}, title = {A Linear Lower Bound on the Communication Complexity of Single-Server Private Information Retrieval}, howpublished = {Cryptology {ePrint} Archive, Paper 2007/351}, year = {2007}, url = {https://eprint.iacr.org/2007/351} }