A new method for computational private information retrieval

Tillem, Gamze and Savaş, Erkay and Kaya, Kamer (2017) A new method for computational private information retrieval. Computer Journal, 60 (8). pp. 1238-1250. ISSN 0010-4620 (Print) 1460-2067 (Online)

[thumbnail of bxx025.pdf] PDF
bxx025.pdf
Restricted to Repository staff only

Download (863kB) | Request a copy

Abstract

Lipmaa's Computational Private Information Retrieval (CPIR) protocol is probably the most bandwidth efficient method in the literature, although its computational complexity is a limiting factor for practical applications as it is based on expensive public key operations. Utilizing binary decision diagrams (Bdd) and the Damgård–Jurik cryptosystem, Lipmaa's CPIR performs three modular exponentiation operations per internal node in Bdd. In this paper, we present a new CPIR protocol, which reduces the number of exponentiation operations to 1 per first-level internal nodes and 2 per other internal nodes of the Bdd. For 1024-bit exponents (i.e. 80-bit security level) and 32 768 items, when compared with the fastest parallel implementation in the literature on four cores, reducing the number of exponentiations yields a 1.22× speedup and the multi-exponentiation technique adds 2.23× more on top of that. Overall, when combined, reducing the number of exponentiations, multi-exponentiation, parallelization on four cores and the hybrid approach can provide more than 300× speedup compared to the sequential implementation of the original method.
Item Type: Article
Uncontrolled Keywords: number theoretic private information retrieval, security, privacy, parallel algorithms
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: Kamer Kaya
Date Deposited: 23 Aug 2017 15:42
Last Modified: 26 Apr 2022 09:47
URI: https://research.sabanciuniv.edu/id/eprint/33002

Actions (login required)

View Item
View Item