(k, ε, δ)-Anonymization: privacy-preserving data release based on k-anonymity and differential privacy

Yao Tung Tsou*, Mansour Naser Alraja, Li Sheng Chen, Yu Hsiang Chang, Yung Li Hu, Yennun Huang, Chia-Mu Yu, Pei Yuan Tsai

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

6 Citations (Scopus)


The General Data Protection Regulation came into effect on May 25, 2018, and has rapidly become a touchstone model for modern privacy law. It empowers consumers with unprecedented control over the use of their personal information. However, new guarantees of consumer privacy adversely affect data sharing and data application markets because service companies (e.g., Apple, Google, Microsoft) cannot provide immediate and optimized services through analysis of collected consumer experiences. Therefore, data de-identification technology (e.g., k-anonymity and differential privacy) is a candidate solution to protect sharing data privacy. Various workarounds based on existing methods such as k-anonymity and differential privacy technologies have been proposed. However, they are limited in data utility, and their data sets have high dimensionality (the so-called curse of dimensionality). In this paper, we propose the (k, ε, δ)-anonymization synthetic data set generation mechanism (called (k, ε, δ)-anonymization for short) to protect data privacy before releasing data sets to be analyzed. Synthetic data sets generated by (k, ε, δ)-anonymization satisfy the definitions of k-anonymity and differential privacy by applying KD-tree and random sampling mechanisms. Moreover, (k, ε, δ)-anonymization uses principle component analysis to rationally replace high-dimensional data sets with lower-dimensional data sets for consideration of efficient computation. Finally, we confirm the relationships between parameters k, ε, and δ for k-anonymity and (ε, δ)-differential privacy and estimate the utility of (k, ε, δ)-anonymization synthetic data sets. We report a privacy analysis and a series of experiments that prove that (k, ε, δ)-anonymization is feasible and efficient.

Original languageEnglish
Pages (from-to)175-185
Number of pages11
JournalService Oriented Computing and Applications
Issue number3
Early online date6 Aug 2021
Publication statusPublished - 1 Sept 2021
Externally publishedYes

Cite this