Paper 2015/1158 Original: eprint.iacr.org/2015/1158 ↗
A note on the optimality of frequency analysis vs. $\ell_p$-optimization
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.
- History
- 2015-11-30: last updated
- 2015-11-30: published
- Short URL
- https://ia.cr/2015/1158
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}