Achieving Probabilistic Anonymity in a Linear and Hybrid Randomization Model

Yingpeng Sang, Hong Shen, Hui Tian, Zonghua Zhang

Research output: Contribution to journalArticlepeer-review

11 Citations (Scopus)


The randomization methods that are applied for privacy-preserving data mining are commonly subject to reconstruction, linkage, and semantic-related attacks. Some existing works employed random noise addition to realize probabilistic anonymity, aiming only at linkage attacks. Random noise addition is vulnerable to reconstruction attacks, and is unable to achieve semantic closeness, particularly on high-dimensional data, to prevent semantic-related attacks. For linkage attacks, the main security vulnerability of their proposed probabilistic anonymity lies in the assumption that the attacker had a priori knowledge of the quasi-identifiers of all individuals. When only some individuals leak their quasi-identifiers, the proposed model will become incapable, because the attacker can deploy a different linkage attack that has not been studied before. This type of attack is much easier to deploy and is thus very harmful. In this paper, we propose new frameworks of probabilistic (1,k)- and (k,k)-anonymity to defend against all these linkage attacks, and realize the frameworks on a hybrid randomization model. The model is also secure against reconstruction attacks. We further achieve statistical semantic closeness of high-dimensional data to prevent semantic-related attacks on the model. The frameworks also allow us to re-design the traditional K-nearest neighbor algorithm to leverage the introduced data uncertainty and improve the mining results. This paper demonstrates the promising applications in large-scale and high-dimensional data mining in clouds, by providing high efficiency and security to protect data privacy, guaranteeing high data utility for mining purposes, on-time processing, and non-interactive data publishing.

Original languageEnglish
Article number7464905
Pages (from-to)2187-2202
Number of pages16
JournalIEEE Transactions on Information Forensics and Security
Issue number10
Publication statusPublished - Oct 2016
Externally publishedYes


  • Randomization
  • data mining
  • k-anonymity
  • privacy protection


Dive into the research topics of 'Achieving Probabilistic Anonymity in a Linear and Hybrid Randomization Model'. Together they form a unique fingerprint.

Cite this