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

Changyu Dong; Liqun Chen

doi:10.1007/978-3-319-11203-9_22

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

Changyu Dong, Liqun Chen

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution book

28 Citations (Scopus)

95 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 language	English
Title of host publication	Computer Security - ESORICS 2014
Subtitle of host publication	19th European Symposium on Research in Computer Security, Wroclaw, Poland, September 7-11, 2014. Proceedings, Part I
Editors	Mirosław Kutyłowski, Jaideep Vaidya
Publisher	Springer
Pages	380-399
Number of pages	20
ISBN (Print)	9783319112022
DOIs	https://doi.org/10.1007/978-3-319-11203-9_22
Publication status	Published - 2014

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	8712
ISSN (Print)	0302-9743

Keywords

private information retrieval
fully homomorphic encryption
privacy
information retrieval protocol

Access to Document

10.1007/978-3-319-11203-9_22

Dong-Chen-ESORICS2014-single-server-private-information-retrieval-protocolSubmitted manuscript, 452 KB

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

Dong, Changyu ; Chen, Liqun. / A fast single server private information retrieval protocol with low communication cost. Computer Security - ESORICS 2014: 19th European Symposium on Research in Computer Security, Wroclaw, Poland, September 7-11, 2014. Proceedings, Part I. editor / Mirosław Kutyłowski ; Jaideep Vaidya. Springer, 2014. pp. 380-399 (Lecture Notes in Computer Science).

@inproceedings{7d1ada39b89b46459ea2e2e56de5f0e0,

title = "A fast single server private information retrieval protocol with low communication cost",

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.",

keywords = "private information retrieval, fully homomorphic encryption, privacy, information retrieval protocol",

author = "Changyu Dong and Liqun Chen",

note = "This is a pre-print of an article accepted to Computer Security - ESORICS 2014. The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-319-11203-9\_22",

year = "2014",

doi = "10.1007/978-3-319-11203-9\_22",

language = "English",

isbn = "9783319112022",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "380--399",

editor = "Miros{\l}aw Kuty{\l}owski and Jaideep Vaidya",

booktitle = "Computer Security - ESORICS 2014",

address = "Switzerland",

}

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. Lecture Notes in Computer Science, vol. 8712, Springer, pp. 380-399. https://doi.org/10.1007/978-3-319-11203-9_22

A fast single server private information retrieval protocol with low communication cost. / Dong, Changyu; Chen, Liqun.
Computer Security - ESORICS 2014: 19th European Symposium on Research in Computer Security, Wroclaw, Poland, September 7-11, 2014. Proceedings, Part I. ed. / Mirosław Kutyłowski; Jaideep Vaidya. Springer, 2014. p. 380-399 (Lecture Notes in Computer Science; Vol. 8712).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution book

TY - GEN

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

AU - Dong, Changyu

AU - Chen, Liqun

N1 - This is a pre-print of an article accepted to Computer Security - ESORICS 2014. The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-319-11203-9_22

PY - 2014

Y1 - 2014

N2 - 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.

AB - 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.

KW - private information retrieval

KW - fully homomorphic encryption

KW - privacy

KW - information retrieval protocol

UR - http://link.springer.com/chapter/10.1007%2F978-3-319-11203-9_22

U2 - 10.1007/978-3-319-11203-9_22

DO - 10.1007/978-3-319-11203-9_22

M3 - Conference contribution book

SN - 9783319112022

T3 - Lecture Notes in Computer Science

SP - 380

EP - 399

BT - Computer Security - ESORICS 2014

A2 - Kutyłowski, Mirosław

A2 - Vaidya, Jaideep

PB - Springer

ER -

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

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

Abstract

Publication series

Keywords

Access to Document

Other files and links

Fingerprint

Cite this