Paper 2024/554

Leakage-Abuse Attacks Against Structured Encryption for SQL

Alexander Hoover, University of Chicago
Ruth Ng, DSO National Laboratories
Daren Khu, DSO National Laboratories
Yao'an Li, DSO National Laboratories
Joelle Lim, DSO National Laboratories
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.

Available format(s)
Attacks and cryptanalysis
Publication info
Published elsewhere. Minor revision. USENIX Security '24
leakage-abuse attacksstructured encryption for sqlLAAStE for SQL
Contact author(s)
alexhoover @ uchicago edu
niiyung @ dso org sg
kboontat @ dso org sg
liyaoaeta @ gmail com
joelle-lim @ hotmail com
nweichen @ dso org sg
jedlimlx @ gmail com
syy3 1415926 @ gmail com
2024-04-12: revised
2024-04-09: received
See all versions
Short URL
Creative Commons Attribution


      author = {Alexander Hoover and Ruth Ng and Daren Khu and Yao'an Li and Joelle Lim and Derrick Ng and Jed Lim and Yiyang Song},
      title = {Leakage-Abuse Attacks Against Structured Encryption for {SQL}},
      howpublished = {Cryptology ePrint Archive, Paper 2024/554},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.