title   
  

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)

[img]PDF - Repository staff only - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
842Kb

Official URL: http://dx.doi.org/10.1093/comjnl/bxx025

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
ID Code:33002
Deposited By:Kamer Kaya
Deposited On:23 Aug 2017 15:42
Last Modified:23 Aug 2017 15:42

Repository Staff Only: item control page