{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T18:32:26Z","timestamp":1773513146390,"version":"3.50.1"},"reference-count":50,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2025,1,24]],"date-time":"2025-01-24T00:00:00Z","timestamp":1737676800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100004359","name":"Swedish Research Council","doi-asserted-by":"publisher","award":["2019-03606"],"award-info":[{"award-number":["2019-03606"]}],"id":[{"id":"10.13039\/501100004359","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>A private compression design problem is studied, where an encoder observes useful data Y, wishes to compress them using variable-length code, and communicates them through an unsecured channel. Since Y are correlated with the private attribute X, the encoder uses a private compression mechanism to design an encoded message C and sends it over the channel. An adversary is assumed to have access to the output of the encoder, i.e., C, and tries to estimate X. Furthermore, it is assumed that both encoder and decoder have access to a shared secret key W. In this work, the design goal is to encode message C with the minimum possible average length that satisfies certain privacy constraints. We consider two scenarios: 1. zero privacy leakage, i.e., perfect privacy (secrecy); 2. non-zero privacy leakage, i.e., non-perfect privacy constraint. Considering the perfect privacy scenario, we first study two different privacy mechanism design problems and find upper bounds on the entropy of the optimizers by solving a linear program. We use the obtained optimizers to design C. In the two cases, we strengthen the existing bounds: 1. |X|\u2265|Y|; 2. The realization of (X,Y) follows a specific joint distribution. In particular, considering the second case, we use two-part construction coding to achieve the upper bounds. Furthermore, in a numerical example, we study the obtained bounds and show that they can improve existing results. Finally, we strengthen the obtained bounds using the minimum entropy coupling concept and a greedy entropy-based algorithm. Considering the non-perfect privacy scenario, we find upper and lower bounds on the average length of the encoded message using different privacy metrics and study them in special cases. For achievability, we use two-part construction coding and extended versions of the functional representation lemma. Lastly, in an example, we show that the bounds can be asymptotically tight.<\/jats:p>","DOI":"10.3390\/e27020124","type":"journal-article","created":{"date-parts":[[2025,1,24]],"date-time":"2025-01-24T11:50:47Z","timestamp":1737719447000},"page":"124","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Variable-Length Coding with Zero and Non-Zero Privacy Leakage"],"prefix":"10.3390","volume":"27","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9296-4939","authenticated-orcid":false,"given":"Amirreza","family":"Zamani","sequence":"first","affiliation":[{"name":"Division of Information Science and Engineering, KTH Royal Institute of Technology, 100-44 Stockholm, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7926-5081","authenticated-orcid":false,"given":"Mikael","family":"Skoglund","sequence":"additional","affiliation":[{"name":"Division of Information Science and Engineering, KTH Royal Institute of Technology, 100-44 Stockholm, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2025,1,24]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"824","DOI":"10.1109\/TIT.2020.3041224","article-title":"Secrecy by Design With Applications to Privacy and Compression","volume":"67","author":"Shkel","year":"2021","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1109\/JSAIT.2021.3055692","article-title":"A Compression Perspective on Secrecy Measures","volume":"2","author":"Shkel","year":"2021","journal-title":"IEEE J. Sel. Areas Inf. Theory"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"656","DOI":"10.1002\/j.1538-7305.1949.tb00928.x","article-title":"Communication theory of secrecy systems","volume":"28","author":"Shannon","year":"1949","journal-title":"Bell Syst. Tech. J."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"G\u00fcnd\u00fcz, D., Erkip, E., and Poor, H.V. (2009). Source coding under secrecy constraints. Securing Wireless Communications at the Physical Layer, Springer.","DOI":"10.1007\/978-1-4419-1385-2_8"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Schaefer, R.F., Boche, H., Khisti, A., and Poor, H.V. (2017). Information Theoretic Security and Privacy of Information Systems, Cambridge University Press.","DOI":"10.1017\/9781316450840"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"838","DOI":"10.1109\/TIFS.2013.2253320","article-title":"Utility-privacy tradeoffs in databases: An information-theoretic approach","volume":"8","author":"Sankar","year":"2013","journal-title":"IEEE Trans. Inf. Forensics Secur."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"8025","DOI":"10.1109\/TIT.2019.2934414","article-title":"Privacy with Estimation Guarantees","volume":"65","author":"Wang","year":"2019","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"594","DOI":"10.1109\/TIFS.2019.2903658","article-title":"Optimal Utility-Privacy Trade-Off With Total Variation Distance as a Privacy Measure","volume":"15","author":"Rassouli","year":"2020","journal-title":"IEEE Trans. Inf. Forensics Secur."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"2012","DOI":"10.1109\/TIFS.2019.2954652","article-title":"Data Disclosure under Perfect Sample Privacy","volume":"15","author":"Rassouli","year":"2020","journal-title":"IEEE Trans. Inf. Forensics Secur."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"918","DOI":"10.1109\/TIT.1983.1056749","article-title":"A source coding problem for sources with additional outputs to keep secret from the receiver or wiretappers (corresp.)","volume":"29","author":"Yamamoto","year":"1983","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"835","DOI":"10.1109\/18.9781","article-title":"A rate-distortion problem for a communication system with a secondary decoder to be hindered","volume":"34","author":"Yamamoto","year":"1988","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Issa, I., Kamath, S., and Wagner, A.B. (2016, January 16\u201318). An operational measure of information leakage. Proceedings of the 2016 Annual Conference on Information Science and Systems, Princeton, NJ, USA.","DOI":"10.1109\/CISS.2016.7460507"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Issa, I., Kamath, S., and Wagner, A.B. (2016, January 10\u201315). Maximal leakage minimization for the Shannon cipher system. Proceedings of the 2016 IEEE International Symposium on Information Theory, Barcelona, Spain.","DOI":"10.1109\/ISIT.2016.7541353"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Makhdoumi, A., Salamatian, S., Fawaz, N., and M\u00e9dard, M. (2014, January 2\u20135). From the information bottleneck to the privacy funnel. Proceedings of the 2014 IEEE Information Theory Workshop, Hobart, Australia.","DOI":"10.1109\/ITW.2014.6970882"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1109\/JSAIT.2021.3053432","article-title":"On Perfect Privacy","volume":"2","author":"Rassouli","year":"2021","journal-title":"IEEE J. Sel. Areas Inf. Theory"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"2312","DOI":"10.1109\/TIFS.2021.3053462","article-title":"A Design Framework for Strongly \u03c72-Private Data Disclosure","volume":"16","author":"Zamani","year":"2021","journal-title":"IEEE Trans. Inf. Forensics Secur."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1109\/TIFS.2021.3137755","article-title":"Data Disclosure With Non-Zero Leakage and Non-Invertible Leakage Matrix","volume":"17","author":"Zamani","year":"2022","journal-title":"IEEE Trans. Inf. Forensics Secur."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"2177","DOI":"10.1109\/TIT.2023.3326070","article-title":"On the Privacy-Utility Trade-Off With and Without Direct Access to the Private Data","volume":"70","author":"Zamani","year":"2024","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Zamani, A., Oechtering, T.J., and Skoglund, M. (July, January 26). Bounds for Privacy-Utility Trade-off with Non-zero Leakage. Proceedings of the 2022 IEEE International Symposium on Information Theory (ISIT), Espoo, Finland.","DOI":"10.1109\/ISIT50566.2022.9834872"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Zamani, A., Oechtering, T.J., and Skoglund, M. (2022, January 1\u20139). Bounds for Privacy-Utility Trade-off with Per-letter Privacy Constraints and Non-zero Leakage. Proceedings of the 2022 IEEE Information Theory Workshop (ITW), Mumbai, India.","DOI":"10.1109\/ITW54588.2022.9965856"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Asoodeh, S., Diaz, M., Alajaji, F., and Linder, T. (2016). Information extraction under privacy constraints. Information, 7.","DOI":"10.3390\/info7010015"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Zamani, A., Oechtering, T.J., G\u00fcnd\u00fcz, D., and Skoglund, M. (2023, January 4\u20137). Private Variable-Length Coding with Zero Leakage. Proceedings of the 2023 IEEE International Workshop on Information Forensics and Security (WIFS), Nurnberg, Germany.","DOI":"10.1109\/WIFS58808.2023.10374696"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Zamani, A., Oechtering, T.J., and Skoglund, M. (2023, January 4\u20137). Private Variable-Length Coding with Non-Zero Leakage. Proceedings of the 2023 IEEE International Workshop on Information Forensics and Security (WIFS), Nurnberg, Germany.","DOI":"10.1109\/WIFS58808.2023.10374604"},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Wang, S., Lin, Z., and Fanti, G. (2024, January 7\u201312). Statistic Maximal Leakage. Proceedings of the 2024 IEEE International Symposium on Information Theory (ISIT), Athens, Greece.","DOI":"10.1109\/ISIT57864.2024.10619258"},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Sreekumar, S., and G\u00fcnd\u00fcz, D. (2019, January 7\u201312). Optimal Privacy-Utility Trade-off under a Rate Constraint. Proceedings of the 2019 IEEE International Symposium on Information Theory, Paris, France.","DOI":"10.1109\/ISIT.2019.8849330"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"8164","DOI":"10.1109\/TIT.2024.3452105","article-title":"Robust Privatization With Multiple Tasks and the Optimal Privacy-Utility Tradeoff","volume":"70","author":"Liu","year":"2024","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Zarrabian, M.A., Ding, N., and Sadeghi, P. (2023). On the Lift, Related Privacy Measures, and Applications to Privacy\u2013Utility Trade-Offs. Entropy, 25.","DOI":"10.3390\/e25040679"},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Dwork, C., McSherry, F., Nissim, K., and Smith, A. (2006, January 4\u20137). Calibrating noise to sensitivity in private data analysis. Proceedings of the Theory of Cryptography Conference, TCC 2006, New York, NY, USA.","DOI":"10.1007\/11681878_14"},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Dwork, C., Kenthapadi, K., McSherry, F., Mironov, I., and Naor, M. (June, January 28). Our data, ourselves: Privacy via distributed noise generation. Proceedings of the Advances in Cryptology-EUROCRYPT 2006: 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, St. Petersburg, Russia.","DOI":"10.1007\/11761679_29"},{"key":"ref_30","unstructured":"Kairouz, P., Oh, S., and Viswanath, P. (2015, January 7\u20139). The composition theorem for differential privacy. Proceedings of the International Conference on Machine Learning, Lille, France."},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Cuff, P., and Yu, L. (2016, January 24\u201328). Differential privacy as a mutual information constraint. Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Vienna, Austria.","DOI":"10.1145\/2976749.2978308"},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Barthe, G., and Olmedo, F. (2013, January 8\u201312). Beyond differential privacy: Composition theorems and relational logic for f-divergences between probabilistic programs. Proceedings of the International Colloquium on Automata, Languages, and Programming, Riga, Latvia.","DOI":"10.1007\/978-3-642-39212-2_8"},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Feldman, V., Mironov, I., Talwar, K., and Thakurta, A. (2018, January 7\u20139). Privacy amplification by iteration. Proceedings of the 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), Paris, France.","DOI":"10.1109\/FOCS.2018.00056"},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Kocaoglu, M., Dimakis, A., Vishwanath, S., and Hassibi, B. (2017, January 4\u20139). Entropic causal inference. Proceedings of the AAAI Conference on Artificial Intelligence, San Francisco, CA, USA.","DOI":"10.1609\/aaai.v31i1.10674"},{"key":"ref_35","unstructured":"Compton, S., Katz, D., Qi, B., Greenewald, K., and Kocaoglu, M. (2023, January 25\u201327). Minimum-entropy coupling approximation guarantees beyond the majorization barrier. Proceedings of the International Conference on Artificial Intelligence and Statistics, Valencia, Spain."},{"key":"ref_36","doi-asserted-by":"crossref","unstructured":"Shkel, Y.Y., and Yadav, A.K. (2023, January 25\u201330). Information spectrum converse for minimum entropy couplings and functional representations. Proceedings of the 2023 IEEE International Symposium on Information Theory (ISIT), Taipei, Taiwan.","DOI":"10.1109\/ISIT54713.2023.10206466"},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"5011","DOI":"10.1109\/TIT.2017.2700857","article-title":"Principal Inertia Components and Applications","volume":"63","author":"Calmon","year":"2017","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1109\/18.32120","article-title":"Multiterminal source encoding with encoder breakdown","volume":"35","author":"Berger","year":"1989","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Zamani, A., Rodr\u00edguez-G\u00e1lvez, B., and Skoglund, M. (2024). On information theoretic fairness: Compressed representations with perfect demographic parity. arXiv.","DOI":"10.1109\/ITW61385.2024.10807019"},{"key":"ref_40","doi-asserted-by":"crossref","unstructured":"Erlingsson, \u00da., Pihur, V., and Korolova, A. (2014, January 3\u20137). Rappor: Randomized aggregatable privacy-preserving ordinal response. Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, Scottsdale, AZ, USA.","DOI":"10.1145\/2660267.2660348"},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"208","DOI":"10.1109\/JSAIT.2021.3054692","article-title":"Three variants of differential privacy: Lossless conversion and applications","volume":"2","author":"Asoodeh","year":"2021","journal-title":"IEEE J. Sel. Areas Inf. Theory"},{"key":"ref_42","unstructured":"Alghamdi, W., Gomez, J.F., Asoodeh, S., Calmon, F., Kosut, O., and Sankar, L. (2023, January 23\u201329). The saddle-point method in differential privacy. Proceedings of the International Conference on Machine Learning, Honolulu, HI, USA."},{"key":"ref_43","doi-asserted-by":"crossref","unstructured":"Dwork, C., Rothblum, G.N., and Vadhan, S. (2010, January 23\u201326). Boosting and differential privacy. Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, Las Vegas, NV, USA.","DOI":"10.1109\/FOCS.2010.12"},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"1355","DOI":"10.1002\/j.1538-7305.1975.tb02040.x","article-title":"The wire-tap channel","volume":"54","author":"Wyner","year":"1975","journal-title":"Bell Syst. Tech. J."},{"key":"ref_45","first-page":"149","article-title":"Common information is far less than mutual information","volume":"2","year":"1973","journal-title":"Probl. Control Inf. Theory"},{"key":"ref_46","doi-asserted-by":"crossref","unstructured":"Basciftci, Y.O., Wang, Y., and Ishwar, P. (February, January 31). On privacy-utility tradeoffs for constrained data release mechanisms. Proceedings of the 2016 Information Theory and Applications Workshop, La Jolla, CA, USA.","DOI":"10.1109\/ITA.2016.7888175"},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"6967","DOI":"10.1109\/TIT.2018.2865570","article-title":"Strong Functional Representation Lemma and Applications to Coding Theorems","volume":"64","author":"Li","year":"2018","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_48","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1109\/TIT.1975.1055346","article-title":"The common information of two dependent random variables","volume":"21","author":"Wyner","year":"1975","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_49","doi-asserted-by":"crossref","unstructured":"Zamani, A., Oechtering, T.J., G\u00fcnd\u00fcz, D., and Skoglund, M. (2023, January 24\u201327). Cache-Aided Private Variable-Length Coding with Zero and Non-Zero Leakage. Proceedings of the 2023 21st International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt), Singapore.","DOI":"10.23919\/WiOpt58741.2023.10349822"},{"key":"ref_50","doi-asserted-by":"crossref","first-page":"2856","DOI":"10.1109\/TIT.2014.2306938","article-title":"Fundamental limits of caching","volume":"60","author":"Niesen","year":"2014","journal-title":"IEEE Trans. Inf. Theory"}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/27\/2\/124\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,8]],"date-time":"2025-10-08T10:35:53Z","timestamp":1759919753000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/27\/2\/124"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,24]]},"references-count":50,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2025,2]]}},"alternative-id":["e27020124"],"URL":"https:\/\/doi.org\/10.3390\/e27020124","relation":{},"ISSN":["1099-4300"],"issn-type":[{"value":"1099-4300","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,1,24]]}}}