We examine Euclidean distance-preserving data perturbation as a tool for privacy-preserving data mining. Such perturbations allow many important data mining algorithms e.g. hierarchical and k-means clustering), with only minor modification, to be applied to the perturbed data and produce exactly the same results as if applied to the original data. However, the issue of how well the privacy of the original data is preserved needs careful study. We engage in this study by assuming the role of an attacker armed with a small set of known original data tuples (inputs). Little work has been done examining this kind of attack when the number of known original tuples is less than the number of data dimensions. We focus on this important case, develop and rigorously analyze an attack that utilizes any number of known original tuples. The approach allows the attacker to estimate the original data tuple associated with each perturbed tuple and calculate the probability that the estimation results in a privacy breach. On a real 16-dimensional dataset, we show that the attacker, with 4 known original tuples, can estimate an original unknown tuple with less than 7 error with probability exceeding 0.8.
Ting @cite_10 considered left-multiplication by a randomly generated orthogonal matrix. However, they assume the original data tuples are rows rather than columns as we do. As a result, Euclidean distance between original data tuples is not preserved, but, sample mean and covariance are. If the original data arose as independent samples from multi-variate Gaussian distribution, then the perturbed data allows inferences to be drawn about this underlying distribution just as well as the original data. For all but small or very high-dimensional datasets, their approach is more resistant to prior knowledge attacks than Euclidean distance preserving perturbations. Their perturbation matrix is @math ( @math the number of original data tuples), much bigger than Euclidean distance preserving perturbation matrices, @math ( @math the number of entries in each original data tuple).
@cite_10
1975118429
Statistically defensible methods for disclosure limitation allow users to make inferences about parameters in a model similar to those that would be possible using the original unreleased data. We present a new perturbation method for protecting confidential continuous microdata Random Orthogonal Matrix Masking (ROMM) which preserves the sufficient statistics for multivariate normal distributions, and thus is statistically defensible. ROMM encompasses all methods that preserve these statistics and can be restricted to provide 'small' perturbations. We contrast ROMM with other microdata perturbation methods and we discuss methods for evaluating it from the perspective of the tradeoff between disclosure risk and data utility.