Learning from Leakage: Database Reconstruction from Just a Few Multidimensional Range Queries

Peijie Li, Huanhuan Chen, Evangelia Anna Markatou, Kaitai LiangIACR ePrint 2025

Introduction

Searchable Encryption (SE) is often considered the "holy grail" for secure cloud storage, promising the ability to query encrypted data without revealing decryption keys to the server. However, this efficiency often comes at the cost of information leakage. By observing which encrypted records are returned for specific queries—a phenomenon known as access pattern leakage—an untrusted server can begin to reconstruct the underlying plaintext.

In this paper, researchers from Delft University of Technology and the University of Turku introduce REMIN, a powerful new attack that demonstrates how just a tiny amount of range query leakage can be used to reconstruct high-dimensional databases with startling accuracy.

The Challenge of Multidimensional Reconstruction

While previous research has successfully demonstrated reconstruction attacks on one-dimensional data (e.g., ages or salaries), extending these techniques to multidimensional datasets (e.g., geospatial coordinates or multi-attribute medical records) is notoriously difficult. Existing multidimensional attacks typically require an impractical amount of leakage—often observing every possible query—or fail on "sparse" datasets where records are not perfectly packed.

The authors address the challenge of approximate database reconstruction (ADR), aiming to recover the topological and geometric layout of a database under a "minimal leakage" regime, where the attacker observes only a small fraction of user queries.

The REMIN Attack Methodology

The core of the REMIN attack is a shift in perspective: viewing query leakage as a manifold learning problem. The attack follows a structured pipeline to transform observed responses into a reconstructed dataset.

The REMIN attack workflow: from observed query responses to a reconstructed low-dimensional dataset.
  1. Co-occurrence Analysis: REMIN tracks how often pairs of encrypted records appear together across different queries. High co-occurrence indicates that records are likely close to each other in the original plaintext space.
  2. Frequency-to-Distance Mapping: These frequencies are converted into a high-dimensional distance matrix using a reciprocal metric: $d(a, e) = 1 / (\text{frequency}[a, e] + 1)$.
  3. Unsupervised Representation Learning (t-SNE): Unlike traditional methods like Multidimensional Scaling (MDS) that attempt to preserve global distances, REMIN utilizes t-SNE (t-distributed Stochastic Neighbor Embedding). t-SNE excels at preserving local neighborhood structures, which aligns perfectly with the local nature of range queries.
  4. REMIN-P (Poisoning Variant): The authors also introduce an active version of the attack. By "poisoning" the database with a few "anchor points" (records with known values), the attacker can use a Radial Correction algorithm to fix edge distortions and significantly improve global alignment.

Experimental Evaluation

The authors evaluated REMIN across a diverse range of datasets, including synthetic grids, geospatial data (e.g., Manhattan highway crossings, Shanghai bus stops), and 3D elevation samples.

Visual comparison between the original dataset (blue) and the REMIN reconstruction (orange).

Key Results

  • Superior Accuracy: REMIN consistently outperformed previous state-of-the-art methods, reducing Mean Squared Error (MSE) by up to 50%.
  • Minimal Leakage: On the Manhattan dataset, REMIN achieved high-fidelity reconstruction with under 1% of possible queries observed.
  • Efficiency: The method is an order of magnitude faster than previous cubic-complexity baselines, making it scalable to much larger databases.
  • Poisoning Power: Injecting just a handful of anchor points (REMIN-P) reduced MSE by an additional 50% on average, proving that even tiny amounts of auxiliary knowledge can be devastating.

Discussion and Conclusion

The success of REMIN highlights a fundamental vulnerability in Searchable Encryption: range queries are inherently local. By aligning their mathematical tools (t-SNE) with the nature of the leakage, the authors demonstrate that even sparse, high-dimensional data can be unmasked. The "edge distortion" phenomenon, where boundary points are compressed due to fewer query overlaps, remains a challenge but is largely addressable through strategic poisoning.

This research serves as a stark reminder that in the world of Searchable Encryption, "efficient" often means "leaky." With modern machine learning, even a small amount of leakage can go a very long way in compromising data privacy.

Summary updated

BibTeX
@article{li2025learning,
  author = {Peijie Li and Huanhuan Chen and Evangelia Anna Markatou and Kaitai Liang},
  title = {{Learning from Leakage: Database Reconstruction from Just a Few Multidimensional Range Queries}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2025},
}
Figure