Bandwidth-optimized parallel private information retrieval

Ünal, Ecem and Savaş, Erkay (2014) Bandwidth-optimized parallel private information retrieval. In: Proceedings of the 7th International Conference on Security of Information and Networks, SIN '14, Glasgow, UK (Accepted/In Press)

PDF - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader


We present improved and parallel versions of Lipmaa’s computationally-private information retrieval (CPIR) protocol based on a additively-homomorphic cryptosystem. Lipmaa’s original CPIR utilizes binary decision diagrams, in which non-sink nodes have two children nodes and the data items to be retrieved are placed in the sink nodes. In our scheme, we employ, instead, quadratic and octal trees, where nonsink nodes have four and eight child nodes, respectively. Using other tree forms, which does not change the asymptotic complexity, results in shallow trees by which we can obtain an implementation that is an order of magnitude faster than the original scheme. We also present a non-trivial parallel algorithm that takes advantage of shared-memory multi-core architectures. Finally, our scheme proves to be highly efficient in terms of bandwidth requirement, the amount of data being exchanged in a run of the CPIR protocol.

Item Type:Papers in Conference Proceedings
Subjects:Q Science > QA Mathematics > QA075 Electronic computers. Computer science
ID Code:25177
Deposited By:Erkay Savaş
Deposited On:07 Dec 2014 20:34
Last Modified:07 Dec 2014 20:34

Repository Staff Only: item control page