[BBO07] Deterministic and Efficiently Searchable Encryption
Authors: Mihir Bellare, Alexandra Boldyreva, Adam O’Neill | Venue: CRYPTO 2007 | Source
Abstract
We present as-strong-as-possible definitions of privacy, and constructions achieving them, for public-key encryption schemes where the encryption algorithm is deterministic. We obtain as a consequence database encryption methods that permit fast (i.e. sub-linear, and in fact logarithmic, time) search while provably providing privacy that is as strong as possible subject to this fast search constraint. One of our constructs, called RSA-DOAEP, has the added feature of being length preserving, so that it is the first example of a public-key cipher. We generalize this to obtain a notion of efficiently-searchable encryption schemes which permit more flexible privacy to search-time trade-offs via a technique called bucketization. Our results answer much-asked questions in the database community and provide foundations for work done there.
BibTeX
@Inproceedings{C:BelBolONe07,
author = {Mihir Bellare and Alexandra Boldyreva and Adam {O'Neill}},
title = {Deterministic and Efficiently Searchable Encryption},
pages = {535--552},
editor = {Alfred Menezes},
booktitle = {Advances in Cryptology -- {CRYPTO}~2007},
volume = {4622},
series = {Lecture Notes in Computer Science},
address = {Santa Barbara, CA, USA},
month = {aug~19--23},
publisher = {Springer Berlin Heidelberg, Germany},
year = {2007},
doi = {10.1007/978-3-540-74143-5_30},
}