On acceleration and scalability of number theoretic private information retrieval

Ünal, Ecem and Savaş, Erkay (2016) On acceleration and scalability of number theoretic private information retrieval. IEEE Transactions on Parallel & Distributed Systems, 27 (6). pp. 1727-1741. ISSN 1045-9219 (Print) 1558-2183 (Online)

This is the latest version of this item.

[img]PDF - Registered users only - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader

Official URL: http://dx.doi.org/10.1109/TPDS.2015.2456021


We present scalable and parallel versions of Lipmaa’s computationally-private information retrieval (CPIR) scheme [20], which provides log-squared communication complexity. In the proposed schemes, instead of binary decision diagrams utilized in the original CPIR, we employ an octal tree based approach, in which non-sink nodes have eight child nodes. Using octal trees offers two advantages: i) a serial implementation of the proposed scheme in software is faster than the original scheme and ii) its bandwidth usage becomes less than the original scheme when the number of items in the data set is moderately high (e.g., 4,096 for 80-bit security level using Damga rd-Jurik cryptosystem). In addition, we present a highly-optimized parallel algorithm for shared-memory multi-core/processor architectures, which minimizes the number of synchronization points between the cores.We show that the parallel implementation is about 50 times faster than the serial implementation for a data set with 4,096 items on an eight-core machine. Finally, we propose a hybrid algorithm that scales the CPIR scheme to larger data sets with small overhead in bandwidth complexity. We demonstrate that the hybrid scheme based on octal trees can lead to more than two orders of magnitude faster parallel implementations than serial implementations based on binary trees. Comparison with the original as well as the other schemes in the literature reveals that our scheme is the best in terms of bandwidth requirement.

Item Type:Article
Uncontrolled Keywords:Number theoretic private information retrieval; security; privacy; parallel algorithms
Subjects:Q Science > QA Mathematics > QA075 Electronic computers. Computer science
Q Science > QA Mathematics > QA076 Computer software
ID Code:30192
Deposited By:Erkay Savaş
Deposited On:12 Nov 2016 12:31
Last Modified:12 Nov 2016 12:31

Available Versions of this Item

Repository Staff Only: item control page