Computer Science ›› 2023, Vol. 50 ›› Issue (2): 333-345.doi: 10.11896/jsjkx.220700273

• Information Security • Previous Articles     Next Articles

RCP:Mean Value Protection Technology Under Local Differential Privacy

LIU Likang, ZHOU Chunlai   

  1. School of Information,Renmin University of China,Beijing 100872,China
  • Revised:2022-10-21 Online:2023-02-15 Published:2023-02-22
  • Supported by:
    National Natural Science Foundation of China(61732006)

Abstract: This paper mainly focuses on the mean estimation problem in differential privacy query.After introducing the current mainstream local differential privacy design scheme of numerical data mean estimation,it first introduces the random censoring mechanism in random response technology to reveal the basic principle of mean calculation under local differential privacy,proposes a utility optimization theorem about the variance of mean estimation,and gives a boundary optimization formula,which improves the interpretability and operability of utility optimization theory in this field.Based on this theory,this paper proposes a practical,concise and efficient mean estimation algorithm protocol RCP for the first time,which can be used to collect and analyze the data of intelligent device users connected to the Internet,while meeting the requirements of local differential privacy.RCP is simple in structure,supports data analysis tasks on any number of numerical attributes,and has efficient communication and calculation,effectively alleviating the practical problems of complex algorithm design,difficult optimization,and low efficiency.Finally,empirical research demonstrates that the proposed method outperforms other existing schemes in terms of utility,efficiency and asymptotic error bounds.

Key words: Local differential privacy, Mean estimation, Random response, Random censoring, Utility optimization

CLC Number: 

  • TP309
[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] HUANG Jue, ZHOU Chun-lai. Frequency Feature Extraction Based on Localized Differential Privacy [J]. Computer Science, 2022, 49(7): 350-356.
[2] SHI Kun, ZHOU Yong, ZHANG Qi-liang, JIANG Shun-rong. Privacy-preserving Scheme of Energy Trading Data Based on Consortium Blockchain [J]. Computer Science, 2022, 49(11): 335-344.
[3] SUN Lin, PING Guo-lou, YE Xiao-jun. Correlation Analysis for Key-Value Data with Local Differential Privacy [J]. Computer Science, 2021, 48(8): 278-283.
[4] PENG Chun-chun, CHEN Yan-li, XUN Yan-mei. k-modes Clustering Guaranteeing Local Differential Privacy [J]. Computer Science, 2021, 48(2): 105-113.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!