International Association
for Cryptologic Research

In this talk I will present the design, analysis, and implementation of Pancake, the first system to protect key-value stores from access pattern leakage attacks with small constant factor bandwidth overhead. First, I will outline our new formal security model, and explain why it captures realistic attacks. Then, I will describe our frequency smoothing mechanism, which provably transforms plaintext accesses into uniformly-distributed encrypted accesses. Finally, I will explain the implementation and evaluation of the Pancake system itself. We integrated Pancake into three key-value stores used in production clusters, and demonstrated its practicality: on standard benchmarks, PANCAKE achieves 229× better throughput than non-recursive Path ORAM - within 3-6× of insecure baselines for these key-value stores.

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.