How Query Distribution Knowledge Breaks Multidimensional Encrypted Range Queries, With Guarantees
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917470198038528 |
|---|---|
| author | Blackley, Daniel Moyer, Nathaniel Papamanthou, Charalampos Kornaropoulos, Evgenios M. |
| author_facet | Blackley, Daniel Moyer, Nathaniel Papamanthou, Charalampos Kornaropoulos, Evgenios M. |
| contents | In this work, we show how knowledge of the query distribution, combined with access-pattern leakage, is sufficient to break multi-dimensional encrypted range queries, with provable guarantees. Prior attacks either recover only data topology without concrete coordinates for plaintexts (and as a result require post-hoc transformations), or assume adversarial control over database content; a strong and unrealistic threat model. Given knowledge of the query distribution, we revisit frequency matching, one of the earliest cryptanalytic ideas in this area, and push it to its limits in the multi-dimensional regime through LAMa ($\underline{L}$eakage-$\underline{A}$buse via $\underline{Ma}$tching). LAMa is a three-component framework that reconstructs plaintext coordinates in arbitrary dimensions without post-hoc transformations or data injection/poisoning. We complement LAMa with the first rigorous guarantees for multi-dimensional frequency-matching cryptanalysis, covering its query complexity, optimal parameterization, and worst-case reconstruction quality. Experiments on real-world data show that LAMa consistently outperforms the state of the art. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_11563 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | How Query Distribution Knowledge Breaks Multidimensional Encrypted Range Queries, With Guarantees Blackley, Daniel Moyer, Nathaniel Papamanthou, Charalampos Kornaropoulos, Evgenios M. Cryptography and Security In this work, we show how knowledge of the query distribution, combined with access-pattern leakage, is sufficient to break multi-dimensional encrypted range queries, with provable guarantees. Prior attacks either recover only data topology without concrete coordinates for plaintexts (and as a result require post-hoc transformations), or assume adversarial control over database content; a strong and unrealistic threat model. Given knowledge of the query distribution, we revisit frequency matching, one of the earliest cryptanalytic ideas in this area, and push it to its limits in the multi-dimensional regime through LAMa ($\underline{L}$eakage-$\underline{A}$buse via $\underline{Ma}$tching). LAMa is a three-component framework that reconstructs plaintext coordinates in arbitrary dimensions without post-hoc transformations or data injection/poisoning. We complement LAMa with the first rigorous guarantees for multi-dimensional frequency-matching cryptanalysis, covering its query complexity, optimal parameterization, and worst-case reconstruction quality. Experiments on real-world data show that LAMa consistently outperforms the state of the art. |
| title | How Query Distribution Knowledge Breaks Multidimensional Encrypted Range Queries, With Guarantees |
| topic | Cryptography and Security |
| url | https://arxiv.org/abs/2508.11563 |