4.3 Information-theoretical security (perfect secrecy)

The historical roots of encryption are in military and diplomatic communications. The first encryption schemes were perhaps invented by the ancient Greeks and Romans. These encryption schemes have survived until today in the form of examples for easily breakable ciphers and can be found in virtually any textbook on cryptography.

Another famous historical example is provided by the Enigma encryption machine, which was used by the Axis powers in World War II. Due to its large key space, this sophisticated rotor-based machine was deemed unbreakable by its inventors. However, building on the work of Polish mathematicians and using (for the time) massive computing power, the Allies were able to prove them wrong [171]. Judging from these historical examples, one might get the impression that all encryption schemes can be broken. However, it is possible to devise provably secure encryption schemes.

An encryption scheme that is provably...