Determining Error Bounds for Spectral Filtering Based Reconstruction Methods in Privacy Preserving Data Mining

Additive randomization has been a primary tool for hiding sensitive private information. Previous work empirically showed that individual data values can be approximately reconstructed from the perturbed values, using spectral filtering techniques. This poses a serious threat of privacy breaches. In...

Full description

Saved in:
Bibliographic Details
Main Authors: GUO, Songtao, Wu, Xintao, LI, Yingjiu
Format: text
Language:English
Published: Institutional Knowledge at Singapore Management University 2008
Subjects:
Online Access:https://ink.library.smu.edu.sg/sis_research/749
http://dx.doi.org/10.1007/s10115-008-0123-9
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Singapore Management University
Language: English
Description
Summary:Additive randomization has been a primary tool for hiding sensitive private information. Previous work empirically showed that individual data values can be approximately reconstructed from the perturbed values, using spectral filtering techniques. This poses a serious threat of privacy breaches. In this paper we conduct a theoretical study on how the reconstruction error varies, for different types of additive noise. In particular, we first derive an upper bound for the reconstruction error using matrix perturbation theory. Attackers who use spectral filtering techniques to estimate the true data values may leverage this bound to determine how close their estimates are to the original data. We then derive a lower bound for the reconstruction error, which can help data owners decide how much noise should be added to satisfy a given threshold of the tolerated privacy breach.