Paper 2017/1068
Frequency-smoothing encryption: preventing snapshot attacks on deterministically-encrypted data
Marie-Sarah Lacharité and Kenneth G. Paterson
Abstract
Naveed, Kamara, and Wright (CCS 2015) applied classical frequency analysis to carry out devastating inference attacks on databases in which the columns are encrypted with deterministic and order-preserving encryption. In this paper, we propose another classical technique, homophonic encoding, as a means to combat these attacks. We introduce and develop the concept of frequency-smoothing encryption (FSE) which provably prevents inference attacks in the snapshot attack model, wherein the adversary obtains a static snapshot of the complete encrypted database, while preserving the ability to efficiently make encrypted queries to the database. We provide provably secure constructions for FSE schemes, and we empirically assess their security for concrete parameters by evaluating them against real data. We show that frequency analysis attacks (and optimal generalisations of them for the FSE setting) no longer succeed. Finally, we discuss extending our schemes to take advantage of the full generality and power of our stateful FSE framework.
Metadata
- Available format(s)
- Publication info
- Preprint. MINOR revision.
- Keywords
- encrypted databasesnapshot attackinference attackfrequency analysisdeterministic encryptionhomophonic encodingfrequency-smoothing encryption
- Contact author(s)
- marie-sarah lacharite 2015 @ rhul ac uk
- History
- 2018-02-23: revised
- 2017-11-10: received
- See all versions
- Short URL
- https://ia.cr/2017/1068
- License
-
CC BY