Paper 2009/395 Original: eprint.iacr.org/2009/395 ↗
First CPIR Protocol with Data-Dependent Computation
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
Metadata
- Available format(s)
PDF- Category
- Cryptographic protocols
- Publication info
- Preprint.
- History
- 2010-01-20: last updated
- 2009-08-15: published
- Short URL
- https://ia.cr/2009/395
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}