Limitations of Incompressible Encodings

This thesis studies the limitations of incompressible encodings with information- theoretic security. We demonstrate a flaw in the existing proof of the impossibility of constructing incompressible encodings information-theoretically. Our main contribu- tion is a full proof of impossibility of existence of non-trivial information-theoretically secure incompressible encoding schemes. In the first part of the thesis, we introduce the basics of incompressible encodings and provide the necessary definitions. Next, we present the flaws in the existing argument and provide explicit counterexamples to them. Throughout the rest of the thesis, we gradually construct a complete proof. We start by showing the impossibility under a few additional restrictions on the correctness and structure of the schemes that we subsequently remove one by one. Finally, we present an adversary able to break any non-trivial incompressible encoding scheme.