First CPIR Protocol with Data-Dependent Computation.
Helger Lipmaa · 2009
Abstract We design a new (n, 1)-CPIR protocol BddCpir for ℓ-bit strings as a combination of a noncryptographic (BDD-based) data structure and a more basic cryptographic primitive (communication-efficient (2, 1)-CPIR). BddCpir is the first CPIR protocol where server’s online computation depends substantially on the concrete database. We then show that (a) for reasonably small values of ℓ, BddCpir is guaranteed to have simultaneously log-squared communication and sublinear online computation, and (b) BddCpir can handle huge but sparse matrices, common in data-mining applications, significantly more efficiently compared to all previous protocols. The security of BddCpir can be based on the well-known Decisional Composite Residuosity assumption.