A fast single server private information retrieval protocol with low communication cost

Changyu Dong, Liqun Chen

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

7 Citations (Scopus)
60 Downloads (Pure)

Abstract

Existing single server Private Information Retrieval (PIR) protocols are far from practical. To be practical, a single server PIR protocol has to be both communicationally and computationally efficient. In this paper, we present a single server PIR protocol that has low communication cost and is much faster than existing protocols. A major building block of the PIR protocol in this paper is a tree-based compression scheme, which we call folding/unfolding. This compression scheme enables us to lower the communication complexity to O(loglogn). The other major building block is the BGV fully homomorphic encryption scheme. We show how we design the protocol to exploit the internal parallelism of the BGV scheme. This significantly reduces the server side computational overhead and makes our protocol much faster than the existing protocols. Our protocol can be further accelerated by utilising hardware parallelism. We have built a prototype of the protocol. We report on the performance of our protocol based on the prototype and compare it with the current most efficient protocols.
Original languageEnglish
Title of host publicationComputer Security - ESORICS 2014
Subtitle of host publication19th European Symposium on Research in Computer Security, Wroclaw, Poland, September 7-11, 2014. Proceedings, Part I
EditorsMirosław Kutyłowski, Jaideep Vaidya
PublisherSpringer
Pages380-399
Number of pages20
ISBN (Print)9783319112022
DOIs
Publication statusPublished - 2014

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume8712
ISSN (Print)0302-9743

    Fingerprint

Keywords

  • private information retrieval
  • fully homomorphic encryption
  • privacy
  • information retrieval protocol

Cite this

Dong, C., & Chen, L. (2014). A fast single server private information retrieval protocol with low communication cost. In M. Kutyłowski, & J. Vaidya (Eds.), Computer Security - ESORICS 2014: 19th European Symposium on Research in Computer Security, Wroclaw, Poland, September 7-11, 2014. Proceedings, Part I (pp. 380-399). (Lecture Notes in Computer Science; Vol. 8712). Springer. https://doi.org/10.1007/978-3-319-11203-9_22