{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T03:26:33Z","timestamp":1760239593212,"version":"build-2065373602"},"reference-count":23,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2020,12,12]],"date-time":"2020-12-12T00:00:00Z","timestamp":1607731200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["JCP"],"abstract":"<jats:p>Quantitative Information Flow (QIF) and Differential Privacy (DP) are both concerned with the protection of sensitive information, but they are rather different approaches. In particular, QIF considers the expected probability of a successful attack, while DP (in both its standard and local versions) is a max-case measure, in the sense that it is compromised by the existence of a possible attack, regardless of its probability. Comparing systems is a fundamental task in these areas: one wishes to guarantee that replacing a system A by a system B is a safe operation that is the privacy of B is no worse than that of A. In QIF, a refinement order provides strong such guarantees, while, in DP, mechanisms are typically compared w.r.t. the privacy parameter \u03b5 in their definition. In this paper, we explore a variety of refinement orders, inspired by the one of QIF, providing precise guarantees for max-case leakage. We study simple structural ways of characterising them, the relation between them, efficient methods for verifying them and their lattice properties. Moreover, we apply these orders in the task of comparing DP mechanisms, raising the question of whether the order based on \u03b5 provides strong privacy guarantees. We show that, while it is often the case for mechanisms of the same \u201cfamily\u201d (geometric, randomised response, etc.), it rarely holds across different families.<\/jats:p>","DOI":"10.3390\/jcp1010004","type":"journal-article","created":{"date-parts":[[2020,12,13]],"date-time":"2020-12-13T20:56:57Z","timestamp":1607893017000},"page":"40-77","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Refinement Orders for Quantitative Information Flow and Differential Privacy"],"prefix":"10.3390","volume":"1","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3081-5775","authenticated-orcid":false,"given":"Konstantinos","family":"Chatzikokolakis","sequence":"first","affiliation":[{"name":"Department of Informatics and Telecommunications, National and Kapodistrian University of Athens Campus, Ilisia, 15784 Athens, Greece"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9212-7839","authenticated-orcid":false,"given":"Natasha","family":"Fernandes","sequence":"additional","affiliation":[{"name":"Department of Computing, Macquarie University, Ryde City 2109, Australia"},{"name":"Inria and Institut Polytechnique de Paris, 91120 Palaiseau, France"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4597-7002","authenticated-orcid":false,"given":"Catuscia","family":"Palamidessi","sequence":"additional","affiliation":[{"name":"Inria and Institut Polytechnique de Paris, 91120 Palaiseau, France"}]}],"member":"1968","published-online":{"date-parts":[[2020,12,12]]},"reference":[{"key":"ref_1","first-page":"265","article-title":"Calibrating noise to sensitivity in private data analysis","volume":"Volume 3876","author":"Halevi","year":"2006","journal-title":"Proceedings of the Third Theory of Cryptography Conference (TCC)"},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Duchi, J.C., Jordan, M.I., and Wainwright, M.J. (2013, January 26\u201329). Local Privacy and Statistical Minimax Rates. Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS), Berkeley, CA, USA.","DOI":"10.1109\/FOCS.2013.53"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1007\/978-3-642-39077-7_5","article-title":"Broadening the scope of Differential Privacy using metrics","volume":"Volume 7981","author":"Wright","year":"2013","journal-title":"Proceedings of the 13th International Symposium on Privacy Enhancing Technologies (PETS 2013)"},{"key":"ref_4","unstructured":"Ning, P., di Vimercati, S.D.C., and Syverson, P.F. (2007, January 28\u201331). An information-theoretic model for adaptive side-channel attacks. Proceedings of the 2007 ACM Conference on Computer and Communications Security (CCS 2007), Alexandria, VA, USA."},{"key":"ref_5","first-page":"288","article-title":"On the Foundations of Quantitative Information Flow","volume":"Volume 5504","year":"2009","journal-title":"Proceedings of the 12th International Conference on Foundations of Software Science and Computation Structures (FOSSACS 2009)"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Alvim, M.S., Chatzikokolakis, K., Palamidessi, C., and Smith, G. (2012, January 25\u201327). Measuring Information Leakage Using Generalized Gain Functions. Proceedings of the 25th IEEE Computer Security Foundations Symposium (CSF), Cambridge, MA, USA.","DOI":"10.1109\/CSF.2012.26"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1007\/978-3-642-54792-8_5","article-title":"Abstract Channels and Their Robust Information-Leakage Ordering","volume":"Volume 8414","author":"Abadi","year":"2014","journal-title":"Proceedings of the Third International Conference on Principles of Security and Trust (POST)"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"3:1","DOI":"10.1145\/2514689","article-title":"Pufferfish: A framework for mathematical privacy definitions","volume":"39","author":"Kifer","year":"2014","journal-title":"ACM Trans. Database Syst."},{"key":"ref_9","unstructured":"Alvim, M.S., Chatzikokolakis, K., McIver, A., Morgan, C., Palamidessi, C., and Smith, G. (July, January 27). Axioms for Information Leakage. Proceedings of the 29th IEEE Computer Security Foundations Symposium (CSF), Lisbon, Portugal."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Yasuoka, H., and Terauchi, T. (2010, January 17\u201319). Quantitative Information Flow\u2014Verification Hardness and Possibilities. Proceedings of the 23rd IEEE Computer Security Foundations Symposium, Edinburgh, UK.","DOI":"10.1109\/CSF.2010.9"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"404","DOI":"10.1017\/S0960129513000649","article-title":"Algebraic foundations for quantitative information flow","volume":"25","author":"Malacaria","year":"2015","journal-title":"Math. Struct. Comput. Sci."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1093\/logcom\/exi009","article-title":"Quantitative Information Flow, Relations and Polymorphic Types","volume":"18","author":"Clark","year":"2005","journal-title":"J. Log. Comput."},{"key":"ref_13","unstructured":"Hofmann, M., and Felleisen, M. (2007, January 17\u201319). Assessing security threats of looping constructs. Proceedings of the 34th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL 2007), Nice, France."},{"key":"ref_14","unstructured":"Landauer, J., and Redmond, T. (1993, January 15\u201317). A Lattice of Information. Proceedings of theComputer Security Foundations Workshop VI, Franconia, NH, USA."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Hsu, J., Gaboardi, M., Haeberlen, A., Khanna, S., Narayan, A., Pierce, B.C., and Roth, A. (2014, January 19\u201322). Differential Privacy: An Economic Method for Choosing Epsilon. Proceedings of the IEEE 27th Computer Security Foundations Symposium, CSF 2014, Vienna, Austria.","DOI":"10.1109\/CSF.2014.35"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Ghosh, A., and Roth, A. (2011, January 5\u20139). Selling Privacy at Auction. Proceedings of the 12th ACM Conference on Electronic Commerce, San Jose, CA, USA.","DOI":"10.1145\/1993574.1993605"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Andr\u00e9s, M.E., Bordenabe, N.E., Chatzikokolakis, K., and Palamidessi, C. (2013, January 4\u20138). Geo-indistinguishability: Differential privacy for location-based systems. Proceedings of the 20th ACM Conference on Computer and Communications Security (CCS 2013), Berlin, Germany.","DOI":"10.1145\/2508859.2516735"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Barthe, G., and K\u00f6pf, B. (2011, January 27\u201329). Information-theoretic Bounds for Differentially Private Mechanisms. Proceedings of the 24th IEEE Computer Security Foundations Symposium (CSF), Cernay-la-Ville, France.","DOI":"10.1109\/CSF.2011.20"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Prasad Kasiviswanathan, S., and Smith, A. (2008). On the \u2018Semantics\u2019 of Differential Privacy: A Bayesian Formulation. J. Priv. Confidentiality, 6.","DOI":"10.29012\/jpc.v6i1.634"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Chatzikokolakis, K., Fernandes, N., and Palamidessi, C. (2019, January 25\u201328). Comparing systems: Max-case refinement orders and application to differential privacy. Proceedings of the 32nd IEEE Computer Security Foundations Symposium, Hoboken, NJ, USA.","DOI":"10.1109\/CSF.2019.00037"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"469","DOI":"10.1007\/s00454-008-9097-3","article-title":"On the Hardness of Computing Intersection, Union and Minkowski Sum of Polytopes","volume":"40","author":"Tiwary","year":"2008","journal-title":"Discret. Comput. Geom."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1016\/S0925-7721(01)00032-3","article-title":"Extended Convex Hull","volume":"20","author":"Fukuda","year":"2000","journal-title":"Comput. Geom."},{"key":"ref_23","unstructured":"Bertsekas, D.P. (2009). Convex Optimization Theory, Athena Scientific."}],"container-title":["Journal of Cybersecurity and Privacy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2624-800X\/1\/1\/4\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T10:44:11Z","timestamp":1760179451000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2624-800X\/1\/1\/4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12,12]]},"references-count":23,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2021,3]]}},"alternative-id":["jcp1010004"],"URL":"https:\/\/doi.org\/10.3390\/jcp1010004","relation":{},"ISSN":["2624-800X"],"issn-type":[{"type":"electronic","value":"2624-800X"}],"subject":[],"published":{"date-parts":[[2020,12,12]]}}}