# A Concentration of Measure Approach to Database De-anonymization

arXiv: https://arxiv.org/abs/1901.07655 · HTML: https://mlsanity.com/paper/1901.07655/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Jan 2019.

## Built on by (most cited first, 5 of 5)

- [On Correlation Detection and Alignment Recovery of Gaussian Databases](https://mlsanity.com/paper/2211.01069/) (2022)
- [Phase Transitions in the Detection of Correlated Databases](https://mlsanity.com/paper/2302.03380/) (2023)
- [Gaussian Database Alignment and Gaussian Planted Matching](https://mlsanity.com/paper/2307.02459/) (2023)
- [Testing Dependency of Unlabeled Databases](https://mlsanity.com/paper/2311.05874/) (2023)
- [Detection of Correlated Random Vectors](https://mlsanity.com/paper/2401.13429/) (2024)

## Abstract (arXiv)

In this paper, matching of correlated high-dimensional databases is investigated. A stochastic database model is considered where the correlation among the database entries is governed by an arbitrary joint distribution. Concentration of measure theorems such as typicality and laws of large numbers are used to develop a database matching scheme and derive necessary conditions for successful matching. Furthermore, it is shown that these conditions are tight through a converse result which characterizes a set of distributions on the database entries for which reliable matching is not possible. The necessary and sufficient conditions for reliable matching are evaluated in the cases when the database entries are independent and identically distributed as well as under Markovian database models.