{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T02:40:29Z","timestamp":1760236829374,"version":"build-2065373602"},"reference-count":53,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2021,12,25]],"date-time":"2021-12-25T00:00:00Z","timestamp":1640390400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>This work introduces channel-supermodular entropies, a subset of quasi-concave entropies. Channel-supermodularity is a property shared by some of the most commonly used entropies in the literature, including Arimoto\u2013R\u00e9nyi conditional entropies (which include Shannon and min-entropy as special cases), k-tries entropies, and guessing entropy. Based on channel-supermodularity, new preorders for channels that strictly include degradedness and inclusion (or Shannon ordering) are defined, and these preorders are shown to provide a sufficient condition for the more-capable and capacity ordering, not only for Shannon entropy but also regarding analogous concepts for other entropy measures. The theory developed is then applied in the context of query anonymization. We introduce a greedy algorithm based on channel-supermodularity for query anonymization and prove its optimality, in terms of information leakage, for all symmetric channel-supermodular entropies.<\/jats:p>","DOI":"10.3390\/e24010039","type":"journal-article","created":{"date-parts":[[2021,12,27]],"date-time":"2021-12-27T01:00:54Z","timestamp":1640566854000},"page":"39","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Channel-Supermodular Entropies: Order Theory and an Application to Query Anonymization"],"prefix":"10.3390","volume":"24","author":[{"given":"Arthur","family":"Am\u00e9rico","sequence":"first","affiliation":[{"name":"School of Electronic Engineering and Computer Science, Queen Mary University of London, London E1 4NS, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"MHR","family":"Khouzani","sequence":"additional","affiliation":[{"name":"School of Electronic Engineering and Computer Science, Queen Mary University of London, London E1 4NS, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pasquale","family":"Malacaria","sequence":"additional","affiliation":[{"name":"School of Electronic Engineering and Computer Science, Queen Mary University of London, London E1 4NS, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2021,12,25]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"390","DOI":"10.1016\/S0019-9958(58)90239-0","article-title":"A note on a partial ordering for communication channels","volume":"1","author":"Shannon","year":"1958","journal-title":"Inf. Control"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1109\/TIT.1979.1056029","article-title":"The capacity of a class of broadcast channels","volume":"25","year":"1979","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_3","first-page":"411","article-title":"Comparison of two noisy channels","volume":"16","author":"Korner","year":"1977","journal-title":"Coll. Math. Soc. J. Bolyai"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1093\/logcom\/exi009","article-title":"Quantitative Information Flow, Relations and Polymorphic Types","volume":"15","author":"Clark","year":"2005","journal-title":"J. Log. Comput."},{"key":"ref_5","first-page":"288","article-title":"On the Foundations of Quantitative Information Flow","volume":"Volume 5504","author":"Smith","year":"2009","journal-title":"Proceedings of the 12th International Conference on Foundations of Software Science and Computational Structures (FOSSACS)"},{"key":"ref_6","unstructured":"Cohen, J., Kempermann, J.H.B., and Zbaganu, G. (1998). Comparisons of Stochastic Matrices with Applications in Information Theory, Statistics, Economics and Population, Springer Science & Business Media."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Am\u00e9rico, A., Malacaria, P., and Khouzani, A.M. (2019, January 25\u201328). Channel Ordering and Supermodularity. Proceedings of the 2019 IEEE Information Theory Workshop (ITW) (IEEE ITW 2019), Visby, Sweden.","DOI":"10.1109\/ITW44776.2019.8989409"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1109\/TIT.1972.1054727","article-title":"Broadcast channels","volume":"18","author":"Cover","year":"1972","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Pasareanu, C.S., Phan, Q., and Malacaria, P. (July, January 27). Multi-run Side-Channel Analysis Using Symbolic Execution and Max-SMT. Proceedings of the IEEE 29th Computer Security Foundations Symposium, CSF 2016, Lisbon, Portugal.","DOI":"10.1109\/CSF.2016.34"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Heusser, J., and Malacaria, P. (2010, January 6\u201310). Quantifying information leaks in software. Proceedings of the Twenty-Sixth Annual Computer Security Applications Conference, ACSAC 2010, Austin, TX, USA.","DOI":"10.1145\/1920261.1920300"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"1841","DOI":"10.1109\/TNET.2015.2438860","article-title":"Quantifying the information leakage in timing side channels in deterministic work-conserving schedulers","volume":"24","author":"Gong","year":"2016","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"K\u00f6pf, B., and Smith, G. (2010, January 17\u201319). Vulnerability Bounds and Leakage Resilience of Blinded Cryptography under Timing Attacks. Proceedings of the 2010 23rd IEEE Computer Security Foundations Symposium, Edinburgh, UK.","DOI":"10.1109\/CSF.2010.11"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Am\u00e9rico, A., Khouzani, M., and Malacaria, P. (2019, January 25\u201328). Deterministic Channel Design for Minimum Leakage. Proceedings of the IEEE 32nd Computer Security Foundations Symposium (CSF), Hoboken, NJ, USA.","DOI":"10.1109\/CSF.2019.00036"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1109\/TIT.1973.1054980","article-title":"Random coding theorem for broadcast channels with degraded components","volume":"19","author":"Bergmans","year":"1973","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1109\/TIT.1974.1055184","article-title":"A simple converse for broadcast channels with additive white Gaussian noise (Corresp.)","volume":"20","author":"Bergmans","year":"1974","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_16","first-page":"3","article-title":"Capacity and coding for degraded broadcast channels","volume":"10","author":"Gallager","year":"1974","journal-title":"Probl. Peredachi Informatsii"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Smith, G. (2015, January 6\u201310). Recent Developments in Quantitative Information Flow (Invited Tutorial). Proceedings of the LICS \u201915 2015 30th Annual ACM\/IEEE Symposium on Logic in Computer Science (LICS), Kyoto, Japan.","DOI":"10.1109\/LICS.2015.13"},{"key":"ref_18","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_19","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 IEEE 25th Computer Security Foundations Symposium (CSF), Cambridge, MA, USA.","DOI":"10.1109\/CSF.2012.26"},{"key":"ref_20","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":"McIver","year":"2014","journal-title":"Proceedings of the International Conference on Principles of Security and Trust (POST)"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Neyman, J. (1951). The comparison of experiments. Second Berkeley Symposium on Mathematical Statistics and Probability, Univ. of California Press.","DOI":"10.1525\/9780520411586"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Bordenabe, N.E., and Smith, G. (July, January 27). Correlated Secrets in Quantitative Information Flow. Proceedings of the 2016 IEEE 29th Computer Security Foundations Symposium (CSF), Lisbon, Portugal.","DOI":"10.1109\/CSF.2016.14"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1134\/S0032946016030017","article-title":"Degradable channels, less noisy channels, and quantum statistical morphisms: An equivalence relation","volume":"52","author":"Buscemi","year":"2016","journal-title":"Probl. Inf. Transm."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"1419","DOI":"10.1214\/aoms\/1177700372","article-title":"Sufficiency and Approximate Sufficiency","volume":"35","author":"Cam","year":"1964","journal-title":"Ann. Math. Stat."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Raginsky, M. (August, January 31). Shannon meets Blackwell and Le Cam: Channels, codes, and statistical experiments. Proceedings of the 2011 IEEE International Symposium on Information Theory Proceedings, St. Petersburg, Russia.","DOI":"10.1109\/ISIT.2011.6033729"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"72","DOI":"10.1109\/TIT.2013.2284771","article-title":"Analytical and Numerical Characterizations of Shannon Ordering for Discrete Memoryless Channels","volume":"60","author":"Zhang","year":"2014","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"6759","DOI":"10.1109\/TIT.2018.2859252","article-title":"Characterizations of Two Channel Orderings: Input-Degradedness and the Shannon Ordering","volume":"64","author":"Nasser","year":"2018","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"888","DOI":"10.1109\/TIT.2018.2883705","article-title":"Generalised Entropies and Metric-Invariant Optimal Countermeasures for Information Leakage under Symmetric Constraints","volume":"65","author":"Khouzani","year":"2018","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Khouzani, M., and Malacaria, P. (2017, January 21\u201325). Leakage-Minimal Design: Universality, Limitations, and Applications. Proceedings of the IEEE 30th Computer Security Foundations Symposium (CSF), Santa Barbara, CA, USA.","DOI":"10.1109\/CSF.2017.40"},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Khouzani, M., and Malacaria, P. (2018). Optimal Channel Design: A Game Theoretical Analysis. Entropy, 20.","DOI":"10.3390\/e20090675"},{"key":"ref_31","first-page":"3165","article-title":"Optimal Accuracy-Privacy Trade-Off for Secure Computations","volume":"65","author":"Huth","year":"2018","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_32","unstructured":"K\u00f6pf, B., and Basin, D.A. (October, January 2). An information-theoretic model for adaptive side-channel attacks. Proceedings of the 14th ACM Conference on Computer and Communications Security, Alexandria, VA, USA."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/j.ic.2013.03.005","article-title":"Min-entropy as a resource","volume":"226","author":"Espinoza","year":"2013","journal-title":"Inf. Comp."},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Alvim, M.S., Chatzikokolakis, K., McIver, A., Morgan, C., Palamidessi, C., and Smith, G. (2014, January 19\u201322). Additive and Multiplicative Notions of Leakage, and Their Capacities. Proceedings of the IEEE 27th Computer Security Foundations Symposium (CSF), Vienna, Austria.","DOI":"10.1109\/CSF.2014.29"},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Gervais, A., Shokri, R., Singla, A.K., Capkun, S., and Lenders, V. (2014, January 3\u20137). Quantifying Web-Search Privacy. Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, Scottsdale, AZ, USA.","DOI":"10.1145\/2660267.2660367"},{"key":"ref_36","doi-asserted-by":"crossref","unstructured":"Beigi, G., Guo, R., Nou, A., Zhang, Y., and Liu, H. (2018). Protecting User Privacy: An Approach for Untraceable Web Browsing History and Unambiguous User Profiles. arXiv.","DOI":"10.1145\/3289600.3291026"},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"4631","DOI":"10.1109\/TIT.2010.2054471","article-title":"Optimized Query Forgery for Private Information Retrieval","volume":"56","author":"Forne","year":"2010","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1016\/j.tcs.2018.10.016","article-title":"An axiomatization of information flow measures","volume":"777","author":"Alvim","year":"2019","journal-title":"Theor. Comput. Sci."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/S0019-9958(71)90065-9","article-title":"Information-theoretical considerations on estimation problems","volume":"19","author":"Arimoto","year":"1971","journal-title":"Inf. Control"},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"2015","DOI":"10.1080\/03610929308831131","article-title":"Asymptotic distribution of (h, \u03a6)-entropies","volume":"22","author":"Salicru","year":"1993","journal-title":"Commun. Stat.-Theory Methods"},{"key":"ref_41","first-page":"229","article-title":"Information-type measures of difference of probability distributions and indirect observation","volume":"2","year":"1967","journal-title":"Stud. Sci. Math. Hung."},{"key":"ref_42","doi-asserted-by":"crossref","unstructured":"Ho, S.W., and Verd\u00fa, S. (2015, January 14\u201319). Convexity\/concavity of r\u00e9nyi entropy and \u03b1-mutual information. Proceedings of the 2015 IEEE International Symposium on Information Theory (ISIT), Hong Kong, China.","DOI":"10.1109\/ISIT.2015.7282554"},{"key":"ref_43","unstructured":"Arimoto, S. (1977). Information measures and capacity of order \u03b1 for discrete memoryless channels. Topics in Information Theory, North-Holland Publishing Company."},{"key":"ref_44","unstructured":"Massey, J.L. (July, January 27). Guessing and entropy. Proceedings of the IEEE Int. Symposium on Information Theory (ISIT), Trondheim, Norway."},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"479","DOI":"10.1007\/BF01016429","article-title":"Possible generalization of Boltzmann-Gibbs statistics","volume":"52","author":"Tsallis","year":"1988","journal-title":"J. Stat. Phys."},{"key":"ref_46","first-page":"28","article-title":"New non-additive measures of entropy for discrete probability distributions","volume":"10","author":"Sharma","year":"1975","journal-title":"J. Math. Sci."},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"3989","DOI":"10.1109\/TIT.2011.2110950","article-title":"Exponential decreasing rate of leaked information in universal random privacy amplification","volume":"57","author":"Hayashi","year":"2011","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_48","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/S0024-3795(98)10175-1","article-title":"Matrix majorization","volume":"288","author":"Dahl","year":"1999","journal-title":"Linear Algebra Its Appl."},{"key":"ref_49","unstructured":"Topkis, D.M. (1998). Supermodularity and Complementarity, Princeton University Press."},{"key":"ref_50","unstructured":"Marshall, A.W., Olkin, I., and Arnold, B.C. (1979). Inequalities: Theory of Majorization and Its Applications, Academic Press. Mathematics in Science and Engineering."},{"key":"ref_51","doi-asserted-by":"crossref","unstructured":"Khouzani, M.H.R., and Malacaria, P. (July, January 27). Relative Perfect Secrecy: Universally Optimal Strategies and Channel Design. Proceedings of the IEEE 29th Computer Security Foundations Symposium, CSF 2016, Lisbon, Portugal.","DOI":"10.1109\/CSF.2016.12"},{"key":"ref_52","doi-asserted-by":"crossref","unstructured":"Padr\u00f3, C. (2014). Information Theoretic Security for Encryption Based on Conditional R\u00e9nyi Entropies. Information Theoretic Security, Springer International Publishing.","DOI":"10.1007\/978-3-319-04268-8"},{"key":"ref_53","unstructured":"Cover, T.M., and Thomas, J.A. (2006). Elements of Information Theory, John Wiley & Sons, Inc.. [2nd ed.]."}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/24\/1\/39\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T07:53:22Z","timestamp":1760169202000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/24\/1\/39"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,12,25]]},"references-count":53,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2022,1]]}},"alternative-id":["e24010039"],"URL":"https:\/\/doi.org\/10.3390\/e24010039","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2021,12,25]]}}}