NDLI: De-anonymizing private data by matching statistics

Content Provider	IEEE Xplore Digital Library
Author	Unnikrishnan, J. Naini, F.M.
Copyright Year	2013
Description	Author affiliation: Sch. of Comput. & Commun. Sci., Ecole Polytech. Fed. de Lausanne (EPFL), Lausanne, Switzerland (Unnikrishnan, J.; Naini, F.M.)
Abstract	Recent research has illustrated privacy breaches that can be effected on an anonymized dataset by an attacker who has access to auxiliary information about the users. Most of these attack strategies rely on the uniqueness of specific aspects of the users' data - e.g., observing a mobile user at just a few points on the time-location space are sufficient to uniquely identify him/her from an anonymized set of users. In this work, we consider de-anonymization attacks on anonymized summary statistics in the form of histograms. Such summary statistics are useful for many applications that do not need knowledge about exact user behavior. We consider an attacker who has access to an anonymized set of histograms of K users' data and an independent set of data belonging to the same users. Modeling the users' data as i.i.d., we study the composite hypothesis testing problem of identifying the correct matching between the anonymized histograms from the first set and the user data from the second. We propose a Generalized Likelihood Ratio Test as a solution to this problem and show that the solution can be identified using a minimum weight matching algorithm on an K × K complete bipartite weighted graph. We show that a variant of this solution is asymptotically optimal as the data lengths are increased.We apply the algorithm on mobility traces of over 1000 users on EPFL campus collected during two weeks and show that up to 70% of the users can be correctly matched. These results show that anonymized summary statistics of mobility traces themselves contain a significant amount of information that can be used to uniquely identify users by an attacker who has access to auxiliary information about the statistics.
Sponsorship	IEEE Cont. Syst. Soc.
Starting Page	1616
Ending Page	1623
File Size	810494
Page Count	8
File Format	PDF
e-ISBN	9781479934102
DOI	10.1109/Allerton.2013.6736722
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2013-10-02
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Wireless communication Histograms Accuracy Databases Trajectory Bipartite graph Testing
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Where You Are Is Who You Are: User Identification by Matching Statistics

Tag suggestion and localization for images by bipartite graph matching

Anonymizing Bipartite Graph Data using Safe Groupings (2008)

Anonymizing bipartite graph data using safe groupings (2008)

Anonymizing bipartite graph data using safe groupings (2008).

Anonymizing bipartite graph data using safe groupings (2010).

De-anonymizing . . . percolation graph matching (2015)

Online bipartite perfect matching with.

Online Bipartite Perfect Matching With Augmentations

De-anonymizing private data by matching statistics

Similar Documents

Where You Are Is Who You Are: User Identification by Matching Statistics

Tag suggestion and localization for images by bipartite graph matching

Anonymizing Bipartite Graph Data using Safe Groupings (2008)

Anonymizing bipartite graph data using safe groupings (2008)

Anonymizing bipartite graph data using safe groupings (2008).

Anonymizing bipartite graph data using safe groupings (2010).

De-anonymizing . . . percolation graph matching (2015)

Online bipartite perfect matching with.

Online Bipartite Perfect Matching With Augmentations

De-anonymizing private data by matching statistics