Technical Program

Paper Detail

Paper Title A Concentration of Measure Approach to Database De-anonymization
Paper IdentifierFR2.R7.3
Authors Farhad Shirani, Siddharth Garg, Elza Erkip, New York University, United States
Session Active Adversaries
Location Bièvre, Level 5
Session Time Friday, 12 July, 11:40 - 13:00
Presentation Time Friday, 12 July, 12:20 - 12:40
Manuscript  Click here to download the manuscript
Abstract 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.