Optimal Random Perturbation at Multiple Privacy Levels

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

38 Scopus Citations
View graph of relations



Original languageEnglish
Pages (from-to)814-825
Journal / PublicationProceedings of the VLDB Endowment
Issue number1
Publication statusPublished - Aug 2009
Externally publishedYes


Random perturbation is a popular method of computing anonymized data for privacy preserving data mining. It is simple to apply, ensures strong privacy protection, and permits effective mining of a large variety of data patterns. However, all the existing studies with good privacy guarantees focus on perturbation at a single privacy level. Namely, a fixed degree of privacy protection is imposed on all anonymized data released by the data holder. This drawback seriously limits the applicability of random perturbation in scenarios where the holder has numerous recipients to which different privacy levels apply. 

Motivated by this, we study the problem of multi-level perturbation, whose objective is to release multiple versions of a dataset anonymized at different privacy levels. The challenge is that various recipients may collude by sharing their data to infer privacy beyond their permitted levels. Our solution overcomes this obstacle, and achieves two crucial properties. First, collusion is useless, meaning that the colluding recipients cannot learn anything more than what the most trustable recipient (among the colluding recipients) already knows alone. Second, the data each recipient receives can be regarded (and hence, analyzed in the same way) as the output of conventional uniform perturbation. Besides its solid theoretical foundation, the proposed technique is both space economical and computationally efficient. It requires (n+m) expected space, and produces a new anonymized version in (n+log m) expected time, where n is the cardinality of the original dataset, and m the number of versions released previously. Both bounds are optimal under the realistic assumption that n » m. © 2009 VLDB Endowment.

Citation Format(s)

Optimal Random Perturbation at Multiple Privacy Levels. / Xiao, Xiaokui; Tao, Yufei; Chen, Minghua.

In: Proceedings of the VLDB Endowment, Vol. 2, No. 1, 08.2009, p. 814-825.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review