随机响应机制效用优化研究

doi:10.11959/j.issn.1000-436x.2019088

Journal on Communications ›› 2019, Vol. 40 ›› Issue (6): 74-81.doi: 10.11959/j.issn.1000-436x.2019088

• Papers • Previous Articles Next Articles

Study on utility optimization for randomized response mechanism

ZHOU Yihui¹,LU Laifeng^2,³(),WU Zhenqiang^1,³

¹ School of Computer Science,Shaanxi Normal University,Xi’an 710119,China
² School of Mathematics and Information Science,Shaanxi Normal University,Xi’an 710119,China
³ Guizhou Provincial Key Lab of Public Big Data,Guizhou University,Guiyang 550025,China

Revised:2019-02-13 Online:2019-06-25 Published:2019-07-04
Supported by:
The National Natural Science Foundation of China(61673251);The Natural Science Foundation of Shaanxi Province(2018JM6050);The Natural Science Foundation of Shaanxi Province(2017JQ6038);The Open Project Fund of Guizhou Provincial Key Laboratory of Public Big Data(2017BDKFJJ026);The Open Project Fund of Guizhou Provincial Key Laboratory of Public Big Data(2018BDKFJJ004);The Fundamental Research Funds for the Central Universities(GK201903091);The Fundamental Research Funds for the Central Universities(GK201903011)

Abstract

Abstract:

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.

Key words: local differential privacy, randomized response, utility optimization, extreme point, simplex method

CLC Number:

TP309

ZHOU Yihui,LU Laifeng,WU Zhenqiang. Study on utility optimization for randomized response mechanism[J]. Journal on Communications, 2019, 40(6): 74-81.

Figures/Tables 8

References 12

[1]	DWORK C , ROTH A . Thealgorithmic foundations of differential privacy[J]. Foundations and Trends in Theoretical Computer Science, 2014,9(3-4): 211-407.
[2]	TANG J , KOROLOVAA J , 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 aggregatable privacy-preserving ordinal response[C]// The ACM SIGSAC Conference on Computer and Communications Security. 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]	GENG Q , KAIROUZ P , OH S ,et al. The staircase mechanism in differential privacy[J]. IEEE Journal of Selected Topics in Signal Processing, 2015,9(7): 1176-1184.
[7]	GENG Q , VISWANATH P . The optimal noise-adding mechanism in differential privacy[J]. IEEE Transactions on Information Theory, 2016,62(2): 925-951.
[8]	GENG Q , VISWANATH P . Optimal noise adding mechanisms for 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 PressPress, 2014.
[11]	KAIROUZ P , OH S ， VISWANATHP . Extremal mechanisms for local differential privacy[J]. Journal of Machine Learning Research, 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.

Metrics

Recommended 0

No Suggested Reading articles found!

Study on utility optimization for randomized response mechanism

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 8

References 12

Related Articles 3

Metrics

Recommended 0

[1]	Hanyi WANG, Xiaoguang LI, Wenqing BI, Yahong CHEN, Fenghua LI, Ben NIU. Multi-level local differential privacy algorithm recommendation framework [J]. Journal on Communications, 2022, 43(8): 52-64.
[2]	Yang LIU, Jun LI, Wenyun CHEN, Mugen PENG. Research on endogenous security data sharing mechanism of F-RAN for 6G [J]. Journal on Communications, 2021, 42(1): 67-78.
[3]	Cui-tao ZHU,Zong-kai YANG,Wen-qing CHENG,Di WU,He YAN. Overlay multicast strategy based on utility optimization for wireless mesh networks [J]. Journal on Communications, 2008, 29(6): 108-114.