西安电子科技大学学报（自然科学版）2023，Vol.50Issue(6)：219-236,18.DOI:10.19665/j.issn1001-2400.20230207
混洗差分隐私保护的度分布直方图发布算法
Histogram publishing algorithm for degree distribution via shuffled differential privacy
摘要
Abstract
At present,the existing histogram publishing algorithms based on centralized or local differential privacy for graph data degree distribution can neither balance the privacy and utility of published data,nor preserve the identity privacy of end users.To solve this problem,a histogram publishing algorithm for degree distribution via shuffled differential privacy(SDP)is proposed under the framework of Encode-Shuffle-Analyze.First,a privacy preserving framework for histogram publishing of degree distribution is designed based on shuffled differential privacy.In this framework,the noisy impact that the encoder brings to distributed users is reduced by employing interactive user grouping,the shuffler and the square wave noise mechanism,while adding noise via local differential privacy.The noisy histogram of degree distribution is reconciled via the maximum likelihood estimation at the analyzer end,thus improving the utility of published data.Second,specific algorithms are proposed for concreting distributed user grouping,adding shuffled differential privacy noise and reconciling the noisy data,respectively.Furthermore,it is proved that these algorithms meet the requirement of(ε,σ)-SDP.Experiments and comparisons illustrate that the proposed algorithms can preserve the privacy of distributed users,and that the data utility is improved more than 26%with metrics in terms of L1 distance,H distance and MSE in comparison with the existing related algorithms.The proposed algorithms also perform with a low overhead and stable data utility,and are suitable for publishing and sharing the histogram of degree distribution for different scales of graph data.关键词
隐私保护技术/图结构/混洗差分隐私/度分布直方图发布/数据效用Key words
privacy-preserving techniques/graph structures/shuffled differential privacy/degree distribution histogram publishing/data utility分类
信息技术与安全科学引用本文复制引用
丁红发,傅培旺,彭长根,龙士工,吴宁博..混洗差分隐私保护的度分布直方图发布算法[J].西安电子科技大学学报（自然科学版）,2023,50(6):219-236,18.基金项目
国家自然科学基金(62002080) （62002080）
贵州财经大学校级项目(2021KYYB14) （2021KYYB14）
