Paper 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
Note: This corresponds to the final, published version of the paper. (Note that the title has changed.)
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Published elsewhere. ICISC 2009
- Keywords
- Binary decision diagramprivacy-preserving data miningsublinear communication
- Contact author(s)
- lipmaa @ research cyber ee
- History
- 2010-01-20: revised
- 2009-08-15: received
- See all versions
- Short URL
- https://ia.cr/2009/395
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2009/395,
author = {Helger Lipmaa},
title = {First {CPIR} Protocol with Data-Dependent Computation},
howpublished = {Cryptology {ePrint} Archive, Paper 2009/395},
year = {2009},
url = {https://eprint.iacr.org/2009/395}
}
