Paper 2023/810
MAPLE: MArkov Process Leakage attacks on Encrypted Search
Abstract
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.
Metadata
- Available format(s)
- Category
- Attacks and cryptanalysis
- Publication info
- Preprint.
- Keywords
- 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 - History
- 2023-06-06: approved
- 2023-06-01: received
- See all versions
- Short URL
- https://ia.cr/2023/810
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/810, 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}, url = {https://eprint.iacr.org/2023/810} }