Pancake: Frequency Smoothing for Encrypted Data Stores

Authors: 

Paul Grubbs, Cornell Tech; Anurag Khandelwal, Yale University; Marie-Sarah Lacharité, Royal Holloway, University of London; Lloyd Brown, University of California, Berkeley; Lucy Li, Cornell Tech; Rachit Agarwal, Cornell University; Thomas Ristenpart, Cornell Tech

Distinguished Paper Award Winner

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.

Open Access Media

USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.

BibTeX
@inproceedings {255306,
author = {Paul Grubbs and Anurag Khandelwal and Marie-Sarah Lacharit{\'e} and Lloyd Brown and Lucy Li and Rachit Agarwal and Thomas Ristenpart},
title = {Pancake: Frequency Smoothing for Encrypted Data Stores},
booktitle = {29th {USENIX} Security Symposium ({USENIX} Security 20)},
year = {2020},
isbn = {978-1-939133-17-5},
pages = {2451--2468},
url = {https://www.usenix.org/conference/usenixsecurity20/presentation/grubbs},
publisher = {{USENIX} Association},
month = aug,
}

Presentation Video