Database Matching Under Adversarial Column Deletions

Serhat Bakirtas, Elza Erkip

Research output: Chapter in Book/Report/Conference proceedingConference contribution


The de-anonymization of users from anonymized microdata through matching or aligning with publicly-available correlated databases has been of scientific interest recently. While most of the rigorous analyses of database matching have focused on random-distortion models, the adversarial-distortion models have been wanting in the relevant literature. In this work, motivated by synchronization errors in the sampling of time-indexed microdata, matching (alignment) of random databases under adversarial column deletions is investigated. It is assumed that a constrained adversary, which observes the anonymized database, can delete up to a δ fraction of the columns (attributes) to hinder matching and preserve privacy. Column histograms of the two databases are utilized as permutation-invariant features to detect the column deletion pattern chosen by the adversary. The detection of the column deletion pattern is then followed by an exact row (user) matching scheme. The worst-case analysis of this two-phase scheme yields a sufficient condition for the successful matching of the two databases, under the near-perfect recovery condition. A more detailed investigation of the error probability leads to a tight necessary condition on the database growth rate, and in turn, to a single-letter characterization of the adversarial matching capacity. This adversarial matching capacity is shown to be significantly lower than the "random"matching capacity, where the column deletions occur randomly. Overall, our results analytically demonstrate the privacy-wise advantages of adversarial mechanisms over random ones during the publication of anonymized time-indexed data.

Original languageEnglish (US)
Title of host publication2023 IEEE Information Theory Workshop, ITW 2023
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages5
ISBN (Electronic)9798350301496
StatePublished - 2023
Event2023 IEEE Information Theory Workshop, ITW 2023 - Saint-Malo, France
Duration: Apr 23 2023Apr 28 2023

Publication series

Name2023 IEEE Information Theory Workshop, ITW 2023


Conference2023 IEEE Information Theory Workshop, ITW 2023

ASJC Scopus subject areas

  • Artificial Intelligence
  • Computational Theory and Mathematics
  • Computer Networks and Communications
  • Signal Processing
  • Control and Optimization


Dive into the research topics of 'Database Matching Under Adversarial Column Deletions'. Together they form a unique fingerprint.

Cite this