Alexander Hoover, University of Chicago; Ruth Ng, Daren Khu, Yao'An Li, Joelle Lim, and Derrick Ng, DSO National Laboratories; Jed Lim, NUS High School of Mathematics and Science; Yiyang Song, Raffles Institution
Structured Encryption (StE) enables a client to securely store and query data stored on an untrusted server. Recent constructions of StE have moved beyond basic queries, and now support large subsets of SQL. However, the security of these constructions is poorly understood, and no systematic analysis has been performed.
We address this by providing the first leakage-abuse attacks against StE for SQL schemes. Our attacks can be run by a passive adversary on a server with access to some information about the distribution of underlying data, a common model in prior work. They achieve partial query recovery against select operations and partial plaintext recovery against join operations. We prove the optimality and near-optimality of two new attacks, in a Bayesian inference framework. We complement our theoretical results with an empirical investigation testing the performance of our attacks against real-world data and show they can successfully recover a substantial proportion of queries and plaintexts.
In addition to our new attacks, we provide proofs showing that the conditional optimality of a previously proposed leakage-abuse attack and that inference against join operations is NP-hard in general.
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.
![](https://www.usenix.org/sites/all/modules/usenix/usenix_files/images/usenix-locked.png)
author = {Alexander Hoover and Ruth Ng and Daren Khu and Yao{\textquoteright}An Li and Joelle Lim and Derrick Ng and Jed Lim and Yiyang Song},
title = {{Leakage-Abuse} Attacks Against Structured Encryption for {SQL}},
booktitle = {33rd USENIX Security Symposium (USENIX Security 24)},
year = {2024},
address = {Philadelphia, PA},
url = {https://www.usenix.org/conference/usenixsecurity24/presentation/hoover},
publisher = {USENIX Association},
month = aug
}