### 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.

Available format(s)
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
See all versions
Short URL
https://ia.cr/2015/1158

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},
note = {\url{https://eprint.iacr.org/2015/1158}},
url = {https://eprint.iacr.org/2015/1158}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.