Research of Improved k-Anonymity Algorithm and Its Application in Privacy Protection

doi:10.3969/j.issn.1671-1122.2022.10.008

Abstract

Abstract:

At present, the problem of privacy disclosure in public data of the network frequently appears, which has caused adverse effects and even serious harm to the relevant individuals. Therefore, the research on privacy protection technology has attracted more and more global attention. As a technology that can effectively protect privacy information, k-anonymization has developed a variety of algorithms, however, some of these algorithms have low data processing efficiency and weak anti-attack performance. This paper established an improved algorithm of (k, e) anonymous privacy protection based on K-means by using the K-means algorithm and the Mondrian algorithm for clustering; and it not only compared the computational efficiency with the representative privacy protection algorithm (k, e)- MDAV algorithm, but also used the improved algorithm to analyze an application case involving personal location information. The results show that the improved algorithm proposed in this paper can effectively improve the operation efficiency based on the implementation of anonymous data, and has strong anti-link attack and anti-homogeneity attack performance.

Key words: k-anonymity, clustering algorithm, improved algorithm, privacy protection

CLC Number:

TP309

GU Haiyan, JIANG Tong, MA Zhuo, ZHU Jipeng. Research of Improved k-Anonymity Algorithm and Its Application in Privacy Protection[J]. Netinfo Security, 2022, 22(10): 52-58.

Figures/Tables 11

References 16

[1]	ZHOU Kexin. Location Privacy Protection Method Based on k-Anonymity[D]. Nanjing: Nanjing University of Aeronautics and Astronautics, 2020.
	周珂欣. 基于k-匿名的位置隐私保护方法[D]. 南京: 南京航空航天大学, 2020.
[2]	SONG Mingqiu, WANG Lin, JIANG Baoyan, et al. K-Anonymity Algorithm Based on Multi Attribute Generalization[J]. Journal of University of Electronic Science and Technology of China, 2017, 46(6): 896-901.
	宋明秋, 王琳, 姜宝彦, 等. 多属性泛化的K-匿名算法[J]. 电子科技大学学报, 2017, 46(6):896-901.
[3]	CHENG Nannan, LIU Shubo, XIONG Xingxing, et al. A (θ, k)- Anonymous Model for Sensitive Attributes Protection[J]. Journal of Zhengzhou University(Natural Science Edition), 2019, 51(3): 42-47.
	程楠楠, 刘树波, 熊星星, 等. 用于敏感属性保护的(θ, k)-匿名模型[J]. 郑州大学学报(理学版), 2019, 51(3):42-47.
[4]	JIA Junjie, YAN Guolei, XING Licheng, et al. A Dynamic Update Algorithmon ( p, k) Anonymity[J]. Computer Engineering & Science, 2018, 40(7): 1206-1212.
	贾俊杰, 闫国蕾, 邢里程, 等. (p,k)匿名数据集的增量更新算法[J]. 计算机工程与科学, 2018, 40(7):1206-1212.
[5]	JIN Ye, DING Xiaobo, GONG Guoqiang, et al. Privacy Protection Method for k Degree Anonymity Based on Node Classification[J]. Computer Engineering, 2020, 46(3): 138-143.
	金叶, 丁晓波, 龚国强, 等. 基于节点分类的k度匿名隐私保护方法[J]. 计算机工程, 2020, 46(3):138-143.
[6]	TU Zhen, ZHAO Kai, XU Fengli, et al. Protecting Trajectory from Semantic Attack Considering k-Anonymity, l-Diversity, and t-Closeness[J]. IEEE Transactions on Network and Service Management, 2019, 16(1): 264-278.
[7]	PU Dong, FANG Rui. Personalization(p, α, k)- Anonymous Privacy Protection Algorithm[J]. Computer Applications and Software, 2020, 37(2): 301-307.
	蒲东, 方睿. 个性化(p,α,k)—匿名隐私保护算法[J]. 计算机应用与软件, 2020, 37(2):301-307.
[8]	HE Jingsha, DU Jinhui, ZHU Nafei. Research on k-Anonymity Algorithm for Personalized Quasi-Identifier Attributes[J]. Netinfo Security, 2020, 20(10): 19-26.
	何泾沙, 杜晋晖, 朱娜斐. 基于k-匿名的准标识符属性个性化实现算法研究[J]. 信息网络安全, 2020, 20(10):19-26.
[9]	YAN Guanghui, LIU Ting, ZHANG Xuejun, et al. Service Similarity Location k-Anonymity Privacy Protection Scheme against Background Knowledge Inference Attacks[J]. Journal of Xi'an Jiaotong University, 2020, 54(1): 8-18.
	闫光辉, 刘婷, 张学军, 等. 抵御背景知识推理攻击的服务相似性位置k-匿名隐私保护方法[J]. 西安交通大学学报, 2020, 54(1):8-18.
[10]	YANG Liu, LI Yun. Hybrid K-Anonymous Feature Selection Algorithm[J]. Journal of Computer Applications, 2021, 41(12): 3521-3526.
	杨柳, 李云. 混合式的K-匿名特征选择算法[J]. 计算机应用, 2021, 41(12):3521-3526.
[11]	LIU Nian, XIE Sijiang, WAN Zongjie, et al. A Micro Aggregate Data Desensitization Model for Big Data Sharing[J]. Secrecy Science and Technology, 2021(4): 28-35.
	刘念, 谢四江, 万宗杰, 等. 一种面向大数据共享的微聚集数据脱敏模型[J]. 保密科学技术, 2021(4):28-35.
[12]	TAN Pangning, MICHAEL S, VIPIN K. Introduction to Data Mining[M]. Beijing: People's Posts and Telecommunications Press, 2011.
	TAN Pangning, MICHAEL S, VIPIN K. 数据挖掘导论[M]. 北京: 人民邮电出版社, 2011.
[13]	SHI Guobin, ZHANG Zhonglin. Aparameter-Free K-Means Algorithm Based on Improved Hierarchical Clustering[J]. Computer Simulation, 2022, 39(8): 340-346, 426.
	史国斌, 张忠林. 基于改进层次方法的无参K-means算法[J]. 计算机仿真, 2022, 39(8):340-346,426.
[14]	XIAN Ying, YU Jiong, YANG Xingyao, et al. Research on Microaggregation Fused Collaborative Filtering Algorithm for Privacy Protection[J]. Modern Electronics Technique, 2018, 41(6): 5-10.
	鲜英, 于炯, 杨兴耀, 等. 融合微聚集隐私保护的协同过滤算法研究[J]. 现代电子技术, 2018, 41(6):5-10.
[15]	WANG Qian, GAN Rongqing. An Efficient Micro-Aggregation Algorithm for K-Anonymity[J]. World Sci-Tech R & D, 2013, 35(1): 38-40, 55.
	王茜, 甘荣庆. 一种高效的微聚集k-匿名算法[J]. 世界科技研究与发展, 2013, 35(1):38-40,55.
[16]	SONG Cheng, JIN Tong, NI Shuiping, et al. K-Anonymous Location Privacy Protection Scheme for the Mobile Terminal[J]. Journal of Xidian University, 2021, 48(3): 138-145.
	宋成, 金彤, 倪水平, 等. 一种面向移动终端的K-匿名位置隐私保护方案[J]. 西安电子科技大学学报, 2021, 48(3):138-145.

time	age	gender	height	transport	position
t3	24	male	178	by bus	22.79,6.79
t2	24	male	178	by bike	18.73,8.73
t1	24	male	178	walk	3.26,6.23

time	age	gender	height	transport	position
t3	[4,7]	[0,0]	[15,21]	[0,2]	25.17,6.19
t2	[7,9]	[0,1]	[20,28]	[2,4]	14.81,5.94
t1	[7,7]	[0,0]	[20,22]	[2,3]	4.89,4.98

time	age	gender	height	transport	position
t3	[21,24]	Male	[173,179]	by bus/by metro/walk	25.17,6.19
t2	[24,28]	Female/Male	[178,189]	walk/by bike/self driving	14.81,5.94
t1	[24,24]	Male	[178,180]	walk/by bike	4.89,4.98