Paper 2020/1501

PANCAKE: Frequency Smoothing for Encrypted Data Stores

Paul Grubbs, Anurag Khandelwal, Marie-Sarah Lacharité, Lloyd Brown, Lucy Li, Rachit Agarwal, and Thomas Ristenpart

Abstract

We present PANCAKE, the first system to protect key-value stores from access pattern leakage attacks with small constant factor bandwidth overhead. PANCAKE uses a new approach, that we call frequency smoothing, to transform plaintext accesses into uniformly distributed encrypted accesses to an encrypted data store. We show that frequency smoothing prevents access pattern leakage attacks by passive persistent adversaries in a new formal security model. We integrate PANCAKE into three key-value stores used in production clusters, and demonstrate 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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Major revision.Usenix Security 2020
Keywords
encrypted search
Contact author(s)
paulgrubbs12 @ gmail com
anurag khandelwal @ yale edu
History
2020-12-02: received
Short URL
https://ia.cr/2020/1501
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/1501,
      author = {Paul Grubbs and Anurag Khandelwal and Marie-Sarah Lacharité and Lloyd Brown and Lucy Li and Rachit Agarwal and Thomas Ristenpart},
      title = {PANCAKE: Frequency Smoothing for Encrypted Data Stores},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1501},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/1501}},
      url = {https://eprint.iacr.org/2020/1501}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.