Full Citation

Title: Privacy Risk and Scalability of Differentially-Private Data Anonymization

Citation Type: Dissertation/Thesis

Publication Year: 2012

ISBN:

ISSN:

DOI:

NSFID:

PMCID:

PMID:

Abstract: Although data disclosure is advantageous for many obvious reasons, it may incur some risk resulting from potential security breaches. An example of such privacy violation occurs when an adversary reconstructs the original data using additional information. Moreover, sharing private information such as address and telephone number insocial networks isalwayssubjecttoapotential misuse. Inthisdissertation, we address both the scalability andprivacy risk ofdata anonymization. Wedevelop a framework that assesses the relationship between thedisclosed data and the resulting privacy risk and use it to determine the optimal set of transformations that need to be performed before data is disclosed. We propose a scalable algorithm that meets differential privacy when applying a specific random sampling.The main contribution of this dissertation is three-fold: (i) we show that determining the optimal transformations is an NP-hard problem and propose a few approximationheuristics, which wejustify experimentally,(ii) wepropose apersonalized anonymizationtechniquebased on an aggregate(Lagrangian) formulation and provethat itcouldbesolved inpolynomialtime,and(iii)weshowthatcombining the proposed aggregate formulation with specific sampling gives an anonymization algorithm that satisfies differential privacy. Our results rely heavily on exploring the supermodularity properties of the risk function, which allow us to employ techniques from convex optimization. Finally, we use the proposed model to assess the risk of private information sharing in social networks.Through experimental studies we compare our proposed algorithms with other anonymization schemes in terms of both time and privacy risk. We show that the proposed algorithm is scalable. Moreover, we compare the performance of the proposedapproximate algorithms with the optimal algorithm and show that the sacrifice in risk is outweighed by the gain in efficiency

User Submitted?: No

Authors: Fouad, Mohamed R.

Institution: Purdue University

Department: Computer Science

Advisor: Elisa Bertino

Degree: Doctor of Philosophy

Publisher Location: West Lafayette, IN

Pages:

Data Collections: IPUMS USA

Topics: Methodology and Data Collection, Other

Countries: