A New Method for Computational Private Information Retrieval. (22nd March 2017)

• Record Type: Journal Article
• Authors: Tillem, Gamze; Savaş, Erkay; Kaya, Kamer
• Is Part Of: Computer journal. Volume 60:Number 8(2017)
• Page Start: 1238
• Page End: 1250
• Publication Date: 2017-03-22
• Subjects: number theoretic private information retrieval -- security -- privacy -- parallel algorithms; Computers -- Periodicals; 005.1
• DOI: 10.1093/comjnl/bxx025
• Languages: English
• ISSNs: 0010-4620

Abstract

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.