Paper 2023/813

Bayesian Leakage Analysis: A Framework for Analyzing Leakage in Encrypted Search

Seny Kamara, MongoDB, Brown University
Tarik Moataz, MongoDB

Sub-linear encrypted search algorithms (ESA) are highly efficient search algorithms that operate on end-to-end encrypted data. ESAs can be built using a variety of cryptographic primitives and can achieve different trade-offs between efficiency, expressiveness and leakage. Since the introduction of ESAs, cryptographers have focused on both minimizing and attacking their leakage but an important open problem in the field has been to provide a theoretical framework with which leakage can be analyzed and better understood. In this work, we propose such a framework. We model leakage profiles as Bayesian networks and capture leakage attacks as statistical inference algorithms on these networks. We then formalize a notion we call coherence which, roughly speaking, captures the quality of the inference given some observed leakage and an auxiliary distribution. In this work, we focus on partial and full query recovery attacks, though our framework can be extended to capture data recovery attacks as well. We then use our framework to study the coherence of two common leakage patterns---the query equality pattern and the volume pattern---against two well-known and powerful statistical inference techniques. In each case, we provide generic bounds on the coherence in the sense that they apply to arbitrary query and auxiliary distributions and concrete analyses for specific pairs of query and auxiliary distributions.

Available format(s)
Publication info
encrypted searchleakagebayesian network
Contact author(s)
seny kamara @ mongodb com
tarik moataz @ mongodb com
2023-06-06: approved
2023-06-02: received
See all versions
Short URL
Creative Commons Attribution


      author = {Seny Kamara and Tarik Moataz},
      title = {Bayesian Leakage Analysis: A Framework for Analyzing Leakage in Encrypted Search},
      howpublished = {Cryptology ePrint Archive, Paper 2023/813},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.