A Compression Perspective on Secrecy Measures
- 2 February 2021
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Journal on Selected Areas in Information Theory
- Vol. 2 (1) , 163-176
Abstract
The relationships among secrecy, compression rate and shared secret key rate in lossless data compression are studied through the lenses of perfect secrecy, mutual information leakage, maximal leakage, local differential privacy, and secrecy by design. It is revealed that the utility cost of jointly compressing and securing data is very sensitive to the adopted secrecy metric and the specifics of the compression setting. That is, although it is well-known that the fundamental limits of traditional lossless variable-length compression and almost-lossless fixed-length compression are intimately related, this relationship collapses for many secrecy measures. The asymptotic fundamental limit of almost-lossless fixed-length compression remains entropy for all secrecy measures studied. However, the fundamental limit of lossless variable-length compression is no longer entropy under perfect secrecy, secrecy by design, or local differential privacy. Moreover, there are significant differences in secret key/secrecy tradeoffs between lossless and almost-lossless compression under perfect secrecy, secrecy by design, maximal leakage, and local differential privacy.Keywords
Funding Information
- U.S. National Science Foundation (CCF-0939370, CCF-1908308)
This publication has 39 references indexed in Scilit:
- Rate-Distortion Theory for Secrecy SystemsIEEE Transactions on Information Theory, 2014
- What Can We Learn Privately?SIAM Journal on Computing, 2011
- Our Data, Ourselves: Privacy Via Distributed Noise Generation2006
- On Compressing Encrypted DataIEEE Transactions on Signal Processing, 2004
- Compression and Information Leakage of Plaintext2002
- The Shannon cipher system with a guessing wiretapperIEEE Transactions on Information Theory, 1999
- Coding theorems for Shannon's cipher system with correlated source outputs, and common informationIEEE Transactions on Information Theory, 1994
- A rate-distortion problem for a communication system with a secondary decoder to be hinderedIEEE Transactions on Information Theory, 1988
- The Wire-Tap ChannelBell System Technical Journal, 1975
- Communication Theory of Secrecy Systems*Bell System Technical Journal, 1949