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)

[thumbnail of cpir_parallel.pdf] PDF

Download (146kB)


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
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Computer Science & Eng.
Faculty of Engineering and Natural Sciences
Depositing User: Erkay Savaş
Date Deposited: 07 Dec 2014 20:34
Last Modified: 26 Apr 2022 09:16

Actions (login required)

View Item
View Item