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

Dong, Changyu and Chen, Liqun; Kutyłowski, Mirosław and Vaidya, Jaideep, eds. (2014) A fast single server private information retrieval protocol with low communication cost. In: Computer Security - ESORICS 2014. Lecture Notes in Computer Science . Springer, pp. 380-399. ISBN 9783319112022 (https://doi.org/10.1007/978-3-319-11203-9_22)

[thumbnail of Dong-Chen-ESORICS2014-single-server-private-information-retrieval-protocol] PDF. Filename: Dong_Chen_ESORICS2014_single_server_private_information_retrieval_protocol.pdf
Preprint
Download (462kB)

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.

ORCID iDs

Dong, Changyu ORCID logoORCID: https://orcid.org/0000-0002-8625-0275 and Chen, Liqun; Kutyłowski, Mirosław and Vaidya, Jaideep
CORE (COnnecting REpositories)