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 DamgArd-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.22x speedup and the multi-exponentiation technique adds 2.23x 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 300x speedup compared to the sequential implementation of the original method.