Paper 2008/429
Public-Key Encryption with Efficient Amortized Updates
Nishanth Chandran, Rafail Ostrovsky, and William E. Skeith III
Abstract
Searching and modifying public-key encrypted data (without having the decryption key) has received a lot of attention in recent literature. In this paper we re-visit this important problem and achieve much better amortized communication-complexity bounds. Our solution resolves the main open question posed by Boneh at al., \cite{BKOS07}.
First, we consider the following much simpler to state problem (which turns out to be central for the above): A server holds a copy of Alice's database that has been encrypted under Alice's public key. Alice would like to allow other users in the system to replace a
bit of their choice in the server's database by communicating directly with the server, despite other users not having Alice's private key. However, Alice requires that the server should not know
which bit was modified. Additionally, she requires that the
modification protocol should have ``small" communication complexity
(sub-linear in the database size). This task is referred to as
private database modification, and is a central tool in building a more general protocol for modifying and searching over public-key encrypted data with small communication complexity. The problem was first considered by Boneh at al., \cite{BKOS07}. The protocol of \cite{BKOS07} to modify
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Published elsewhere. Unknown where it was published
- Keywords
- public key encryptionPIRprivate database modificationcommunication complexityexpander graphs
- Contact author(s)
- nishanth @ cs ucla edu
- History
- 2008-10-08: received
- Short URL
- https://ia.cr/2008/429
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2008/429, author = {Nishanth Chandran and Rafail Ostrovsky and William E. Skeith III}, title = {Public-Key Encryption with Efficient Amortized Updates}, howpublished = {Cryptology {ePrint} Archive, Paper 2008/429}, year = {2008}, url = {https://eprint.iacr.org/2008/429} }