Cryptology ePrint Archive: Report 2009/395

First CPIR Protocol with Data-Dependent Computation

Helger Lipmaa

Abstract: We design a new $(n, 1)$-CPIR protocol $\mathsf{BddCpir}$ for $\ell$-bit strings as a combination of a noncryptographic (BDD-based) data structure and a more basic cryptographic primitive (communication-efficient $(2, 1)$-CPIR). $\mathsf{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 $\ell$, $\mathsf{BddCpir}$ is guaranteed to have simultaneously log-squared communication and sublinear online computation, and (b) $\mathsf{BddCpir}$ can handle huge but sparse matrices, common in data-mining applications, significantly more efficiently compared to all previous protocols. The security of $\mathsf{BddCpir}$ can be based on the well-known Decisional Composite Residuosity assumption

Category / Keywords: cryptographic protocols / Binary decision diagram, computationally-private information retrieval, privacy-preserving data mining, sublinear communication

Publication Info: ICISC 2009

Date: received 12 Aug 2009, last revised 20 Jan 2010

Contact author: lipmaa at research cyber ee

Available formats: PDF | BibTeX Citation

Note: This corresponds to the final, published version of the paper. (Note that the title has changed.)

Version: 20100120:163052 (All versions of this report)

Discussion forum: Show discussion | Start new discussion