Paper 2017/1098

The Strength of Weak Randomization: Efficiently Searchable Encryption with Minimal Leakage

David Pouliot, Scott Griffy, and Charles V. Wright

Abstract

Efficiently searchable and easily deployable encryption schemes enable an untrusted, legacy service such as a relational database engine to perform searches over encrypted data. The ease with which such schemes can be deployed on top of existing services makes them especially appealing in operational environments where encryption is needed but it is not feasible to replace large infrastructure components like databases or document management systems. Unfortunately all previously known approaches for efficiently searchable encryption are vulnerable to inference attacks where an adversary can use knowledge of the distribution of the data to recover the plaintext with high probability. In this paper, we present the first efficiently searchable, easily deployable database encryption scheme that is provably secure against inference attacks even when used with real, low-entropy data. Ours is also the only efficiently searchable construction that provides any provable security for protecting multiple related attributes (columns) in the same database. Using this ESE construction as a building block, we give an efficient construction for performing range queries over encrypted data. We implemented our constructions in Haskell and used them to query encrypted databases of up to 10 million records. In experiments with a local Postgres database and with a Google Cloud Platform database, the response time for our encrypted queries is not excessively slower than for plaintext queries. With the use of parallel query processing, our encrypted queries can achieve similar and in some cases superior performance to queries on the plaintext.

Metadata
Available format(s)
PDF
Category
Applications
Publication info
Preprint. MINOR revision.
Keywords
efficiently searchable encryptionencrypted databases
Contact author(s)
cvwright @ cs pdx edu
History
2017-11-11: received
Short URL
https://ia.cr/2017/1098
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/1098,
      author = {David Pouliot and Scott Griffy and Charles V.  Wright},
      title = {The Strength of Weak Randomization: Efficiently Searchable Encryption with Minimal Leakage},
      howpublished = {Cryptology ePrint Archive, Paper 2017/1098},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/1098}},
      url = {https://eprint.iacr.org/2017/1098}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.