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
Creative Commons Attribution
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.