{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T23:29:40Z","timestamp":1740180580534,"version":"3.37.3"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2024,9,25]],"date-time":"2024-09-25T00:00:00Z","timestamp":1727222400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,9,25]],"date-time":"2024-09-25T00:00:00Z","timestamp":1727222400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Cybersecurity"],"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The differential privacy (DP) literature often centers on meeting privacy constraints by introducing noise to the query, typically using a pre-specified parametric distribution model with one or two degrees of freedom. However, this emphasis tends to neglect the crucial considerations of response accuracy and utility, especially in the context of categorical or discrete numerical database queries, where the parameters defining the noise distribution are finite and could be chosen optimally. This paper addresses this gap by introducing a novel framework for designing an optimal noise probability mass function (PMF) tailored to discrete and finite query sets. Our approach considers the modulo summation of random noise as the DP mechanism, aiming to present a tractable solution that not only satisfies privacy constraints but also minimizes query distortion. Unlike existing approaches focused solely on meeting privacy constraints, our framework seeks to optimize the noise distribution under an arbitrary <jats:inline-formula><jats:alternatives><jats:tex-math>$$(\\epsilon , \\delta )$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>\u03f5<\/mml:mi>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mi>\u03b4<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> constraint, thereby enhancing the accuracy and utility of the response. We demonstrate that the optimal PMF can be obtained through solving a mixed-integer linear program. Additionally, closed-form solutions for the optimal PMF are provided, minimizing the probability of error for two specific cases. Numerical experiments highlight the superior performance of our proposed optimal mechanisms compared to state-of-the-art methods. This paper contributes to the DP literature by presenting a clear and systematic approach to designing noise mechanisms that not only satisfy privacy requirements but also optimize query distortion. The framework introduced here opens avenues for improved privacy-preserving database queries, offering significant enhancements in response accuracy and utility.<\/jats:p>","DOI":"10.1186\/s42400-024-00239-3","type":"journal-article","created":{"date-parts":[[2024,9,25]],"date-time":"2024-09-25T01:39:16Z","timestamp":1727228356000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Optimum noise mechanism for differentially private queries in discrete finite sets"],"prefix":"10.1186","volume":"7","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7085-3365","authenticated-orcid":false,"given":"Sachin","family":"Kadam","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anna","family":"Scaglione","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nikhil","family":"Ravi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sean","family":"Peisert","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Brent","family":"Lunghino","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aram","family":"Shumavon","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,9,25]]},"reference":[{"key":"239_CR1","unstructured":"Adams R (2013) The gumbel-max trick for discrete distributions. https:\/\/lips.cs.princeton.edu\/the-gumbel-max-trick-for-discrete-distributions\/"},{"key":"239_CR2","doi-asserted-by":"crossref","unstructured":"Balcer V, Vadhan S (2019) Differential privacy on finite computers. arXiv:1709.05396","DOI":"10.29012\/jpc.679"},{"key":"239_CR3","first-page":"15676","volume":"33","author":"CL Canonne","year":"2020","unstructured":"Canonne CL, Kamath G, Steinke T (2020) The discrete gaussian for differential privacy. Adv Neural Inf Process Syst 33:15676\u201315688","journal-title":"Adv Neural Inf Process Syst"},{"key":"239_CR4","unstructured":"Census U (2020) Decennial census: processing the count: disclosure avoidance modernization. https:\/\/www.census.gov\/programs-surveys\/decennial-census\/decade\/2020\/planning-management\/process\/disclosure-avoidance.html"},{"issue":"2","key":"239_CR5","first-page":"415","volume":"33","author":"G Cormode","year":"2019","unstructured":"Cormode G, Kulkarni T, Srivastava D (2019) Constrained private mechanisms for count data. IEEE Trans Knowl Data Eng 33(2):415\u2013430","journal-title":"IEEE Trans Knowl Data Eng"},{"key":"239_CR6","first-page":"3574","volume":"30","author":"B Ding","year":"2017","unstructured":"Ding B, Kulkarni J, Yekhanin S (2017) Collecting telemetry data privately. Adv Neural Inf Process Syst 30:3574\u20133583","journal-title":"Adv Neural Inf Process Syst"},{"key":"239_CR7","doi-asserted-by":"crossref","unstructured":"Dwork C, McSherry F, Nissim K, Smith A (2006) Calibrating noise to sensitivity in private data analysis. In: Theory of cryptography conference. Springer, Berlin, pp 265\u2013284","DOI":"10.1007\/11681878_14"},{"key":"239_CR8","unstructured":"Eland A (2015) Tackling urban mobility with technology. https:\/\/europe.googleblog.com\/2015\/11\/tackling-urban-mobility-with-technology.html"},{"issue":"2","key":"239_CR9","doi-asserted-by":"publisher","first-page":"925","DOI":"10.1109\/TIT.2015.2504967","volume":"62","author":"Q Geng","year":"2015","unstructured":"Geng Q, Viswanath P (2015) The optimal noise-adding mechanism in differential privacy. IEEE Trans Inf Theory 62(2):925\u2013951","journal-title":"IEEE Trans Inf Theory"},{"issue":"2","key":"239_CR10","doi-asserted-by":"publisher","first-page":"952","DOI":"10.1109\/TIT.2015.2504972","volume":"62","author":"Q Geng","year":"2015","unstructured":"Geng Q, Viswanath P (2015) Optimal noise adding mechanisms for approximate differential privacy. IEEE Trans Inf Theory 62(2):952\u2013969","journal-title":"IEEE Trans Inf Theory"},{"issue":"7","key":"239_CR11","doi-asserted-by":"publisher","first-page":"1176","DOI":"10.1109\/JSTSP.2015.2425831","volume":"9","author":"Q Geng","year":"2015","unstructured":"Geng Q, Kairouz P, Oh S, Viswanath P (2015) The staircase mechanism in differential privacy. IEEE J Sel Topics Signal Process 9(7):1176\u20131184","journal-title":"IEEE J Sel Topics Signal Process"},{"key":"239_CR12","doi-asserted-by":"publisher","unstructured":"Ghosh A, Roughgarden T, Sundararajan M (2009) Universally utility-maximizing privacy mechanisms. In: Proceedings of the forty-first annual ACM symposium on theory of computing. STOC \u201909. Association for Computing Machinery, New York, NY, USA, pp 351\u2013360. https:\/\/doi.org\/10.1145\/1536414.1536464","DOI":"10.1145\/1536414.1536464"},{"key":"239_CR13","unstructured":"Jiang H et al (2021) On the complexity of mixed integer programming. PhD thesis, Johns Hopkins University"},{"key":"239_CR14","doi-asserted-by":"crossref","unstructured":"Machanavajjhala A, Kifer D, Abowd J, Gehrke J, Vilhuber L (2008) Privacy: theory meets practice on the map. In: 2008 IEEE 24th International Conference on Data Engineering. IEEE, Cancun, Mexico, pp 277\u2013286","DOI":"10.1109\/ICDE.2008.4497436"},{"key":"239_CR15","unstructured":"McClure D (2015) Relaxations of differential privacy and risk\/utility evaluations of synthetic data and fidelity measures. PhD thesis, Duke University"},{"key":"239_CR16","doi-asserted-by":"crossref","unstructured":"McSherry F, Talwar K (2007) Mechanism design via differential privacy. In: 48th annual IEEE symposium on foundations of computer science (FOCS\u201907). IEEE, Providence, RI, USA, pp 94\u2013103","DOI":"10.1109\/FOCS.2007.66"},{"key":"239_CR17","unstructured":"Meiser S (2018) Approximate and probabilistic differential privacy definitions. Cryptology ePrint Archive. https:\/\/eprint.iacr.org\/2018\/277"},{"key":"239_CR18","doi-asserted-by":"crossref","unstructured":"Qin S, He J, Fang C, Lam J (2022) Differential private discrete noise adding mechanism: conditions and properties. In: 2022 American Control Conference (ACC). IEEE, pp 946\u2013951","DOI":"10.23919\/ACC53348.2022.9867334"},{"issue":"6","key":"239_CR19","doi-asserted-by":"publisher","first-page":"4801","DOI":"10.1109\/TSG.2022.3184252","volume":"13","author":"N Ravi","year":"2022","unstructured":"Ravi N, Scaglione A, Kadam S, Gentz R, Peisert S, Lunghino B, Levijarvi E, Shumavon A (2022) Differentially private K-means clustering applied to meter data analysis and synthesis. IEEE Trans Smart Grid 13(6):4801\u20134814. https:\/\/doi.org\/10.1109\/TSG.2022.3184252","journal-title":"IEEE Trans Smart Grid"},{"key":"239_CR20","doi-asserted-by":"crossref","unstructured":"Rogers R, Subramaniam S, Peng S, Durfee D, Lee S, Kancha SK, Sahay S, Ahammad P (2020) LinkedIn\u2019s audience engagements API: a privacy preserving data analytics system at scale. arXiv:2002.05839","DOI":"10.29012\/jpc.782"},{"key":"239_CR21","unstructured":"Sadeghi P, Asoodeh S, Calmon FdP (2020) Differentially private mechanisms for count queries. arXiv:2007.09374"},{"issue":"1","key":"239_CR22","first-page":"155","volume":"4","author":"N Sholmo","year":"2012","unstructured":"Sholmo N, Skinner CJ (2012) Privacy protection from sampling and perturbation in survey microdata. J Privacy Confid 4(1):155\u2013169","journal-title":"J Privacy Confid"},{"key":"239_CR23","unstructured":"Solver GO (2021) Gurobi. https:\/\/www.gurobi.com\/"},{"key":"239_CR24","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1016\/j.ins.2013.07.004","volume":"250","author":"J Soria-Comas","year":"2013","unstructured":"Soria-Comas J, Domingo-Ferrer J (2013) Optimal data-independent noise for differential privacy. Inf Sci 250:200\u2013214","journal-title":"Inf Sci"},{"key":"239_CR25","unstructured":"Triastcyn A, Faltings B (2020) Bayesian differential privacy for machine learning. In: International conference on machine learning. PMLR, Proceedings of Machine Learning Research, pp 9583\u20139592"},{"key":"239_CR26","doi-asserted-by":"crossref","unstructured":"Wang N, Xiao X, Yang Y, Zhao J, Hui SC, Shin H, Shin J, Yu G (2019) Collecting and analyzing multidimensional data with local differential privacy. In: 2019 IEEE 35th international conference on data engineering (ICDE). IEEE, pp 638\u2013649","DOI":"10.1109\/ICDE.2019.00063"},{"key":"239_CR27","doi-asserted-by":"crossref","unstructured":"Ye Q, Hu H, Meng X, Zheng H (2019) PrivKV: key-value data collection with local differential privacy. In: 2019 IEEE symposium on security and privacy (SP). IEEE, pp 317\u2013331","DOI":"10.1109\/SP.2019.00018"},{"issue":"2","key":"239_CR28","doi-asserted-by":"publisher","first-page":"426","DOI":"10.1109\/TSC.2018.2810890","volume":"14","author":"J-D Zhang","year":"2021","unstructured":"Zhang J-D, Chow C-Y (2021) Enabling probabilistic differential privacy protection for location recommendations. IEEE Trans Serv Comput 14(2):426\u2013440. https:\/\/doi.org\/10.1109\/TSC.2018.2810890","journal-title":"IEEE Trans Serv Comput"}],"container-title":["Cybersecurity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s42400-024-00239-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s42400-024-00239-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s42400-024-00239-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,25]],"date-time":"2024-09-25T01:39:30Z","timestamp":1727228370000},"score":1,"resource":{"primary":{"URL":"https:\/\/cybersecurity.springeropen.com\/articles\/10.1186\/s42400-024-00239-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,25]]},"references-count":28,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2024,12]]}},"alternative-id":["239"],"URL":"https:\/\/doi.org\/10.1186\/s42400-024-00239-3","relation":{},"ISSN":["2523-3246"],"issn-type":[{"type":"electronic","value":"2523-3246"}],"subject":[],"published":{"date-parts":[[2024,9,25]]},"assertion":[{"value":"7 June 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 April 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 September 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Not applicable.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval and consent to participate"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}},{"value":"The authors declare that they have no competing interests.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"54"}}