基于差分隐私的非等距直方图发布算法

doi:10.3969/j.issn.0255-8297.2024.06.013

应用科学学报 ›› 2024, Vol. 42 ›› Issue (6): 1052-1063.doi: 10.3969/j.issn.0255-8297.2024.06.013

基于差分隐私的非等距直方图发布算法

单丽洋^1,2,3, 陈学斌^1,2,3, 郭如敏^1,2,3

1. 华北理工大学理学院, 河北唐山 063210;
2. 华北理工大学河北省数据科学与应用重点实验室, 河北唐山 063210;
3. 华北理工大学唐山市数据科学重点实验室, 河北唐山 063210

收稿日期:2024-03-21 出版日期:2024-11-30 发布日期:2024-11-30
通信作者: 陈学斌,教授,研究方向为大数据安全、物联网安全、网络安全。E-mail:chxb@ncst.edu.cn E-mail:chxb@ncst.edu.cn
基金资助:
国家自然科学基金（No.U20A20179）资助

Non-isometric Histogram Publishing Algorithm Based on Differential Privacy

SHAN Liyang^1,2,3, CHEN Xuebin^1,2,3, GUO Rumin^1,2,3

1. College of Science, North China University of Science and Technology, Tangshan 063210, Hebei, China;
2. Hebei Provincial Key Laboratory of Data Science and Application, North China;University of Science and Technology, Tangshan 063210, Hebei, China;
3. Tangshan Key Laboratory of Data Science, North China University of Science and Technology, Tangshan 063210, Hebei, China

Received:2024-03-21 Online:2024-11-30 Published:2024-11-30

摘要/Abstract

摘要： 针对直方图隐私泄露与分组数难以确定的问题，提出一种基于差分隐私的非等距直方图数据发布算法。首先，提出一种改进的定量化的综合评价指标，将直方图的分组评判标准定量化为特定的计算公式，以确定直方图最优分组数。然后，利用经验分布函数设计隐私预算分配方案，计算得出分组边界，从而构建非等距直方图。最后，根据非等距边界划分的分组，统计组内频数，对频数进行加噪，发布满足差分隐私的非等距直方图。实验结果表明，分组数的最优计算及非等距的实现，保证了直方图发布数据的准确性和隐私性，同时仍能保证直方图的分布特征不受影响，该文所提发布算法的均方误差与同类精确的直方图发布（accurate histogram publication,AHP）算法相比降低了99%。

关键词: 非等距, 直方图分组, 差分隐私, 隐私预算

Abstract: To address the histogram privacy leakage and the challenge of determining the number of groups, a non-equidistant histogram data publishing algorithm based on differential privacy (DP) is proposed. Firstly, an improved quantified comprehensive evaluation index is introduced, which quantifies the criterion of histogram grouping into a specific calculation formula to determine the optimal number of histogram groups. Next, the empirical distribution function is used to design a privacy budget allocation scheme, and the grouping boundaries are calculated to construct the non-equidistant histogram. The dataset is then divided according to the non-equidistant boundaries, and the frequencies are counted, with noise added to satisfy the differential privacy requirements. The non-equidistant histogram is subsequently published. Experimental results show that the optimal calculation of the number of groups and the implementation of non-equidistance can ensure the accuracy and privacy of the published data of the histogram, while preserving the distribution characteristics of the histogram. The mean square error of the proposed algorithm is reduced by 99% compared with similar accurate histogram publication (AHP) algorithms.

Key words: non-isometric, histogram grouping, differential privacy (DP), privacy budget

中图分类号:

TP309

单丽洋, 陈学斌, 郭如敏. 基于差分隐私的非等距直方图发布算法[J]. 应用科学学报, 2024, 42(6): 1052-1063.

SHAN Liyang, CHEN Xuebin, GUO Rumin. Non-isometric Histogram Publishing Algorithm Based on Differential Privacy[J]. Journal of Applied Sciences, 2024, 42(6): 1052-1063.

参考文献

[1] Chen S, Fu A, Yu S, et al. DP-QIC: a differential privacy scheme based on quasi-identifier classification for big data publication [J]. Soft Computing, 2021, 25: 7325-7339.
[2] Zheng X, Yan K, Duan J, et al. Histogram publication over numerical values under local differential privacy [J]. Wireless Communications and Mobile Computing, 2021, 4: 1-11.
[3] Joshuva A, Sugumaran V. Comparative study on tree classifiers for application to condition monitoring of wind turbine blade through histogram features using vibration signals: a datamining approach [J]. Structural Durability & Health Monitoring, 2019, 13(4): 399-416.
[4] Sturges H A. The choice of a class interval [J]. Journal of the American Statistical Association, 1926, 21(153): 65-66.
[5] Scott D W. On optimal and data-based histograms [J]. Biometrika, 1979(3): 605-610.
[6] Rudemo M. Empirical choice of histogram and kernel density estimators [J]. Scandinavian Journal of Statistics, 1982(9): 65-78.
[7] Wang X X, Zhang J F. Histogram-kernel error and its application for bin width selection in histograms [J]. Acta Mathematicae Applicatae Sinica, English Series, 2012, 28(3): 607-624.
[8] 张建方, 王秀祥. 直方图理论与最优直方图制作[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. (in Chinese)
[9] Dwork C, Smith A. Differential privacy for statistics: what we know and what we want to learn [J]. Journal of Privacy and Confidentiality, 2009, 1(2): 135-154.
[10] 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: 587-595.
[11] 陈婷, 罗景青. 基于直方图最优分组的雷达信号特征参数分析[J]. 微电子学与计算机, 2009, 26(3): 162-165. Chen T, Luo J Q. Analysis of radar signal feature parameters based on optimal grouping of histogram [J]. Microelectronics and Computer, 2009, 26(3): 162-165. (in Chinese)
[12] 杨磊, 郑啸, 赵伟. 基于差分隐私的非等距直方图发布方法[J]. 网络与信息安全学报, 2020, 6(3): 39-49. Yang L, Zheng X, Zhao W. Non-isometric histogram publishing method based on differential privacy [J]. Journal of Network and Information Security, 2020, 6(3): 39-49. (in Chinese)
[13] 徐文涛, 李林森, 钮佳超, 等. 一种基于桶重构的差分隐私直方图发布方法[J]. 通信技术, 2019, 52(2): 409-417. Xu W T, Li L S, Niu J C, et al. A differential privacy histogram publishing method based on barrel reconstruction [J]. Communications Technology, 2019, 52(2): 409-417. (in Chinese)
[14] 张浩铭, 刘田天, 龙士工. 优化结构下的差分隐私直方图发布[J]. 计算机仿真, 2019, 36(3): 220-224. Zhang H M, Liu T T, Long S G. Differential privacy histogram release under the optimized structure [J]. Computer Simulation, 2019, 36(3): 220-224. (in Chinese)
[15] Lemzin A. Streaming data processing [J]. Asian Journal of Research in Computer Science, 2023, 15(1): 11-21.
[16] 王修君, 莫磊, 郑啸, 等. 面向数据流滑动窗口的自适应直方图发布算法[J]. 计算机科学, 2022, 49(10): 344-352. Wang X J, Mo L, Zheng X, et al. Adaptive histogram publishing algorithm for data flow sliding window [J]. Computer Science, 2022, 49(10): 344-352. (in Chinese)
[17] Gao R, Ma X. Dynamic data histogram publishing based on differential privacy [C]//IEEE International Conference on Parallel & Distributed Processing with Applications, Ubiquitous Computing & Communications, Big Data & Cloud Computing, Social Computing & Networking, Sustainable Computing & Communications (ISPA/IUCC/BDCloud/SocialCom/SustainCom), 2018: 737-743.
[18] Li Y L, Li S Y. Research on differential private streaming histogram publication algorithm [C]//Proceedings of the 20185th IEEE International Conference on Cloud Computing and Intelligence Systems (CCIS), 2018: 598-603.
[19] Chen Q, Ni Z, Zhu X, et al. Differential privacy histogram publishing method based on dynamic sliding window [J]. Frontiers of Computer Science, 2022, 17(4): 174809.
[20] Dwork C. Differential privacy [C]//Proceedings of the 2006 International Colloquium on Automata, Languages, and Programming, 2006: 1-12.
[21] 莫磊, 王修君, 郑啸, 等. 有效的基于滑动窗口数据流直方图方法[J]. 计算机应用研究, 2021, 38(7): 2085-2090. Mo L, Wang X J, Zheng X, et al. A valid sliding window-based data flow histogram method [J]. Application Research of Computers, 2021, 38(7): 2085-2090. (in Chinese)
[22] 李昆明, 王超迁, 倪巍伟, 等. 基于差分隐私的高精度直方图发布方法[J]. 计算机应用, 2020, 40(11): 3242-3248. Li K M, Wang C Q, Ni W W, et al. High-precision histogram publishing method based on differential privacy [J]. Journal of Computer Applications, 2020, 40(11): 3242-3248. (in Chinese)
[23] 唐海霞, 杨庚, 白云璐. 自适应差分隐私预算分配策略的直方图发布算法[J]. 计算机应用研究, 2020, 37(7): 1952-1957, 1963. Tang H X, Yang G, Bai Y L. A histogram publishing algorithm for the adaptive differential privacy budget allocation strategy [J]. Application Research of Computers, 2020, 37(7): 1952-1957, 1963. (in Chinese)

基于差分隐私的非等距直方图发布算法

Non-isometric Histogram Publishing Algorithm Based on Differential Privacy

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 2

编辑推荐

Metrics

本文评价

[1]	焦合军, 周万春, 施进发, 刘晟源. 基于差分隐私保护的服务机器人视觉图像发布算法[J]. 应用科学学报, 2023, 41(4): 682-691.
[2]	叶云, 石聪聪, 余勇, 怀梦迪, 林为民, 高鹏. 保护隐私的分布式朴素贝叶斯挖掘[J]. 应用科学学报, 2017, 35(1): 1-10.