Channel-Supermodular Entropies: Order Theory and an Application to Query Anonymization
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–Rényi conditional entropies (which include Shannon and min-entropy as special cases)...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2021-12-01
|
| Series: | Entropy |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1099-4300/24/1/39 |
| _version_ | 1827665711577694208 |
|---|---|
| author | Arthur Américo MHR Khouzani Pasquale Malacaria |
| author_facet | Arthur Américo MHR Khouzani Pasquale Malacaria |
| author_sort | Arthur Américo |
| collection | DOAJ |
| description | 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–Rényi 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. |
| first_indexed | 2024-03-10T01:31:58Z |
| format | Article |
| id | doaj.art-be33d12663c54dfca3e56c2c67a76225 |
| institution | Directory Open Access Journal |
| issn | 1099-4300 |
| language | English |
| last_indexed | 2024-03-10T01:31:58Z |
| publishDate | 2021-12-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Entropy |
| spelling | doaj.art-be33d12663c54dfca3e56c2c67a762252023-11-23T13:40:54ZengMDPI AGEntropy1099-43002021-12-012413910.3390/e24010039Channel-Supermodular Entropies: Order Theory and an Application to Query AnonymizationArthur Américo0MHR Khouzani1Pasquale Malacaria2School of Electronic Engineering and Computer Science, Queen Mary University of London, London E1 4NS, UKSchool of Electronic Engineering and Computer Science, Queen Mary University of London, London E1 4NS, UKSchool of Electronic Engineering and Computer Science, Queen Mary University of London, London E1 4NS, UKThis 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–Rényi 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.https://www.mdpi.com/1099-4300/24/1/39information theoryquantitative information flowchannel orderingmore-capableless-noisybroadcast channels |
| spellingShingle | Arthur Américo MHR Khouzani Pasquale Malacaria Channel-Supermodular Entropies: Order Theory and an Application to Query Anonymization Entropy information theory quantitative information flow channel ordering more-capable less-noisy broadcast channels |
| title | Channel-Supermodular Entropies: Order Theory and an Application to Query Anonymization |
| title_full | Channel-Supermodular Entropies: Order Theory and an Application to Query Anonymization |
| title_fullStr | Channel-Supermodular Entropies: Order Theory and an Application to Query Anonymization |
| title_full_unstemmed | Channel-Supermodular Entropies: Order Theory and an Application to Query Anonymization |
| title_short | Channel-Supermodular Entropies: Order Theory and an Application to Query Anonymization |
| title_sort | channel supermodular entropies order theory and an application to query anonymization |
| topic | information theory quantitative information flow channel ordering more-capable less-noisy broadcast channels |
| url | https://www.mdpi.com/1099-4300/24/1/39 |
| work_keys_str_mv | AT arthuramerico channelsupermodularentropiesordertheoryandanapplicationtoqueryanonymization AT mhrkhouzani channelsupermodularentropiesordertheoryandanapplicationtoqueryanonymization AT pasqualemalacaria channelsupermodularentropiesordertheoryandanapplicationtoqueryanonymization |