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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.