Non-equal-width histogram publishing method based on differential privacy

Lei YANG; Xiao ZHENG; Wei ZHAO

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

您当前的位置：

首页 >

文章列表页 >

Non-equal-width histogram publishing method based on differential privacy

Special Column: New Technology Exploration on Privacy Protection | 更新时间：2024-06-03

- Non-equal-width histogram publishing method based on differential privacy
- Chinese Journal of Network and Information Security Vol. 6, Issue 3, Pages: 39-49(2020)
- 作者机构：
  
  1. 安徽工业大学计算机科学与技术学院安徽马鞍山 243032
  2. 安徽省工业互联网智能应用与安全工程实验室安徽马鞍山 243032
- 作者简介：
- 基金信息：
- DOI：10.11959/j.issn.2096-109x.2020035
  CLC： TP309.2
- Online First：2020-06，
  
  Published：15 June 2020
- 稿件说明：
移动端阅览
Lei YANG, Xiao ZHENG, Wei ZHAO. Non-equal-width histogram publishing method based on differential privacy[J]. Chinese Journal of Network and Information Security, 2020, 6(3): 39-49.
DOI：

Lei YANG, Xiao ZHENG, Wei ZHAO. Non-equal-width histogram publishing method based on differential privacy[J]. Chinese Journal of Network and Information Security, 2020, 6(3): 39-49. DOI： 10.11959/j.issn.2096-109x.2020035.

摘要

已有的基于差分隐私的直方图发布技术在利用直方图反映数据的真实分布特征时可能会出现“重拖尾”和“零桶”现象，并且在数据量较多处“过于平缓”；另外，已有技术对原始直方图进行差分隐私保护时未考虑每个分组所蕴含的信息量大小不同。针对以上问题，提出一种基于差分隐私的非等距直方图发布方法。首先，利用经验分布函数根据数据稀疏性合理构建非等距直方图；然后，在非等距直方图上应用差分隐私保护技术对原始非等距直方图进行隐私保护；最后，根据非等距直方图的组距大小为每组设置隐私预算以提高每组数据的隐私性。实验结果表明，所提方法在差分隐私下进行直方图发布时充分考虑了数据分布的稀疏性，有效避免了直方图的“重拖尾”和“零桶”现象，保证了所发布直方图反映数据分布特征的准确性；并且为每组添加符合拉普拉斯（Laplace）机制的噪声时，根据组距为每组设置合理的隐私预算，在一定程度上提高了不同数据段的隐私性。

Abstract

Existing histogram publishing technology based on differential privacy may show phenomenon of＆quot;retracting＆quot; and ＆quot;zero bucket＆quot; when histogram is used to reflect the real distribution characteristics of data

and ＆quot;too gentle＆quot; in the case of large data volume.In addition

the existing technology of the original histogram difference of privacy protection when not considering the amount of information of each group is different.In view of the above problems

a kind of non-equal-width histogram publishing method based on differential privacy was proposed.First of all

a non-isometric histogram based on the sparseness of the data should bereasonably constructed by empirical distribution function.Secondly

differential privacy protection technology should be applied to non-equal-width histogram to protect the privacy of the original non-equal-width histogram.Finally

the privacy budget should be set for each group according to the class widths of the non-equal-width histogram to improve the privacy of each group of data.The experimental results show that the sparseness of the data distribution is fully taken into account when using the proposed method to perform histogram publishing under differential privacy

effectively avoid the phenomenon of histogram with “retracting” and “zero barrels”

and the accuracy of the published histogram for reflecting the characteristics of the data distribution is guaranteed.Also

when adding noise in line with Laplace mechanism to each group

setting a reasonable privacy budget for each group according to the class widths to some extent increases the privacy of different data segments.

关键词

Keywords

references

林子雨 . 大数据技术原理与应用 [M ] . 北京 : 人民邮电出版社 , 2015 .

LIN Z Y . BigData technology and application [M ] . Beijing : Posts and Telecom PressPress , 2015 .

李森有 , 季新生 , 游伟 . 基于置信度分析的差分隐私保护参数配置方法研究 [J ] . 网络与信息安全学报 , 2019 ( 4 ): 29 - 39 .

LI S Y , JI X S , YOU W . Research on differential privacy protection parameter configuration method based on confidence level [J ] . Chinese Journal of Network and Information Security , 2019 , 5 ( 4 ): 29 - 39 .

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

MACHANAVAJJHALA A , GEHRKE J , KIFER D , et al . L-diversity:privacy beyond k-anonymity [C ] // 22nd International Conference on Data Engineering . 2006 :3.

LI N , LI T , VENKATASUBRAMANIAN S . T-Closeness:privacy beyond k-anonymity and l-diversity [C ] // 2007 IEEE 23rd International Conference on Data Engineering . 2007 .

DWORK C , . Differential privacy [C ] // International Colloquium on Automata,Languages,and Programming . Berlin:Springer , 2006 .

DWORK C , MCSHERRY F , NISSIM K , et al . Calibrating noise to sensitivity in private data analysis [C ] // Theory of Cryptography Conference . Berlin:Springer , 2006 .

XU J , ZHANG Z , XIAO X , et al . Differentially private histogram publication [C ] // IEEE International Conference on Data Engineering . 2012 .

JAGADISH H V , KOUDAS N , MUTHUKRISHNAN S , et al . Optimal histograms with quality guarantees [C ] // VLDB . 1998 : 275 - 286 .

ZHANG X , CHEN R , XU J , et al . Towards accurate histogram publication under differential privacy [C ] // Proceedings of the 2014 SIAM International Conference on Data Mining . 2014 .

张啸剑 , 邵超 , 孟小峰 . 差分隐私下一种精确直方图发布方法 [J ] . 计算机研究与发展 , 2016 , 53 ( 5 ): 1106 - 1117 .

ZHANG X J , SHAO C , MENG X F . Accurate histogram release under differential privacy [J ] . Journal of Computer Research and Development , 2016 , 53 ( 5 ): 1106 - 1117 .

HUI L , CUI J , LIN X , et al . Improving the utility in differential private histogram publishing:theoretical study and practice [C ] // IEEE International Conference on Big Data . 2017 .

唐海霞 , 杨庚 , 白云璐 . 一种自适应差分隐私预算分配策略的直方图发布算法 [J ] . 计算机应用研究 , 2020 ( 1 ): 1 - 8 .

TANG H X , YANG G , BAI Y L . Histogram publishing algorithm based on adaptive privacy budget allocation strategy under differential privacy [J ] . Application Research of Computers , 2020 ( 1 ): 1 - 8 .

BKAKRIA A , TASIDOU A , CUPPENS-BOULAHIA N , et al . Optimal distribution of privacy budget in differential privacy [C ] // Risks and Security of Internet and Systems(CRiSIS 2018) . 2018 .

杨军 . 一种基于经验分布函数的不等组距直方图的绘制方法 [P ] . 2015 .

YANG J . A method for drawing unequal spacing histograms based on empirical distribution functions [P ] . 2015 .

ZHU T , LI G , ZHOU W , et al . Differentially private data publishing and analysis:a survey [J ] . IEEE Transactions on Knowledge and Data Engineering , 2017 : 1 - 1 .

DWORK C , ROTH A . The algorithmic foundations of differential privacy [J ] . Theoretical Computer Science , 2013 , 9 ( 3-4 ): 211 - 407 .

张建方 , 王秀祥 . 直方图理论与最优直方图制作 [J ] . 应用概率统计 , 2009 , 25 ( 2 ): 201 - 214 .

ZHANG J F , WANG X X . Histogram theories and optimal histogram construction algorithms [J ] . Chinese Journal of Applied Probability and Statistics , 2009 , 25 ( 2 ): 201 - 214 .

Views

256

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

A differentially-private mechanism for multi-level data publishing

DP-FedDRC: differentially private personalized federated learning to alleviate dimension collapse

FLWD:A Webshell detection method based on federated learning

Survey on incentive-driven federated learning: privacy and security

Survey of differentially private methods for trajectory data

Related Author

Hui LI

Wen-jing ZHANG

Hu Changhui

Zhang Yuhao

Wang Minli

WU Shuixiu

CHAI Jiangli

ZENG Qingpeng

Related Institution

School of Cyberspace Security (School of Cryptography), Hainan University

School of Computer Information Engineering, Jiangxi Normal University

School of Mathematics and Computer Sciences, Nanchang University

Faculty of Date Science, City University of Macau, Macau

School of Information Engineering, Zhongnan University of Economics and Law

⁰