Privacy-preserving data compression scheme for k-anonymity model based on Huffman coding

Yue YU; Xianzheng LIN; Weihai LI; Nenghai YU

doi:10.11959/j.issn.2096-109x.2023054

您当前的位置：

首页 >

文章列表页 >

Privacy-preserving data compression scheme for k-anonymity model based on Huffman coding

Papers | 更新时间：2024-06-03

- Privacy-preserving data compression scheme for k-anonymity model based on Huffman coding
- Chinese Journal of Network and Information Security Vol. 9, Issue 4, Pages: 64-73(2023)
- 作者机构：
  
  1. 中国科学技术大学网络空间安全学院，安徽合肥 230001
  2. 中国科学院电磁空间信息重点实验室，安徽合肥 230001
  3. 华为技术有限公司2012实验室，香港 999077
- 作者简介：
- 基金信息：
- DOI：10.11959/j.issn.2096-109x.2023054
  CLC： TP393
- Online First：2023-08，
  
  Published：25 August 2023
- 稿件说明：
移动端阅览
Yue YU, Xianzheng LIN, Weihai LI, et al. Privacy-preserving data compression scheme for k-anonymity model based on Huffman coding[J]. Chinese Journal of Network and Information Security, 2023, 9(4): 64-73.
DOI：

Yue YU, Xianzheng LIN, Weihai LI, et al. Privacy-preserving data compression scheme for k-anonymity model based on Huffman coding[J]. Chinese Journal of Network and Information Security, 2023, 9(4): 64-73. DOI： 10.11959/j.issn.2096-109x.2023054.

摘要

k-匿名模型作为常用的数据匿名技术，广泛应用于数据发布阶段的隐私保护。随着大数据时代的快速发展，海量数据的产生给数据存储带来了新的挑战。然而，存储器的成本较高且存储空间有限，通过硬件升级来无限制地扩充存储空间并不可行。为此，使用数据压缩技术可以减少存储成本和通信开销。为减少数据发布阶段使用匿名技术产生的数据的存储空间，提出了 k-匿名模型隐私保护数据压缩方案。对于 k匿名模型的原始数据，按照设定的规则及原始数据同匿名数据之间的预设泛化层次关系计算两者的差值，并根据差值数据具有的频率特性对差值进行哈夫曼编码压缩。通过存储差值可以间接获得原始数据，从而减少原始数据的存储空间。对于 k-匿名模型的匿名数据，根据模型的泛化规则或预设泛化层次关系，匿名数据通常具有较高的重复性，且设定的k值越大，匿名数据的泛化程度越高、重复性越强。对匿名数据设计实现哈夫曼编码压缩，减少匿名数据的存储空间。实验结果表明，所提方案能够显著降低 k-匿名模型的原始数据及匿名数据的压缩率。在使用的5个k-匿名模型及不同k值的设定情况下，与Windows 11的zip工具相比，所提方案的原始数据压缩率和匿名数据压缩率平均降低了72.2%、64.2%。

Abstract

The k-anonymity model is widely used as a data anonymization technique for privacy protection during the data release phase.However

with the advent of the big data era

the generation of vast amounts of data poses challenges to data storage.However

it is not feasible to expand the storage space infinitely by hardware upgrade

since the cost of memory is high and the storage space is limited.For this reason

data compression techniques can reduce storage costs and communication overhead.In order to reduce the storage space of the data generated by using anonymization techniques in the data publishing phase

a compression scheme was proposed for the original data and anonymized data of the k-anonymity model.For the original data of the k-anonymity model

the difference between the original data and the anonymized data was calculated according to the set rules and the pre-defined generalization level.Huffman coding compression was applied to the difference data according to frequency characteristics.By storing the difference data

the original data can be obtained indirectly

thus reducing the storage space of the original data.For anonymized data of the k-anonymity model

the anonymized data usually have high repeatability according to the generalization rules of the model or the pre-defined generalization hierarchy relations.The larger the value of k

the more generalized and repeatable the anonymized data becomes.The design of Huffman coding compression was implemented for anonymous data to reduce storage space.The experimental results show that the proposed scheme can significantly reduce the original data and the anonymous data compression rate of the k-anonymity model.Across five models and variousk-value settings

the proposed scheme reduces the compression rate of raw and anonymized data by 72.2% and 64.2% on average compared to the Windows 11 zip tool.

关键词

Keywords

references

方滨兴 , 贾焰 , 李爱平 , 等 . 大数据隐私保护技术综述 [J ] . 大数据 , 2016 , 2 ( 1 ): 1 - 18 .

FANG B X , JIA Y , LI A P , et al . An overview of big data privacy protection technologies [J ] . Big Data , 2016 , 2 ( 1 ): 1 - 18 .

SAMARATI P , SWEENEY L . Protecting privacy when disclosing information:k-anonymity and its enforcement through generalization and suppression [C ] // Proc of the IEEE Symposium on Research in Security and Privacy . 1998 : 384 - 393

SWEENEY L . K-anonymity:a model for protecting privacy [J ] . International Journal of Uncertainty Fuzziness and Knowledge Based Systems , 2002 , 10 ( 5 ): 557 - 570 .

WU S , WANG X L , WANG S , et al . K-anonymity for crowdsourcing database [J ] . IEEE Transactions on Knowledge and Data Engineering , 2014 , 26 ( 9 ): 2207 - 2221 .

KABIR H , MAHMOOD A , WANG H , et al . Microaggregation sorting framework for k-anonymity statistical disclosure control in cloud computing [J ] . IEEE Transactions on Cloud Computing , 2015 , 8 ( 2 ): 408 - 417 .

WANG J B , CAI Z P , YU J G . Achieving personalized k-anonymity-based content privacy for autonomous vehicles in CPS [J ] . IEEE Transactions on Industrial Informatics , 2020 , 16 ( 6 ): 4242 - 4251 .

FEI F , LI S , DAI H P , et al . A k-anonymity based schema for location privacy preservation [J ] . IEEE Transactions on Sustainable Computing , 2019 , 4 ( 2 ): 156 - 167 .

XING L , JIA X F , GAO J P , et al . A location privacy protection algorithm based on double k-anonymity in the social internet of vehicles [J ] . IEEE Communications Letters , 2021 , 25 ( 10 ): 3199 - 3203 .

JAYASANKAR U , THIRUMAL V , PONNURANGAM D . A survey on data compression techniques:from the perspective of data quality,coding schemes,data type and applications [J ] . Journal of King Saud University-Computer and Information Sciences , 2021 , 33 ( 2 ): 119 - 140 .

LAI H , XU M , XU J , et al . Evaluating data storage structures of MapReduce [C ] // 2013 8th International Conference on Computer Science ＆ Education . 2013 : 1041 - 1045 .

DING X , TIAN B , LI Y . A scheme of structured data compression and query on Hadoop platform [C ] // 2015 Third International Conference on Digital Information,Networking,and Wireless Communications (DINWC) . 2015 : 160 - 164 .

HUFFMAN D A . A method for the construction of minimum-redundancy codes [J ] . Proceedings of the IRE , 1952 , 40 ( 9 ): 1098 - 1101 .

PAI Y T , CHENG F C , LU S P , et al . Sub-trees modification of Huffman coding for stuffing bits reduction and efficient NRZI data transmission [J ] . IEEE Transactions on Broadcasting , 2012 , 58 ( 2 ): 221 - 227 .

ALZAHIR S , BORICI A . An innovative lossless compression method for discrete-color images [J ] . IEEE Transactions on Image Processing , 2014 , 24 ( 1 ): 44 - 56 .

YIN Z , XIANG Y , ZHANG X . Reversible data hiding in encrypted images based on multi-MSB prediction and Huffman coding [J ] . IEEE Transactions on Multimedia , 2019 , 22 ( 4 ): 874 - 884 .

YI X , YANG K , ZHAO X , et al . AHCM:adaptive Huffman code mapping for audio steganography based on psychoacoustic model [J ] . IEEE Transactions on Information Forensics and Security , 2019 , 14 ( 8 ): 2217 - 2231 .

FIRMANSAH L , SETIAWAN E B . Data audio compression lossless FLAC format to lossy audio MP3 format with Huffman shift coding algorithm [C ] // 2016 4th International Conference on Information and Communication Technology (ICoICT) . 2016 : 1 - 5 .

SWEENEY L . Computational disclosure control:primer on data privacy protection [D ] . Massachusetts Institute of Technology , 2001 : 67 - 82 .

LEFEVRE K , DEWITT D J , RAMAKRISHNAN R . Incognito:efficient full-domain k-anonymity [C ] // Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data . 2005 : 49 - 60 .

FUNG B C M , WANG K , Y P S . Top-down specialization for information and privacy preservation [C ] // 21st International Conference on Data Engineering (ICDE'05) . 2005 : 205 - 216 .

LEFEVRE K , DEWITT D J , RAMAKRISHNAN R . Mondrian multidimensional k-anonymity [C ] // 22nd International Conference on Data Engineering (ICDE'06) . 2006 : 25 - 35 .

LEFEVRE K , DEWITT D J , RAMAKRISHNAN R . Workload-aware anonymization [C ] // Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining . 2006 : 277 - 286 .

ASUNCION A , NEWMAN D . UCI machine learning repository [R ] . 2007 .

Views

224

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Privacy-preserving multi-dimensional multi-function data aggregation scheme in smart grid

Survey on incentive-driven federated learning: privacy and security

Multi-party summation query method based on differential privacy

Privacy-preserving scheme for logistics systems based on 2D code and information hiding

Data privacy preservation for the search of Internet of things based on fine-grained authorization

Related Author

ZHU Shuaishuai

WU Xuguang

YAO Wujun

LI Yu

WU Liqiang

HAN Yiliang

WANG Yuanyuan

XIONG Ping

Related Institution

College of Cryptography Engineering, Armed Police Engineering University

Key Laboratory of Counter-Terrorism Command Information Engineering of the Ministry of Education, Armed Police Engineering University

School of Information Engineering, Zhongnan University of Economics and Law

Faculty of Date Science, City University of Macau, Macau

School of Computer Science, Beijing University of Posts and Telecommunications

⁰