Unconditional Security in Cryptography
The fact that most presently-used cryptosystems cannot be rigorously proven secure and hence permanently face the risk of being broken motivates the search for schemes with unconditional security. The corresponding proofs however must be based on information theory rather than complexity theory. One reason for this is the lack of known lower bounds on the running time of algorithms solving certain computational problems such as the discrete-logarithm problem or the integer-factoring problem. At the beginning of an information-theoretic analysis of cryptosystems stands Shannon's definition of perfect secrecy, unquestionably the strongest possible security definition, and his well-known inequality giving a lower bound on the key length of every perfectly secret cipher, thus suggesting that such a high level of confidentiality cannot be realized in any practical scheme. This pessimism has later been qualified by several authors who showed that unconditional security can be achieved in many special but realistic scenarios. Some of these approaches are described in this introductory overview article.