Seeded Database Matching under Noisy Column Repetitions

Serhat Bakirtas, Elza Erkip

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


The re-identification or de-anonymization of users from anonymized data through matching with publicly-available correlated user data has raised privacy concerns, leading to the complementary measure of obfuscation in addition to anonymization. Recent research provides a fundamental understanding of the conditions under which privacy attacks are successful, either in the presence of obfuscation or synchronization errors stemming from the sampling of time-indexed databases. This paper presents a unified framework considering both obfuscation and synchronization errors and investigates the matching of databases under noisy column repetitions. By devising replica detection and seeded deletion detection algorithms, and using information-theoretic tools, sufficient conditions for successful matching are derived. It is shown that a seed size logarithmic in the row size is enough to guarantee the detection of all deleted columns. It is also proved that this sufficient condition is necessary, thus characterizing the database matching capacity of database matching under noisy column repetitions and providing insights on privacy-preserving publication of anonymized and obfuscated time-indexed data.

Original languageEnglish (US)
Title of host publication2022 IEEE Information Theory Workshop, ITW 2022
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages6
ISBN (Electronic)9781665483414
StatePublished - 2022
Event2022 IEEE Information Theory Workshop, ITW 2022 - Mumbai, India
Duration: Nov 1 2022Nov 9 2022

Publication series

Name2022 IEEE Information Theory Workshop, ITW 2022


Conference2022 IEEE Information Theory Workshop, ITW 2022

ASJC Scopus subject areas

  • Information Systems
  • Artificial Intelligence
  • Computational Theory and Mathematics
  • Computer Networks and Communications


Dive into the research topics of 'Seeded Database Matching under Noisy Column Repetitions'. Together they form a unique fingerprint.

Cite this