Paper 2023/810

MAPLE: MArkov Process Leakage attacks on Encrypted Search

Seny Kamara, MongoDB, Brown University
Abdelkarim Kati, Mohammed-VI Polytechnic University
Tarik Moataz, MongoDB
Jamie DeMaria, Elementl
Andrew Park, Carnegie Mellon University
Amos Treiber, Rohde & Schwarz Cybersecurity GmbH

Encrypted search algorithms (ESAs) enable private search on encrypted data and can be constructed from a variety of cryptographic primitives. All known sub-linear ESA algorithms leak information and, therefore, the design of leakage attacks is an important way to ascertain whether a given leakage profile is exploitable in practice. Recently, Oya and Kerschbaum (Usenix '22) presented an attack called IHOP that targets the query equality pattern---which reveals if and when two queries are for the same keyword---of a sequence of dependent queries. In this work, we continue the study of query equality leakage on dependent queries and present two new attacks in this setting which can work either as known-distribution or known-sample attacks. They model query distributions as Markov processes and leverage insights and techniques from stochastic processes and machine learning. We implement our attacks and evaluate them on real-world query logs. Our experiments show that they outperform the state-of-the-art in most settings but also have limitations in practical settings.

Available format(s)
Attacks and cryptanalysis
Publication info
encrypted searchleakage attackshidden Markov model
Contact author(s)
seny kamara @ mongodb com
abdelkarim kati @ um6p ma
tarik moataz @ mongodb com
DeMaria @ alumni brown edu
andrewpark @ cmu edu
amos treiber @ rohde-schwarz com
2023-06-06: approved
2023-06-01: received
See all versions
Short URL
Creative Commons Attribution


      author = {Seny Kamara and Abdelkarim Kati and Tarik Moataz and Jamie DeMaria and Andrew Park and Amos Treiber},
      title = {MAPLE: MArkov Process Leakage attacks on Encrypted Search},
      howpublished = {Cryptology ePrint Archive, Paper 2023/810},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.