Secure lossless compression

The framework of secrecy by design is introduced and the fundamental limits of lossless data compression are analyzed for this setting. The main idea behind secrecy by design is to begin with an operational secrecy constraint, which is modeled by a secrecy function f <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">s</sub> , and then to derive fundamental limits for the performance of the resulting secrecy system. Focusing on the non-asymptotic fundamental limits of lossless compression, variable-length lossless compression and fixed-length almost-lossless compression are studied. Although it is well known that the traditional fundamental limits of variable-length and almost lossless fixed-length compression are intimately related, this relationship collapses once the secrecy constraint is incorporated. The current paper focuses on the setting in which the value of the secrecy function is known to the decompressor as side information: the main challenge is to reconcile the outcome of the information source without violating the secrecy constraint.