×

Bounded privacy-utility monotonicity indicating bounded tradeoff of differential privacy mechanisms. (English) Zbl 1432.68135

Summary: Differential privacy can achieve the tradeoff between privacy and utility by using privacy metric and utility metric. However, since privacy metric and utility metric may not be bounded, differential privacy can not provide the bounded tradeoff. Moreover, there is no unified method to indicate the bounded tradeoff of differential privacy in the current work. To this end, we proposed the bounded privacy-utility monotonicity indicating the bounded tradeoff of differential privacy. First, we gave the definition of the bounded tradeoff of differential privacy, and we presented the bounded privacy-utility monotonicity of differential privacy based on computational indistinguishability. Second, we theoretically proved the bounded privacy-utility monotonicity of several differential privacy mechanisms based on the bounded metrics of modulus of characteristic function and normalized entropy, including the Laplace mechanism, discrete Laplace mechanism, Gaussian mechanism, exponential mechanism, optimal mechanism, and quaternary mechanism. We also showed that these mechanisms had the bounded privacy-utility monotonicity in the multivariate case. Third, our numerical results further demonstrated that these several differential privacy mechanisms obtained the bounded privacy-utility monotonicity. Finally, we gave an instance of achieving the bounded tradeoff of differential privacy mechanisms based on the bounded privacy-utility monotonicity under semi-honest model, and we discussed the goal of optimization of the bounded tradeoff of differential privacy based on the bounded privacy-utility monotonicity under semi-honest model. Therefore, the bounded privacy-utility monotonicity can be used to indicate the bounded tradeoff of differential privacy under semi-honest model. Furthermore, the bounded privacy-utility monotonicity plays an important role of optimizing the bounded tradeoff of differential privacy under semi-honest model.

MSC:

68P27 Privacy of data

Software:

Pufferfish
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Dwork, Cynthia; McSherry, Frank; Nissim, Kobbi; Smith, Adam, Calibrating noise to sensitivity in private data analysis, (Proc. of the 3rd Theory of Cryptography Conference. Proc. of the 3rd Theory of Cryptography Conference, March 4-7 (2006)), 265-284 · Zbl 1112.94027
[2] Bun, Mark; Dwork, Cynthia; Rothblum, Guy N.; Steinke, Thomas, Composable and versatile privacy via truncated CDP, (Proc. of the 50th Annual ACM SIGACT Symposium on Theory of Computing. Proc. of the 50th Annual ACM SIGACT Symposium on Theory of Computing, June 25-29 (2018)), 74-86 · Zbl 1427.68073
[3] Dwork, Cynthia; Rothblum, Guy N., Concentrated differential privacy (March 2016)
[4] Kalantari, Kousha; Sankar, Lalitha; Sarwate, Anand D., Robust privacy-utility tradeoffs under differential privacy and Hamming distortion, IEEE Trans. Inf. Forensics Secur., 13, 11, 2816-2830 (November 2018)
[5] Li, Yaliang; Miao, Chenglin; Su, Lu; Gao, Jing; Li, Qi; Ding, Bolin; Qin, Zhan; Ren, Kui, An efficient two-layer mechanism for privacy-preserving truth discovery, (Proc. of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. Proc. of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, August 19-23 (2018)), 1705-1714
[6] Li, Chencheng; Zhou, Pan; Xiong, Li; Wang, Qian; Wang, Ting, Differentially private distributed online learning, IEEE Trans. Knowl. Data Eng., 30, 8, 1440-1453 (August 2018)
[7] Balog, Matej; Tolstikhin, Ilya; Schölkopf, Bernhard, Differentially private database release via kernel mean embeddings, (Proc. of the 35th International Conference on Machine Learning. Proc. of the 35th International Conference on Machine Learning, July 10-15 (2018))
[8] Wang, Leye; Qin, Gehua; Yang, Dingqi; Han, Xiao; Ma, Xiaojuan, Geographic differential privacy for mobile crowd coverage maximization, (Proc. of the 32nd AAAI Conference on Artificial Intelligence. Proc. of the 32nd AAAI Conference on Artificial Intelligence, February 2-7 (2018)), 200-207
[9] Katz, Jonathan; Lindell, Yehuda, Introduction to Modern Cryptography (2014), CRC Press: CRC Press Boca Raon, Florida, USA · Zbl 1143.94001
[10] Mironov, Ilya; Pandey, Omkant; Reingold, Omer; Vadhan, Salil, Computational differential privacy, (Proc. of the 29th Annual International Cryptology Conference. Proc. of the 29th Annual International Cryptology Conference, August 16-20 (2009)), 126-142 · Zbl 1252.94089
[11] Prasad Kasiviswanathan, Shiva; Lee, Homin K.; Nissim, Kobbi; Raskhodnikova, Sofya; Smith, Adam, What can we learn privately?, SIAM J. Comput., 40, 3, 793-826 (May 2011) · Zbl 1235.68093
[12] Bhaskar, Raghav; Bhowmick, Abhishek; Goyal, Vipul; Laxman, Srivatsan; Thakurta, Abhradeep, Noiseless database privacy, (Proc. of the 17th International Conference on the Theory and Application of Cryptology and Information Security. Proc. of the 17th International Conference on the Theory and Application of Cryptology and Information Security, December 4-8 (2011)), 215-232 · Zbl 1227.94030
[13] Li, Ninghui; Qardaji, Wahbeh; Su, Dong; Wu, Yi; Yang, Weining, Membership privacy: a unifying framework for privacy definitions, (Proc. of the 2013 ACM SIGSAC Conference on Computer and Communications Security. Proc. of the 2013 ACM SIGSAC Conference on Computer and Communications Security, November 4-8 (2013)), 889-900
[14] Kifer, Daniel; Machanavajjhala, Ashwin, Pufferfish: a framework for mathematical privacy definitions, ACM Trans. Database Syst., 39, 1, Article 3 pp. (January 2014) · Zbl 1321.94067
[15] Song, Shuang; Wang, Yizhen; Chaudhuri, Kamalika, Pufferfish privacy mechanisms for correlated data, (Proc. of the 2017 ACM SIGMOD International Conference on Management of Data. Proc. of the 2017 ACM SIGMOD International Conference on Management of Data, May 14-19 (2017)), 1291-1306
[16] Yang, Bin; Sato, Issei; Nakagawa, Hiroshi, Bayesian differential privacy on correlated data, (Proc. of the 2015 ACM SIGMOD International Conference on Management of Data. Proc. of the 2015 ACM SIGMOD International Conference on Management of Data, May 31-June 4 (2015)), 747-762
[17] Jorgensen, Zach; Yu, Ting; Cormode, Graham, Conservative or liberal? Personalized differential privacy, (Proc. of the 31st IEEE International Conference on Data Engineering. Proc. of the 31st IEEE International Conference on Data Engineering, April 13-17 (2015)), 1023-1034
[18] Soria-Comas, Jordi; Domingo-Ferrer, Josep; Sánchez, David; Megías, David, Individual differential privacy: a utility-preserving formulation of differential privacy guarantees, IEEE Trans. Inf. Forensics Secur., 12, 6, 1418-1429 (June 2017)
[19] Mironov, Ilya, Rényi differential privacy, (Proc. of the 30th IEEE Computer Security Foundations Symposium. Proc. of the 30th IEEE Computer Security Foundations Symposium, August 21-25 (2017)), 263-275
[20] Chaudhuri, Kamalika; Monteleoni, Claire; Sarwate, Anand D., Differentially private empirical risk minimization, J. Mach. Learn. Res., 12, 1069-1109 (March 2011) · Zbl 1280.62073
[21] Chaudhuri, Kamalika; Hsu, Daniel, Convergence rates for differentially private statistical estimation, (Proc. of the 29th International Conference on Machine Learning. Proc. of the 29th International Conference on Machine Learning, June 26-July 1 (2012))
[22] Shokri, Reza; Shmatikov, Vitaly, Privacy-preserving deep learning, (Proc. of the 2015 ACM SIGSAC Conference on Computer and Communications Security. Proc. of the 2015 ACM SIGSAC Conference on Computer and Communications Security, October 12-16 (2015)), 1310-1321
[23] Bernstein, Garrett; McKenna, Ryan; Sun, Tao; Sheldon, Daniel; Hay, Michael; Miklau, Gerome, Differentially private learning of undirected graphical models using collective graphical models, (Proc. of the 34th International Conference on Machine Learning. Proc. of the 34th International Conference on Machine Learning, August 6-11 (2017))
[24] Zhang, Tao; Zhu, Quanyan, Dynamic differential privacy for ADMM-based distributed classification learning, IEEE Trans. Inf. Forensics Secur., 12, 1, 172-187 (January 2017)
[25] Wang, Di; Ye, Minwei; Xu, Jinhui, Differentially private empirical risk minimization revisited: faster and more general, (Proc. of the 31st Annual Conference on Neural Information Processing Systems. Proc. of the 31st Annual Conference on Neural Information Processing Systems, December 4-9 (2017)), 2722-2731
[26] Wang, Di; Xu, Jinhui, Differentially private empirical risk minimization with smooth non-convex loss functions: a non-stationary view, (Proc. of the 33rd AAAI Conference on Artificial Intelligence. Proc. of the 33rd AAAI Conference on Artificial Intelligence, January 27-February 1 (2019)), 1182-1189
[27] Wang, Di; Gaboardi, Marco; Xu, Jinhui, Empirical risk minimization in non-interactive local differential privacy revisited, (Proc. of the 32nd Annual Conference on Neural Information Processing Systems. Proc. of the 32nd Annual Conference on Neural Information Processing Systems, December 3-8 (2018)), 973-982
[28] Wang, Di; Xu, Jinhui, On sparse linear regression in the local differential privacy model, (Proc. of the 36th International Conference on Machine Learning. Proc. of the 36th International Conference on Machine Learning, June 9-15 (2019)), 6628-6637
[29] Chaudhuri, Kamalika; Sarwate, Anand D.; Sinha, Kaushik, A near-optimal algorithm for differentially-private principal components, J. Mach. Learn. Res., 14, 1, 2905-2943 (January 2013) · Zbl 1318.62202
[30] Duchi, John C.; Jordan, Michael I.; Wainwright, Martin J., Local privacy and minimax bounds: sharp rates for probability estimation, (Proc. of the 27th Annual Conference on Neural Information Processing Systems. Proc. of the 27th Annual Conference on Neural Information Processing Systems, December 5-8 (2013)), 1-9
[31] He, Xi; Machanavajjhala, Ashwin; Ding, Bolin, Blowfish privacy: tuning privacy-utility trade-offs using policies, (Proc. of the ACM SIGMOD International Conference on Management of Data. Proc. of the ACM SIGMOD International Conference on Management of Data, June 22-27 (2014)), 1447-1458
[32] Kairouz, Peter; Oh, Sewoong; Viswanath, Pramod, Extremal mechanisms for local differential privacy, J. Mach. Learn. Res., 4, 1, 492-542 (December 2016)
[33] Feild, Henry; Allan, James; Glatt, Joshua, CrowdLogging: distributed, private, and anonymous search logging, (Proc. of the 34th International ACM SIGIR Conference on Research and Development in Information Retrieval. Proc. of the 34th International ACM SIGIR Conference on Research and Development in Information Retrieval, July 25-29 (2011)), 375-384
[34] Hong, Yuan; Vaidya, Jaideep; Lu, Haibing; Karras, Panagiotis; Goel, Sanjay, Collaborative search log sanitization: toward differential privacy and boosted utility, IEEE Trans. Dependable Secure Comput., 12, 5, 504-518 (September/October 2015)
[35] Zhang, Sicong; Yang, Hui; Singh, Lisa, Anonymizing query logs by differential privacy, (Proc. of the 39th International ACM SIGIR Conference on Research and Development in Information Retrieval. Proc. of the 39th International ACM SIGIR Conference on Research and Development in Information Retrieval, July 17-21 (2016)), 753-756
[36] Ghosh, Arpita; Roughgarden, Tim; Sundararajan, Mukund, Universally utility-maximizing privacy mechanisms, SIAM J. Comput., 41, 6, 1673-1693 (December 2012) · Zbl 1271.68102
[37] Wang, Meng; Ji, Zhanglong; Kim, Hyeon-Eui; Wang, Shuang; Xiong, Li; Jiang, Xiaoqian, Selecting optimal subset to release under differentially private M-estimators from hybrid datasets, IEEE Trans. Knowl. Data Eng., 30, 3, 573-584 (March 2018)
[38] Huai, Mengdi; Wang, Di; Miao, Chenglin; Xu, Jinhui; Zhang, Aidong, Privacy-aware synthesizing for crowdsourced data, (Proc. of the 28th International Joint Conference on Artificial Intelligence. Proc. of the 28th International Joint Conference on Artificial Intelligence, August 10-16 (2019)), 2542-2548
[39] Geng, Quan; Viswanath, Pramod, Optimal noise adding mechanisms for approximate differential privacy, IEEE Trans. Inf. Theory, 62, 2, 952-969 (February 2016) · Zbl 1359.94644
[40] Nikolov, Aleksandar; Talwar, Kunal; Zhang, Li, The geometry of differential privacy: the small database and approximate cases, SIAM J. Comput., 45, 2, 575-616 (April 2016) · Zbl 1339.68066
[41] Dewri, Rinku, Local differential perturbations: location privacy under approximate knowledge attackers, IEEE Trans. Mob. Comput., 12, 12, 2360-2372 (December 2013)
[42] McSherry, Frank; Mironov, Ilya, Differentially private recommender systems: building privacy into the netflix prize contenders, (Proc. of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Proc. of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, June 29-July 2 (2009)), 627-636
[43] Dwork, Cynthia; Roth, Aaron, The Algorithmic Foundations of Differential Privacy, Foundations and Trends® in Theoretical Computer Science, vol. 9, no. 3-4, 211-407 (August 2014) · Zbl 1302.68109
[44] Forbes, Catherine; Evans, Merran; Hastings, Nicholas; Peacock, Brian, Statistical Distributions (2011), John Wiley & Sons: John Wiley & Sons Hoboken, New Jersey · Zbl 1258.62012
[45] Inusaha, Seidu; Kozubowski, Tomasz J., A discrete analogue of the Laplace distribution, J. Stat. Plan. Inference, 136, 3, 1090-1102 (March 2006) · Zbl 1081.60011
[46] Warner, Stanley L., Randomized response: a survey technique for eliminating evasive answer bias, J. Am. Stat. Assoc., 60, 309, 63-69 (April 1965) · Zbl 1298.62024
[47] Holohan, Naoise; Leith, Douglas J.; Mason, Oliver, Optimal differentially private mechanisms for randomised response, IEEE Trans. Inf. Forensics Secur., 12, 11, 2726-2735 (November 2017)
[48] Kotz, Samuel; Kozubowski, Tomasz J.; Podgórski, Krzysztof, The Laplace Distribution and Generalizations: A Revisit With Applications to Communications, Economics, Engineering, and Finance (2001), Springer Science & Business Media: Springer Science & Business Media New York · Zbl 0977.62003
[49] Liang Tong, Yung, The Multivariate Normal Distribution (1990), Springer Science & Business Media: Springer Science & Business Media New York · Zbl 0689.62036
[50] Kim Hung, Pham, Secrets in Inequalities, vol. 1 (2008), GIL Publishing House: GIL Publishing House Zalǎu, Romania
[51] Liu, Hai; Wu, Zhenqiang; Zhou, Yihui; Peng, Changgen; Tian, Feng; Lu, Laifeng, Privacy-preserving monotonicity of differential privacy mechanisms, Appl. Sci., 8, 11, Article 2081 pp. (October 2018)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.