Provable de-anonymization of large datasets with sparse dimensions

• Main Authors: DATTA, Anupam, SHARMA, Divya, SINHA, Arunesh
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2012
• Subjects: Privacy; database; de-anonymization; Artificial Intelligence and Robotics; Computer Engineering
• Online Access: https://ink.library.smu.edu.sg/sis_research/4471; https://ink.library.smu.edu.sg/context/sis_research/article/5474/viewcontent/dss_post12_1_.pdf
• Institution: Singapore Management University

There is a significant body of empirical work on statistical de-anonymization attacks against databases containing micro-dataabout individuals, e.g., their preferences, movie ratings, or transactiondata. Our goal is to analytically explain why such attacks work. Specifically, we analyze a variant of the Narayanan-Shmatikov algorithm thatwas used to effectively de-anonymize the Netflix database of movie ratings. We prove theorems characterizing mathematical properties of thedatabase and the auxiliary information available to the adversary thatenable two classes of privacy attacks. In the first attack, the adversarysuccessfully identifies the individual about whom she possesses auxiliaryinformation (an isolation attack). In the second attack, the adversarylearns additional information about the individual, although she may notbe able to uniquely identify him (an information amplification attack ).We demonstrate the applicability of the analytical results by empiricallyverifying that the mathematical properties assumed of the database areactually true for a significant fraction of the records in the Netflix movieratings database, which contains ratings from about 500,000 users.