Cryptology ePrint Archive: Report 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.

Category / Keywords: cryptanalysis

Date: received 30 Nov 2015, last revised 30 Nov 2015

Contact author: marie-sarah lacharite 2015 at rhul ac uk

Available format(s): PDF | BibTeX Citation

Version: 20151130:231150 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]