Paper 2015/1158
A note on the optimality of frequency analysis vs. $\ell_p$-optimization
Marie-Sarah Lacharité and Kenneth G. Paterson
Abstract
Naveed, Kamara, and Wright's recent paper "Inference Attacks on Property-Preserving Encrypted Databases" (ACM-CCS 2015) evaluated four attacks on encrypted databases, such as those based on the design of CryptDB (Popa et al., SOSP 2011). Two of these attacks---frequency analysis and l_p-optimization---apply to deterministically encrypted columns when there is a publicly-available auxiliary data set that is "well-correlated" with the ciphertext column. In their experiments, frequency analysis performed at least as well as l_p-optimization for p=1, 2, and 3. We use maximum likelihood estimation to confirm their intuition and show that frequency analysis is an optimal cryptanalytic technique in this scenario.
Metadata
- Available format(s)
-
PDF
- Publication info
- Preprint. MINOR revision.
- Keywords
- cryptanalysis
- Contact author(s)
- marie-sarah lacharite 2015 @ rhul ac uk
- History
- 2015-11-30: last of 2 revisions
- 2015-11-30: received
- See all versions
- Short URL
- https://ia.cr/2015/1158
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2015/1158,
author = {Marie-Sarah Lacharité and Kenneth G. Paterson},
title = {A note on the optimality of frequency analysis vs. $\ell_p$-optimization},
howpublished = {Cryptology {ePrint} Archive, Paper 2015/1158},
year = {2015},
url = {https://eprint.iacr.org/2015/1158}
}
