A new method for computational private information retrieval

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