Paper 2006/186
Deterministic and Efficiently Searchable Encryption
Mihir Bellare, Alexandra Boldyreva, and Adam O'Neill
Abstract
We present as-strong-as-possible definitions of privacy, and constructions achieving them, for public-key encryption schemes where the encryption algorithm is \textit{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.
Metadata
- Available format(s)
-
PDF
- Publication info
- Published elsewhere. Preliminary version appears in CRYPTO 2007
- Keywords
- Public-key encryptiondeterministic encryptionsearchable encryptiondatabase security
- Contact author(s)
- amoneill @ cc gatech edu
- History
- 2008-04-10: last of 36 revisions
- 2006-06-19: received
- See all versions
- Short URL
- https://ia.cr/2006/186
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2006/186,
author = {Mihir Bellare and Alexandra Boldyreva and Adam O'Neill},
title = {Deterministic and Efficiently Searchable Encryption},
howpublished = {Cryptology ePrint Archive, Paper 2006/186},
year = {2006},
note = {\url{https://eprint.iacr.org/2006/186}},
url = {https://eprint.iacr.org/2006/186}
}
