[Resource Topic] 2023/810: MAPLE: MArkov Process Leakage attacks on Encrypted Search

Welcome to the resource topic for 2023/810

MAPLE: MArkov Process Leakage attacks on Encrypted Search

Authors: Seny Kamara, Abdelkarim Kati, Tarik Moataz, Jamie DeMaria, Andrew Park, Amos Treiber


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.

ePrint: https://eprint.iacr.org/2023/810

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .