## First CPIR Protocol with Data-Dependent Computation

Helger Lipmaa. First CPIR Protocol with Data-Dependent Computation. In Donghoon Lee and Seokhie Hong, editors, ICISC 2009, volume 5984 of Lecture Notes in Computer Science, pages 193--210, Seoul, Korea, December 2--4, 2009. Springer, Heidelberg.

File: [.pdf (241 KB)] pdf recommended.

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.

Keywords: Binary decision diagram, computationally-private information retrieval, privacy-preserving data mining, sublinear communication.

Comment: Also available from http://eprint.iacr.org/2009/395.

Authors:

Page by Helger Lipmaa. Send your inqueries to <helger.lipmaa>gmail.com.