Paper 2017/1068

Frequency-smoothing encryption: preventing snapshot attacks on deterministically encrypted data

Marie-Sarah Lacharité and Kenneth G. Paterson


Statistical analysis of ciphertexts has been recently used to carry out devastating inference attacks on deterministic encryption (Naveed, Kamara, and Wright, CCS 2015), order-preserving/revealing encryption (Grubbs et al., S&P 2017), and searchable encryption (Pouliot and Wright, CCS 2016). At the heart of these inference attacks is classical frequency analysis. In this paper, we propose and evaluate another classical technique, homophonic encoding, as a means to combat these attacks. We introduce and develop the concept of frequency-smoothing encryption (FSE) which provably prevents inference attacks in the snapshot attack model, wherein the adversary obtains a static snapshot of the encrypted data, while preserving the ability to efficiently and privately make point queries. We provide provably secure constructions for FSE schemes, and we empirically assess their security for concrete parameters by evaluating them against real data. We show that frequency analysis attacks (and optimal generalisations of them for the FSE setting) no longer succeed.

Available format(s)
Publication info
A minor revision of an IACR publication in FSE 2018
encrypted databasesnapshot attackinference attackfrequency analysisdeterministic encryptionhomophonic encodingfrequency-smoothing encryption
Contact author(s)
marie-sarah lacharite 2015 @ rhul ac uk
2018-02-23: revised
2017-11-10: received
See all versions
Short URL
Creative Commons Attribution


      author = {Marie-Sarah Lacharité and Kenneth G.  Paterson},
      title = {Frequency-smoothing encryption: preventing snapshot attacks on deterministically encrypted data},
      howpublished = {Cryptology ePrint Archive, Paper 2017/1068},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.