{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,3]],"date-time":"2026-05-03T10:59:28Z","timestamp":1777805968910,"version":"3.51.4"},"reference-count":28,"publisher":"SAGE Publications","issue":"4","license":[{"start":{"date-parts":[[2015,9,1]],"date-time":"2015-09-01T00:00:00Z","timestamp":1441065600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["Journal of Computer Security"],"published-print":{"date-parts":[[2015,9,16]]},"abstract":"<jats:p>Abstract<\/jats:p>\n                  <jats:p>Differential privacy aims at protecting the privacy of participants in statistical databases. Roughly, a mechanism satisfies differential privacy if the presence or value of a single individual in the database does not significantly change the likelihood of obtaining a certain answer to any statistical query posed by a data analyst. Differentially-private mechanisms are often oblivious: first the query is processed on the database to produce a true answer, and then this answer is adequately randomized before being reported to the data analyst. Ideally, a mechanism should minimize leakage\u00a0\u2013 i.e., obfuscate as much as possible the link between reported answers and individuals\u2019 data\u00a0\u2013 while maximizing utility\u00a0\u2013 i.e., report answers as similar as possible to the true ones. These two goals, however, are in conflict with each other, thus imposing a trade-off between privacy and utility.<\/jats:p>\n                  <jats:p>In this paper we use quantitative information flow principles to analyze leakage and utility in oblivious differentially-private mechanisms. We introduce a technique that exploits graph symmetries of the adjacency relation on databases to derive bounds on the min-entropy leakage of the mechanism. We consider a notion of utility based on identity gain functions, which is closely related to min-entropy leakage, and we derive bounds for it. Finally, given some graph symmetries, we provide a mechanism that maximizes utility while preserving the required level of differential privacy.<\/jats:p>","DOI":"10.3233\/jcs-150528","type":"journal-article","created":{"date-parts":[[2015,9,22]],"date-time":"2015-09-22T12:08:14Z","timestamp":1442923694000},"page":"427-469","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":23,"title":["On the information leakage of differentially-private mechanisms"],"prefix":"10.1177","volume":"23","author":[{"given":"M\u00e1rio S.","family":"Alvim","sequence":"first","affiliation":[{"name":"Computer Science Department, Universidade Federal de Minas Gerais, Belo Horizonte, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Miguel E.","family":"Andr\u00e9s","sequence":"additional","affiliation":[{"name":"LIX, \u00c9cole Polytechnique, Palaiseau, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Konstantinos","family":"Chatzikokolakis","sequence":"additional","affiliation":[{"name":"CNRS, \u00c9cole Polytechnique, Palaiseau, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pierpaolo","family":"Degano","sequence":"additional","affiliation":[{"name":"Dipartimento di Informatica, Universit\u00e0 di Pisa, Pisa, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Catuscia","family":"Palamidessi","sequence":"additional","affiliation":[{"name":"LIX, \u00c9cole Polytechnique, Palaiseau, France"},{"name":"INRIA, \u00c9cole Polytechnique, Palaiseau, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2015,9,1]]},"reference":[{"key":"ref001","doi-asserted-by":"crossref","unstructured":"[1]M.S.\u00a0Alvim, M.E.\u00a0Andr\u00e9s, K.\u00a0Chatzikokolakis, P.\u00a0Degano and C.\u00a0Palamidessi, Differential privacy: On the trade-off between utility and information leakage, in: Post-Proceedings of the 8th International Workshop on Formal Aspects in Security and Trust (FAST), G.\u00a0Barthe, A.\u00a0Datta and S.\u00a0Etalle, eds, Lecture Notes in Computer Science, Vol.\u00a07140, Springer, Leuven, Belgium, 2011, pp.\u00a039\u201354.","DOI":"10.1007\/978-3-642-29420-4_3"},{"key":"ref002","doi-asserted-by":"crossref","unstructured":"[2]M.S.\u00a0Alvim, M.E.\u00a0Andr\u00e9s, K.\u00a0Chatzikokolakis and C.\u00a0Palamidessi, On the relation between differential privacy and quantitative information flow, in: 38th International Colloquium on Automata, Languages and Programming (ICALP), J.\u00a0Sgall Luca Aceto and M.\u00a0Henzinger, eds, Lecture Notes in Computer Science, Vol.\u00a06756, Springer, Z\u00fcrich, Switzerland, 2011, pp.\u00a060\u201376.","DOI":"10.1007\/978-3-642-22012-8_4"},{"key":"ref003","unstructured":"[3]M.S.\u00a0Alvim, K.\u00a0Chatzikokolakis, P.\u00a0Degano and C.\u00a0Palamidessi, Differential privacy versus quantitative information flow, Technical report, INRIA and LIX, Ecole Polytechnique, 2010, available at: http:\/\/hal.archives-ouvertes.fr\/hal-00548214\/en\/."},{"key":"ref004","doi-asserted-by":"crossref","unstructured":"[4]M.S.\u00a0Alvim, K.\u00a0Chatzikokolakis, C.\u00a0Palamidessi and G.\u00a0Smith, Measuring information leakage using generalized gain functions, in: Proceedings of the 25th IEEE Computer Security Foundations Symposium (CSF), 2012, pp.\u00a0265\u2013279.","DOI":"10.1109\/CSF.2012.26"},{"key":"ref005","doi-asserted-by":"crossref","unstructured":"[5]G.\u00a0Barthe and B.\u00a0K\u00f6pf, Information-theoretic bounds for differentially private mechanisms, in: Proceedings of the 24th IEEE Computer Security Foundations Symposium (CSF), IEEE Computer Society, 2011, pp.\u00a0191\u2013204.","DOI":"10.1109\/CSF.2011.20"},{"key":"ref006","doi-asserted-by":"crossref","unstructured":"[6]J.M.\u00a0Bernardo and A.F.M.\u00a0Smith, Bayesian Theory, John Wiley & Sons, Inc., 1994.","DOI":"10.1002\/9780470316870"},{"key":"ref007","doi-asserted-by":"crossref","unstructured":"[7]A.\u00a0Blum, K.\u00a0Ligett and A.\u00a0Roth, A learning theory approach to non-interactive database privacy, in: Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, STOC\u201908, ACM, New York, NY, USA, 2008, pp.\u00a0609\u2013618.","DOI":"10.1145\/1374376.1374464"},{"key":"ref008","doi-asserted-by":"crossref","unstructured":"[8]C.\u00a0Braun, K.\u00a0Chatzikokolakis and C.\u00a0Palamidessi, Compositional methods for information-hiding, in: Proceedings of the 11th International Conference on the Foundations of Software Science and Computation Structures (FOSSACS\u201908), R.\u00a0Amadio, ed. Lecture Notes in Computer Science, Vol.\u00a04962, Springer, 2008, pp.\u00a0443\u2013457.","DOI":"10.1007\/978-3-540-78499-9_31"},{"key":"ref009","doi-asserted-by":"crossref","unstructured":"[9]C.\u00a0Braun, K.\u00a0Chatzikokolakis and C.\u00a0Palamidessi, Quantitative notions of leakage for one-try attacks, in: Proceedings of the 25th Conference on Mathematical Foundations of Programming Semantics, Electronic Notes in Theoretical Computer Science, Vol.\u00a0249, Elsevier B.V., 2009, pp.\u00a075\u201391.","DOI":"10.1016\/j.entcs.2009.07.085"},{"key":"ref010","doi-asserted-by":"crossref","unstructured":"[10]A.E.\u00a0Brouwer, A.M.\u00a0Cohen and A.\u00a0Neumaier, Distance Regular Graphs, Ergebnisse der Mathematik, Vol.\u00a03, Springer, 1989.","DOI":"10.1007\/978-3-642-74341-2"},{"key":"ref011","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129513000595"},{"key":"ref012","unstructured":"[12]C.\u00a0Dwork, Differential privacy, in: 33rd International Colloquium on Automata, Languages and Programming (ICALP), M.\u00a0Bugliesi, B.\u00a0Preneel, V.\u00a0Sassone and I.\u00a0Wegener, eds, Lecture Notes in Computer Science, Vol.\u00a04052, Springer, 2006, pp.\u00a01\u201312."},{"key":"ref013","doi-asserted-by":"crossref","unstructured":"[13]C.\u00a0Dwork, Differential privacy in new settings, in: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), M.\u00a0Charikar, ed. SIAM, 2010, pp.\u00a0174\u2013183.","DOI":"10.1137\/1.9781611973075.16"},{"key":"ref014","doi-asserted-by":"publisher","DOI":"10.1145\/1866739.1866758"},{"key":"ref015","doi-asserted-by":"crossref","unstructured":"[15]C.\u00a0Dwork and J.\u00a0Lei, Differential privacy and robust statistics, in: Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC), Bethesda, MD, USA, 31 May\u20132 June 2009, M.\u00a0Mitzenmacher, ed. ACM, 2009, pp.\u00a0371\u2013380.","DOI":"10.1145\/1536414.1536466"},{"key":"ref016","doi-asserted-by":"crossref","unstructured":"[16]B.\u00a0Espinoza and G.\u00a0Smith, Min-entropy leakage of channels in cascade, in: Proceedings of the International Workshop on Formal Aspects in Security and Trust (FAST), G.\u00a0Barthe, A.\u00a0Datta and S.\u00a0Etalle, eds, Lecture Notes in Computer Science, Vol.\u00a07140, Springer, 2011, pp.\u00a070\u201384.","DOI":"10.1007\/978-3-642-29420-4_5"},{"key":"ref017","doi-asserted-by":"crossref","unstructured":"[17]A.\u00a0Ghosh, T.\u00a0Roughgarden and M.\u00a0Sundararajan, Universally utility-maximizing privacy mechanisms, in: Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC), ACM, New York, NY, USA, 2009, pp.\u00a0351\u2013360.","DOI":"10.1145\/1536414.1536464"},{"key":"ref018","doi-asserted-by":"crossref","unstructured":"[18]M.\u00a0Hardt and G.N.\u00a0Rothblum, A multiplicative weights mechanism for privacy-preserving data analysis, in: Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS\u201910, IEEE Computer Society, Washington, DC, USA, 2010, pp.\u00a061\u201370.","DOI":"10.1109\/FOCS.2010.85"},{"key":"ref019","doi-asserted-by":"crossref","unstructured":"[19]J.\u00a0Heusser and P.\u00a0Malacaria, Applied quantitative information flow and statistical databases, in: Proceedings of the International Workshop on Formal Aspects in Security and Trust (FAST 2009), P.\u00a0Degano and J.D.\u00a0Guttman, eds, Lecture Notes in Computer Science, Vol.\u00a05983, Springer, 2009, pp.\u00a096\u2013110.","DOI":"10.1007\/978-3-642-12459-4_8"},{"key":"ref020","unstructured":"[20]W.\u00a0Imrich and S.\u00a0Klav\u017ear, Product Graphs, Structure and Recognition, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley, 2000."},{"key":"ref021","doi-asserted-by":"crossref","unstructured":"[21]Y.\u00a0Kawamoto, K.\u00a0Chatzikokolakis and C.\u00a0Palamidessi, Compositionality results for quantitative information flow, in: Proceedings of the 11th International Conference on Quantitative Evaluation of Systems (QEST 2014), G.\u00a0Norman and W.H.\u00a0Sanders, eds, Lecture Notes in Computer Science, Vol.\u00a08657, Springer, 2014, pp.\u00a0368\u2013383, IDEX Digital Society project.","DOI":"10.1007\/978-3-319-10696-0_28"},{"key":"ref022","doi-asserted-by":"crossref","unstructured":"[22]D.\u00a0Kifer and A.\u00a0Machanavajjhala, No free lunch in data privacy, in: Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data, SIGMOD\u201911, ACM, New York, NY, USA, 2011, pp.\u00a0193\u2013204.","DOI":"10.1145\/1989323.1989345"},{"key":"ref023","doi-asserted-by":"crossref","unstructured":"[23]B.\u00a0K\u00f6pf and D.A.\u00a0Basin, An information-theoretic model for adaptive side-channel attacks, in: Proceedings of the 2007 ACM Conference on Computer and Communications Security (CCS 2007), P.\u00a0Ning, S.\u00a0De\u00a0Capitani di\u00a0Vimercati and P.F.\u00a0Syverson, eds, ACM, 2007, pp.\u00a0286\u2013296.","DOI":"10.1145\/1315245.1315282"},{"key":"ref024","doi-asserted-by":"crossref","unstructured":"[24]F.\u00a0McSherry and K.\u00a0Talwar, Mechanism design via differential privacy, in: Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), IEEE Computer Society, 2007, pp.\u00a094\u2013103.","DOI":"10.1109\/FOCS.2007.66"},{"key":"ref025","unstructured":"[25]S.\u00a0Prasad Kasiviswanathan and A.\u00a0Smith, A note on differential privacy: Defining resistance to arbitrary side information, Report 2008\/144, Cryptology ePrint Archive, 2008, available at: http:\/\/eprint.iacr.org\/."},{"key":"ref026","doi-asserted-by":"crossref","unstructured":"[26]A.\u00a0Roth and T.\u00a0Roughgarden, Interactive privacy via the median mechanism, in: Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC), 2010, pp.\u00a0765\u2013774.","DOI":"10.1145\/1806689.1806794"},{"key":"ref027","doi-asserted-by":"crossref","unstructured":"[27]G.\u00a0Smith, On the foundations of quantitative information flow, in: Proceedings of the 12th International Conference on Foundations of Software Science and Computation Structures (FOSSACS 2009), L.\u00a0de Alfaro, ed. Lecture Notes in Computer Science, Vol.\u00a05504, Springer, York, UK, 2009, pp.\u00a0288\u2013302.","DOI":"10.1007\/978-3-642-00596-1_21"},{"key":"ref028","doi-asserted-by":"crossref","unstructured":"[28]G.\u00a0Smith, Quantifying information flow using min-entropy, in: Eighth International Conference on Quantitative Evaluation of Systems, QEST 2011, Aachen, Germany, 5\u20138 September 2011, IEEE Computer Society, 2011, pp.\u00a0159\u2013167.","DOI":"10.1109\/QEST.2011.31"}],"container-title":["Journal of Computer Security"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/JCS-150528","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.3233\/JCS-150528","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/JCS-150528","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T20:44:53Z","timestamp":1777495493000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.3233\/JCS-150528"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,9,1]]},"references-count":28,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,9,16]]}},"alternative-id":["10.3233\/JCS-150528"],"URL":"https:\/\/doi.org\/10.3233\/jcs-150528","relation":{},"ISSN":["0926-227X","1875-8924"],"issn-type":[{"value":"0926-227X","type":"print"},{"value":"1875-8924","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,9,1]]}}}