差分隐私保护参数ε的选取研究

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

摘要/Abstract

摘要：

2006年，差分隐私保护作为一种新的隐私保护范式出现，因其不需要攻击者先验知识的假设，而被认为是一种非常可靠的保护机制。然而，作为隐私保护技术的主要参数ε的意义对于一般用户而言不十分明确。鉴于此，提出一个新的攻击模型，可以用来选取参数ε的值。详细分析了该攻击模型的特点，通过理论证明和模型的实证分析，最后给出了一个参数ε的选取计算式。

关键词: 差分隐私, 攻击模型, 数据隐私

Abstract:

In 2006,differential privacy has emerged as a new paradigm for privacy protection with very conservative assumptions about the adversary’s prior knowledge.It is believed that differential privacy mechanism can provide one of the strongest privacy guarantees.However,the meaning of the privacy budget parameter ε is still unclear for the general application users.In view of this,a new attack model,which can be used to choose the value for the parameter ε was proposed.A careful analytical study of the attack model and theoretical properties of the proposed approach was present.

Key words: differential privacy, attack model, data privacy

何贤芒,王晓阳,陈华辉,董一鸿. 差分隐私保护参数ε的选取研究[J]. 通信学报, 2015, 36(12): 124-130.

Xian-mang HE,Sean WANGX,Hua-hui CHEN,Yi-hong DONG. Study on choosing the parameter ε in differential privacy[J]. Journal on Communications, 2015, 36(12): 124-130.

图/表 4

参考文献 31

[1]	SAMARATI P , SWEENEY L . Generalizing data to provide anonymity when disclosing information (abstract)[A]. Proceedings of the seventeenth ACMSIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems[C]. NewYork, 1998. 188-188.
[2]	DWORK C . Differential privacy[A]. Proceeding of the 33rd International Colloquium on Automata,Languages and Programming (ICALP)[C]. 2006. 1-12
[3]	DWORK C , MCSHERRY F , NISSIM K ,et al. Calibrating Noise to Sensitivity in Private Data Analysis[M]. Theory of cryptography. Berlin: SpringerPress, 2006. 265-284.
[4]	MACHANAVAJJHALA A , KIFER D , GEHRKE J ,et al. L-diversity:privacy beyond k-anonymity[A]. Proceeding of the 22nd International Conference on Data Engineering (ICDE)[C]. 2006. 1-24.
[5]	LI J X , TAO Y F , XIAO X K . Preservation of proximity privacy in publishing numerical sensitive data[A]. Proceeding of the 37th ACM SIGMOD International Conference on Management of Data (SIGMOD)[C]. 2008. 473-486.
[6]	LEE J , CLIFTON C . How much is enough? Choosing ε for differential privacy[A]. Proceeding of the 14th International Conference on Information Security (ISC)[C]. Berlin, 2011. 325-340.
[7]	GEHRKE J , KIFER D , MACHANAVAJJHALA A ,et al. Privacy:theory meets practice on the map[A]. Proceeding of the 24th International Conference on Data Engineering (ICDE)[C]. 2008. 277-286.
[8]	FRANK M . Privacy integrated queries-an extension platform for privacy preserving data analysis[A]. Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data[C]. 2009. 19-30.
[9]	NISSIM K , RASKHODNIKOVA S , SMITH A . Smooth sensitivity and sampling in private data analysis[A]. Proceeding of the 39th ACM Symposium on Theory of Computing (TCC)[C]. 2007. 75-84.
[10]	JOHANNES G , MICHAEL H , EDWARD L ,et al. Crowd-blending pivacy[A]. Proceeding of the 32nd International Conference on Cryptology (CRYPTO)[C]. Berlin, 2012. 479-496.
[11]	CHRIS C , TAMIR T . On syntactic anonymity and differential privacy[J]. Transcations on Data Privacy, 2013,6(2): 161-183.
[12]	NISSIM K , RASKHODNIKOVA S , SMITH A . Smooth sensitivity and sampling in private data analysis[A]. Proceedings of the 39th ACM Symposium on Theory of Computing[C]. 2007. 75-84.
[13]	DWORK C , LEI J . Differential privacy and robust statistics[A]. Proceedings of the 41st Annual ACM Symposium on Theory of Computing[C]. 2009. 371-380.
[14]	MIRONOV I , PANDEY O , REINGOLD O ,et al. Computationaldifferential privacy[A]. Advances in Cryptology,29th Annual InternationalCryptology Conference[C]. Santa Barbara, 2009. 126-142.
[15]	XIAO X K , WANG G Z , JOHANNES G . Differential privacy via wavelet transforms[A]. Proceeding of the 26th Int Conference on Data Engineering (ICDE)[C]. Washington, 2010. 225-236.
[16]	XIAO X , BENDER G , HAY M ,et al. Ireduct:differential privacy with reduced relative errors[A]. Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data[C]. 2011. 229-240.
[17]	CORMODE G , PROCOPIUC C , SRIVASTAVA D ,et al. Differentially private spatial decompositions[A]. Proceeding of the 28th International Conference on Data Engineering (ICDE)[C]. 2012. 20-31.
[18]	ZHANG J , CORMODE G , PROCOPIUC C M ,et al. Privbayes:private data release via bayesian networks[A]. Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data[C]. 2014. 1423-1434.
[19]	CORMODE G , PROCOPIUC C , SRIVASTAVA D ,et al. Differentially private spatial decompositions[A]. Proceeding of the 28th International Conference on Data Engineering (ICDE)[C]. 2012. 20-31.
[20]	LI C , HAY M , RASTOGI V ,et al. Optimizing linear counting queries under differential privacy[A]. Proceedings of the 31st ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems[C]. 2010. 123-134.
[21]	LI C , MIKLAU G . Optimal error of query sets under the differentially-private matrix mechanism[A]. Proceedings of the Joint 2013 EDBT/ICDT Conferences[C]. Italy, 2013. 272-283.
[22]	BHASKAR R , LAXMAN S , SMITH A ,et al. Discovering frequent patterns in sensitive data[A]. Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C]. Washington,DC,USA, 2010. 503-512.
[23]	KOROLOVA A , KENTHAPADI K , MISHRA N ,et al. Releasing search queries and clicks privately[A]. Proceedings of the 18th International Conference on World Wide Web[C]. Madrid,Spain, 2009. 171-180.
[24]	G?TZ M , MACHANAVAJJHALA A , WANG G ,et al. Gehrke:publishing search logs—a comparative study of privacy guarantees[J]. Publication, 2011,24(3): 520-532.
[25]	MCSHERRY F , MAHAJAN R . Differentially-private network trace analysis[A]. Proceedings of the ACMSIGCOMM 2010 Conference on Applications,Technologies,Architectures,and Protocols for Computer Communications[C]. New Delhi,India, 2010. 123-134.
[26]	RASTOGI V , NATH S . Differentially private aggregation of distributed time-series with transformation and encryption[A]. Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data[C]. 2010. 735-746.
[27]	XU J , ZHANG Z , XIAO X ,et al. Differentially private histogram publication[J]. Journal on Very Large Data Bases, 2013,22(6): 797-822.
[28]	LI N H , QARDAJI W , SU D ,et al. Privbasis:frequent itemset mining with differential privacy[J]. PVLDB, 2012,5(11): 1340-1351.
[29]	FRIEDMAN A , SCHUSTER A . Data mining with differential privacy[A]. Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C]. 2010. 493-502.
[30]	RUBINSTEIN B I P , BARTLETT P L , HUANG L ,et al. Learning in a large function space:privacy-preserving mechanisms for SVMLearning[J]. Journal of Privacy and Confidentiality, 2012,4(1): 65-100.
[31]	ZHANG J , CORMODE G , PROCOPIUC C M ,et al. Private release of graph statistics using ladder functions[A]. Proceedings of the 2015ACMSIGMOD International Conference on Management of Data[C]. 2015. 731-745.

Name	Age	Zipcode	Disease
Alex	20	15k	Bronchitis
Bob	21	14k	Bronchitis
Jane	33	71k	Pneumonia
Cathy	38	25k	Gastritis
Eva	44	56k	Bronchitis
Frank	47	18k	Dyspepsia

Name	Age	Zipcode	Disease
Alex	20	15k	？
Bob	21	14k	Bronchitis
Jane	33	71k	Pneumonia
Cathy	38	25k	Gastritis
Eva	44	56k	Bronchitis
Frank	47	18k	Dyspepsia