Published January 1, 2024
| Version v1
Publication
Open
MAPLE: MArkov Process Leakage attacks on Encrypted Search
Creators
- 1. Brown University
- 2. Université Mohammed VI Polytechnique
- 3. Polytechnic University
- 4. Carnegie Mellon University
- 5. Technical University of Darmstadt
Description
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.
Translated Descriptions
⚠️
This is an automatic machine translation with an accuracy of 90-95%
Translated Description (Arabic)
تتيح خوارزميات البحث المشفرة (ESAs) البحث الخاص عن البيانات المشفرة ويمكن إنشاؤها من مجموعة متنوعة من بدائيات التشفير. جميع خوارزميات ESA شبه الخطية المعروفة تسرب المعلومات، وبالتالي، فإن تصميم هجمات التسرب هو وسيلة مهمة للتأكد مما إذا كان ملف تعريف تسرب معين قابلاً للاستغلال في الممارسة العملية. في الآونة الأخيرة، قدم أويا وكيرشباوم (Usenix '22) هجومًا يسمى IHOP يستهدف نمط المساواة في الاستعلام الذي يكشف عما إذا كان ومتى يكون هناك استعلامان لنفس الكلمة الرئيسية لسلسلة من الاستعلامات التابعة. في هذا العمل، نواصل دراسة تسرب المساواة في الاستعلامات على الاستعلامات التابعة ونقدم هجومين جديدين في هذا الإعداد يمكن أن يعملا إما كهجمات توزيع معروفة أو هجمات عينة معروفة. إنهم يصممون توزيعات الاستعلام أثناء معالجة ماركوف ويستفيدون من الرؤى والتقنيات من العمليات العشوائية والتعلم الآلي. نقوم بتنفيذ هجماتنا وتقييمها على سجلات الاستعلام في العالم الحقيقي. تُظهر تجاربنا أنها تتفوق على أحدث التقنيات في معظم الإعدادات ولكن لديها أيضًا قيود في الإعدادات العملية.Translated Description (French)
Les algorithmes de recherche cryptés (ESA) permettent une recherche privée sur des données cryptées et peuvent être construits à partir d'une variété de primitives cryptographiques. Tous les algorithmes sub-linéaires connus de l'ESA divulguent des informations et, par conséquent, la conception des attaques de fuite est un moyen important de déterminer si un profil de fuite donné est exploitable dans la pratique. Récemment,Oya et Kerschbaum(Usenix '22) ont présenté une attaque appelée IHOP qui cible le modèle d'égalité des requêtes qui révèle si et quand deux requêtes sont pour le même mot-clé d'une séquence de requêtes dépendantes. Dans ce travail, nous poursuivons l'étude des fuites d'égalité des requêtes sur les requêtes dépendantes et présentons deux nouvelles attaques dans ce contexte qui peuvent fonctionner soit comme des attaques à distribution connue, soit comme des attaques à échantillon connu. Ils modélisent les distributions de requêtes en tant que processus de Markov et tirent parti des informations et des techniques des processus stochastiques et de l'apprentissage automatique. Nous mettons en œuvre nos attaques et les évaluons sur des journaux de requêtes du monde réel. Nos expériences montrent qu'ils surpassent l'état de l'art dans la plupart des contextes, mais ont également des limites dans les contextes pratiques.Translated Description (Spanish)
Los algoritmos de búsqueda cifrada (esa) permiten la búsqueda privada en datos cifrados y se pueden construir a partir de una variedad de primitivas criptográficas. Todos los algoritmos sublineales conocidos de esa filtran información y, por lo tanto, el diseño de ataques de fuga es una forma importante de determinar si un perfil de fuga dado es explotable en la práctica. Recientemente,Oya y Kerschbaum(Usenix '22) presentaron un ataque llamado IHOP que se dirige al patrón de igualdad de consultas que revela si y cuándo dos consultas son para la misma palabra clave de una secuencia de consultas dependientes. En este trabajo, continuamos el estudio de la fuga de igualdad de consultas en consultas dependientes y presentamos dos nuevos ataques en este entorno que pueden funcionar como ataques de distribución conocida o de muestra conocida. Modelan las distribuciones de consultas como procesos de Markov y aprovechan los conocimientos y las técnicas de los procesos estocásticos y el aprendizaje automático. Implementamos nuestros ataques y los evaluamos en registros de consultas del mundo real. Nuestros experimentos muestran que superan el estado de la técnica en la mayoría de los entornos, pero también tienen limitaciones en los entornos prácticos.Files
popets-2024-0025.pdf.pdf
Files
(797.6 kB)
| Name | Size | Download all |
|---|---|---|
|
md5:84b92b27adf71bcac4a736c49bb2834d
|
797.6 kB | Preview Download |
Additional details
Additional titles
- Translated title (Arabic)
- القيقب: هجمات تسرب عملية ماركوف على البحث المشفر
- Translated title (French)
- MAPLE : Attaques de fuites de processus MArkov sur la recherche cryptée
- Translated title (Spanish)
- MAPLE: Ataques de fuga del proceso MArkov en la búsqueda encriptada
Identifiers
- Other
- https://openalex.org/W4387857582
- DOI
- 10.56553/popets-2024-0025
References
- https://openalex.org/W1502708590
- https://openalex.org/W1502927489
- https://openalex.org/W1539859404
- https://openalex.org/W1674925153
- https://openalex.org/W1724472458
- https://openalex.org/W1988374166
- https://openalex.org/W1991133427
- https://openalex.org/W2027471022
- https://openalex.org/W2031533839
- https://openalex.org/W2033165262
- https://openalex.org/W2074388704
- https://openalex.org/W2086763678
- https://openalex.org/W2131043660
- https://openalex.org/W2133003537
- https://openalex.org/W2147929033
- https://openalex.org/W2152516507
- https://openalex.org/W2154496743
- https://openalex.org/W2184702105
- https://openalex.org/W2341421640
- https://openalex.org/W2404098708
- https://openalex.org/W2532292902
- https://openalex.org/W2592789682
- https://openalex.org/W2765463836
- https://openalex.org/W2794832738
- https://openalex.org/W2795038002
- https://openalex.org/W2891020614
- https://openalex.org/W2910639144
- https://openalex.org/W2946109000
- https://openalex.org/W2949560757
- https://openalex.org/W2985761010
- https://openalex.org/W2986992030
- https://openalex.org/W3006791962
- https://openalex.org/W3029635585
- https://openalex.org/W3043289845
- https://openalex.org/W3127380200
- https://openalex.org/W3141585064
- https://openalex.org/W3156257889
- https://openalex.org/W3192108271
- https://openalex.org/W3195471176
- https://openalex.org/W3207910067
- https://openalex.org/W3213572057
- https://openalex.org/W4255171344
- https://openalex.org/W4283380702
- https://openalex.org/W4385080249