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.

[thumbnail of article_05.pdf] PDF
Restricted to Registered users only

Download (627kB) | Request a copy


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
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Computer Science & Eng.
Faculty of Engineering and Natural Sciences
Depositing User: Erkay Savaş
Date Deposited: 12 Nov 2016 12:31
Last Modified: 12 Nov 2016 12:31
URI: https://research.sabanciuniv.edu/id/eprint/30192

Available Versions of this Item

Actions (login required)

View Item
View Item