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

Publication Type

Journal Article

Publication Date

2008

Abstract

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.

Discipline

Information Security

Research Areas

Information Security and Trust

Publication

Knowledge and Information Systems

Volume

17

Issue

2

First Page

217

Last Page

240

ISSN

0219-1377

Identifier

10.1007/s10115-008-0123-9

Publisher

Springer Verlag

Additional URL

http://dx.doi.org/10.1007/s10115-008-0123-9

Link to Full Text

Share

COinS