Lists That Are Smaller Than Their Parts: A Coding Approach to Tunable Secrecy
Classic information-theoretic approaches to secrecy are concerned with unconditionally secure systems, i.e. schemes that manage to hide all the bits of a message from an adversary with unbounded computational resources. It is well known that, for a noiseless setting, unconditional (i.e. perfect) secrecy can only be attained when both communicating parties share a random key with entropy at least as large as the message itself. In other cases, perfect secrecy can sometimes be achieved by exploiting particular characteristics of the considered model, such as when the legitimate communicating party has a less noisy channel than the eavesdropper (wiretap channel).