Information-Theoretically Secure Symmetric Schemes

The first important step towards modem scientific cryptology was Claude Shannon s work [Shan49]. There, for the first time, a precise (and, according to informal requirements, certainly sufficient) notion of security for any type of cryptologic scheme was defined the information-theoretic security of secrecy schemes, sometimes called Shannon security. Roughly, the definition requires that a ciphertext provides an outsider with no additional information at all about the message. The information-theoretic notion means that the scheme is absolutely unbreakable, i.e., unbreakable even by attackers with unrestricted computing power and unrestricted memory. 

However, in the same article it was proved that any secrecy scheme that is provably secure in this sense is equivalent to one-time pads (see Section 1.5) or even less efficient. Thus, for a while, there was no further research in this field. Besides, for most applications, one-time pads were regarded as too inefficient, because the length of the secret key, which has to be exchanged beforehand, must be at least equal to the overall length of the messages that might be sent later. Hence one continued to use other schemes in practice. 

The word cryptology is nowadays used for all schemes, or only all mathematical schemes, which enable parties who distrust each other or outsiders to cooperate in a useful way. For more types of cryptologic schemes than authentication and secrecy schemes, see, e.g, [Bras88, Schn96] or some subschemes in the later chapters of this text. Cryptography is sometimes regarded as a synonym and sometimes as more restricted, either to the construction of schemes (in contrast to cryptanalysis, for instance) or to secrecy schemes. 

In particular, efficiently computable authentication codes where the key length only grows logarithmically with the length of the messages to be authenticated later were constructed in [WeCaSl]. An improvement of this scheme and an overview of the literature in this field can be found in [BJKS94]. 

In practice, however, to this day, schemes with even greater efficiency are used for symmetric authentication, instead of information-theoretically secure ones schemes about whose security no precise knowledge exists. Most common are certain modes of operation of the (former) Data Encryption Standard (DES). (See, e.g., [DES77] for the standard, [DaPr89] for modes of operation and possible applications, and [BiSh93] for new security examinations.) 

---

The restriction to computational security is not necessarily a serious objection to the use of asymmetric authentication, because, as mentioned, most symmetric schemes used in practice are not information-theoretically secure either, nor has their security been proved in any stricter sense. 

A similar work for authentication schemes was only published 15 years later In [GiMS74], the information-theoretic, i.e., absolute security of symmetric authentication schemes was defined. Schemes complying with this definition are often called authentication codes. Like Claude Shannon s work, [GiMS74] already contains both concrete constructions of authentication codes and lower bounds on the achievable efficiency, and in particular, the key length. In contrast to secrecy schemes, however, the upper and lower bounds are not identical furthermore, the constructions are less trivial. Therefore, there has been further research in this field. 

---