MAPLE: MArkov Process Leakage attacks on Encrypted Search
Authors: Seny Kamara (MongoDB & Brown University), Abdelkarim Kati (Mohammed-VI Polytechnic University), Tarik Moataz (MongoDB), Jamie DeMaria (Elementl), Andrew Park (Carnegie Mellon University), Amos Treiber (Technical University of Darmstadt)
Volume: 2024
Issue: 1
Pages: 430–446
DOI: https://doi.org/10.56553/popets-2024-0025
Abstract: Encrypted search algorithms (ESAs) enable private search on encrypted data and can be constructed from a variety of cryptographic primitives. All knownsub-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 inpractical settings.
Keywords: Encrypted Search, Leakage Attacks, Applied Cryptography
Copyright in PoPETs articles are held by their authors. This article is published under a Creative Commons Attribution 4.0 license.
