摘要
针对本地化差分隐私中的隐私-效用均衡问题,对差分隐私和近似差分隐私情形下的二元广义随机响应机制建立效用优化模型,并采用图解法、最优性证明、软件求解和极值点等方法求解,得到了效用最优值与隐私预算、输入数据分布的精确表达式,给出了相应的效用最优机制。研究结果表明效用最优值和效用最优机制均与隐私预算和输入数据分布相关。另外,多元随机响应机制效用优化模型可通过本地化差分隐私极值点来求解。
For the study of privacy-utility trade-off in local differential privacy, the utility optimization models of binary generalized random response mechanism for the case of differential privacy and approximate differential privacy were established. By graphic method, optimality proof, software solution and extreme point method, the exact expression of the optimal utility with privacy budget and the distribution of input data was obtained, and the corresponding optimal randomized response mechanism was given. The results show that both the optimal utility and optimal mechanism are related to privacy budget and input data distribution. Moreover, the discussion for multivariate randomized response mechanism shows that the method of extreme points of local differential privacy is feasible to the solution.
引文
[1]DWORKC,ROTHA.Thealgorithmicfoundationsofdifferential privacy[J]. Foundations and Trends in Theoretical Computer Science,2014, 9(3-4):211-407.
[2]TANG J, KOROLOVAA, BAI X, et al. Privacy loss inapple’s implementation of differential privacy on MacOS 10.12[J]. Cornell University, arXiv Preprint, arXiv:1709.02753, 2017.
[3]ERLINGSSONú, PIHUR V, KOROLOVA A. RAPPOR:randomized aggregatableprivacy-preservingordinalresponse[C]//TheACM SIGSACConferenceonComputerandCommunicationsSecurity.ACM, 2014:1054-1067.
[4]WARNER S L. Randomized response:a survey technique for eliminating evasive answer bias[J]. Journal of the American Statistical Association, 1965, 60(309):63-69.
[5]COMAS J S, FERRER J D. Optimal data-independent noise for differential privacy[J]. Information Sciences, 2013, 250:200-214.
[6]GENGQ,KAIROUZP,OHS,etal.Thestaircasemechanismin differentialprivacy[J].IEEEJournalofSelectedTopicsinSignal Processing, 2015, 9(7):1176-1184.
[7]GENG Q, VISWANATH P. The optimal noise-adding mechanism in differentialprivacy[J].IEEETransactionsonInformationTheory,2016, 62(2):925-951.
[8]GENGQ,VISWANATHP.Optimalnoiseaddingmechanismsfor approximate differential privacy[J]. IEEE Transactions on Information Theory, 2016, 62(2):952-969.
[9]HOLOHAN N, LEITH D J, MASON O. Optimal differentially private mechanisms for randomized response[J]. IEEE Transactions on Information Forensics&Security,2017, 12(11):2726-2735.
[10]邓成梁.运筹学的原理和方法:第三版[M].武汉:华中科技大学出版社, 2014.DENG C L. The Principle and Method of Operations Research[M]. 3rd ed. Wuhan:Huazhong University of Science&Technology Press, 2014.
[11]KAIROUZ P, OH S, VISWANATHP. Extremal mechanisms for local differentialprivacy[J].JournalofMachineLearningResearch,2016, 4(1):492-542.
[12]HOLOHAN N, LEITHD J, MASON O. Extreme points of the local differential privacy polytope[J]. Linear Algebra and Its Applications,2017, 534:78-96.