计算机科学 ›› 2023, Vol. 50 ›› Issue (2): 333-345.doi: 10.11896/jsjkx.220700273
刘利康, 周春来
LIU Likang, ZHOU Chunlai
摘要: 文中主要围绕差分隐私查询中的均值估计问题展开论述,介绍了目前主流的数值型数据均值估计的本地差分隐私设计方案,首次引入随机响应技术中的随机截尾机制来揭示本地差分隐私下均值计算的基本原理,提出了关于均值估计方差的效用优化定理,给出了边界优化公式,从而提高了该领域效用优化理论的可解释性和可操作性。基于该理论,首次提出了一种实用、简洁、高效的均值估计算法协议RCP,可用于收集和分析连接到互联网的智能设备用户的数据,同时满足本地差分隐私要求。RCP构造简单,支持在任意数量的数值属性上执行数据分析任务,通信与计算高效,有效缓解了现有算法设计复杂、优化困难、效率较低等实际问题。最后,通过实证研究证明了所提方法在效用、效率和渐进误差界限上优于现有的其他方案。
中图分类号:
[1]DWORK C.Differential Privacy[C]//The 33rd InternationalColloquium on Automata,Languages and Programming(ICALP).2006:1-12. [2]DWORK C,MCSHERRY F,NISSIM K,et al.Calibrating noise to sensitivity in private data analysis[M]//Theory of Cryptography.Springer,2006. [3]DWORK C,ROTH A.The algorithmic foundations of differential privacy[J].Foundations and Trends in Theoretical Compu-ter Science,2014,9(3/4):211-407. [4]DWORK C,LEI J.Differential Privacy and Robust Statistics[C]//Proceedings of the 41st ACM Symposium on Theory of Computing.New York:Association for Computing Machinery,2009:371-380. [5]KASIVISWANATHAN S,LEE H K,NISSIM K,et al.What can we learn privately?[J].SIAM Journal on Computing,2011,40(3):793-826. [6]WANG T,ZHANG X F,FENG J Y,et al.A ComprehensiveSurvey on Local Differential Privacy Toward Data Statistics and Analysis[J].Sensors,2020,20(24):7030. [7]YANG M M,LYU L J, ZHAO J,et al.Local Differential Privacy and Its Applications:A Comprehensive Survey[J].arXiv:2008.03686,2020. [8]WARNER S L.Randomized response:A survey technique foreliminating evasive answer bias[J].Journal of the American Statistical Association,1965,60(309):63-69. [9]DUCHI J,JORDAN M,WAINWRIGHT M.Minimax optimal procedures for locally private estimation[J].Journal of the American Statistical Association,2018,113(521):182-201. [10]DUCHI J,JORDAN M,WAINWRIGHT M.Privacy awarelearning[J].Journal of the ACM(JACM),2014,61(6):38. [11]DUCHI J,JORDAN M,WAINWRIGHT M.Local privacy and statistical minimax rates[C]//54th Annual Symposium on Foundations of Computer Science.IEEE,2013:429-438. [12]KAIROUZ P,OH S,VISWANATH P.Extremal mechanismsfor local differential privacy[J].Advances in Neural Information Processing Systems,2014,2(20):2879-2887. [13]WANG N,XIAO X K,YANG Y,et al.Collecting and analyzing multidimensional data with local differential privacy[C]//35th International Conference on Data Engineering(ICDE).IEEE,2019:638-649. [14]LI Z T,WANG T H,LOPUHAA-ZWAKENBERG M,et al.Estimating Numerical Distributions under Local Differential Privacy[J].arXiv:1912.01051,2019. [15]NGUYEN T,XIAO X K,YANG Y,et al.Collecting and analyzing data from smart device users with local differential privacy[J].arXiv:1606.05053,2016. [16]DALENIUS T,VITALE R A.A new randomized response design for estimating the mean of a distribution[M]//Contributions to Statistics.1979:43-47. [17]GREENBERG B G,KUEBLER J R R R,ABERNATHY J R,et al.Application of the randomized response technique in obtaining quantitative data[J].Journal of the American Statistical Association,1971,66(334):243-250. [18]CHAUDHURI A,MUKHERJEE R.Randomized responsetechniques:a review[J].Statistica Neerlandica,1987,41(1):27-44. [19]WARNER S L.The linear randomized response model[J].Journal of the American Statistical Association,1971,66(336):884-888. [20]WARNER S L.Optimal randomized response models[J].International Statistical Review/Revue Internationale de Statistique,1976,15(8):205-212. [21]BASSILY R,SMITH A.Local,Private,Efficient Protocols forSuccinct Histograms[C]//Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing.ACM,2015:127-135. [22]ACHARYA J,SUN Z,ZHANG H.Hadamard response:Estimating distributions privately,efficiently,and with little communication[C]//Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics(AISTATS).2019. [23]WANG T H,LOPUHAA-ZWAKENBERG M,LI Z T,et al.Locally Differentially Private Frequency Estimation with Consistency[C]//27th Annual Network and Distributed System Security Symposium,NDSS 2020.San Diego,California,USA,2020. [24]ERLINGSSON U,PIHUR V,KOROLOVA A.Rappor:Ran-domized aggregatable privacy-preserving ordinal response[C]//Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security.ACM,2014:1054-1067. [25]BEBENSEE B.Local differential privacy:a tutorial[J].arXiv:1907.11908,2019. [26]BASSILY R.Linear queries estimation with local differentialprivacy[C]//AISTATS.2019. [27]WANG T,BLOCKI J,LI N,et al.Locally differentially private protocols for frequency estimation[C]//USENIX Security.2017. [28]ZHANG X J,FU N,MENG X F.Towards Spatial Range Queries Under Local Differential Privacy[J].Journal of Computer Research and Development,2020,57(4):847-858. [29]ZHANG X J,FU N,MENG X F.Key-Value Data Accurate Collection under Local Differential Privacy[J].Chinese Journal of Computers,2020,43(8):1479-1492. [30]YE Q Q,MENG X F,ZHU M J,et al.Survey on local differen- tial privacy[J].Ruan Jian Xue Bao/Journal of Software,2018,29(7):1981-2005. [31]ZHU S X,WANG L,SUN G L.A Perturbation Mechanism for Classified Transformation Satisfying Local Differential Privacy[J].Journal of Computer Research and Development,2021,59(2):430-439. [32]LIU Y X,CHEN H,LIU Y H,et al.Privacy-preserving Techniques in Federated Learning[J].Ruan Jian Xue Bao/Journal of Software,2022,33(3):1057-1092. |
[1] | 黄觉, 周春来. 基于本地化差分隐私的频率特征提取 Frequency Feature Extraction Based on Localized Differential Privacy 计算机科学, 2022, 49(7): 350-356. https://doi.org/10.11896/jsjkx.210900229 |
[2] | 时坤, 周勇, 张启亮, 姜顺荣. 基于联盟链的能源交易数据隐私保护方案 Privacy-preserving Scheme of Energy Trading Data Based on Consortium Blockchain 计算机科学, 2022, 49(11): 335-344. https://doi.org/10.11896/jsjkx.220300138 |
[3] | 孙林, 平国楼, 叶晓俊. 基于本地化差分隐私的键值数据关联分析 Correlation Analysis for Key-Value Data with Local Differential Privacy 计算机科学, 2021, 48(8): 278-283. https://doi.org/10.11896/jsjkx.201200122 |
|