Schemes with Information-Theoretic Security

Signature schemes with information-theoretic security are easy to classify Only one scheme exists so far ([ChRo91] with improvements and extensions in [PfWa92, Waid91]). With the conventions from Chapter 5, it is not even quite a signature scheme In contrast to all other schemes, it does not withstand arbitrary active attacks (see Section 5.4.2). It offers the following service  

The special problem with the degree of security is due to the fact that the entities of recipients and courts have secret information and divulge some of it in authentication and disputes, in contrast to all other existing signature schemes. Hence not only the signer, but also recipients and courts are vulnerable to active attacks, as described at the end of Section 5.4.2. This seems to be a more difficult problem than active attacks on signers, because each signature is issued only once, whereas it may be tested very often.  

One could try to introduce a parameter for the maximum number of tests a recipient or court carries out with respect to a given initialization, similar to the message bound for the number of authentications. However, this would entail further changes to the requirements — at present, it is required that any recipient can have any received authenticated message disputed at any time. 

There exists a distributed variant of authentication for this scheme (see Section 5.2.11), i.e., a protocol where either all the recipients accept a signature or none does [PfWa92b]. This is not trivial, even if reliable broadcast channels are given, because the entities of the recipients have different test keys. 

---

It is not hard to imagine that a scheme with information-theoretic security would greatly increase the legal security of digital signatures. However, as mentioned in Section 6.1.5, such schemes are currently impractical and it seems that they will never be very efficient. Hence their social implications are not very relevant. In contrast, practical schemes with fail-stop or dual security exist. Hence the only two topics of this section are... 

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. 

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.)... 

Schemes with special security properties such as fail-stop, dual, and information-theoretic security will be treated in detail later (starting in Chapter 3 and with an overview in Chapter 6) and are therefore not treated here.

This section sketches the information-theoretically secure signature schemes from [ChRo91, PfWa92, Waid91]. These schemes are with non-interactive authentication and 2-party disputes hence one can speak of signatures and of testing them. 

Security parameters. As some requirements on a fail-stop signature scheme have to be fulfilled information-theoretically and others only computationally, it is natural to consider two security parameters. They are called a and k, where a measures the information-theoretic security and k the computational security. The primary role of cr is that the error probability in the fail-back requirement of the signer on disputes decreases exponentially with a. In other words, a determines the probability that the signer is cheated with unprovable forgeries. The primary role of k is to ensure the correctness of broken , i.e., the larger k is, the harder it should be to compute valid proofs of forgeries (and thus forgeries in the first place). 

The second question is studied for the difference between signature schemes with ordinary, fail-stop, and information-theoretic security. Moreover, one can ask how much an increase in security within a given security type affects the attainable efficiency (see Figure 11.1). With a requirement that is fulfilled information-theoretically with an error probability, such an increase is expressed by the security parameter a that determines the bound on the error probability. Handling computational security is more complicated this is discussed in the introduction to Section 11.3. 

Theorem 11.21. Let a rudimentary standard information-theoretically secure signature scheme, parameters par = ( 1 , 1 , 1 ) with conditional entropy of the i-th correct signature, given the previous ones, is large ... 

The abbreviated names of the constructions mean bottom-up tree authentication (10.9), top-down tree authentication (10.13), top-down tree authentication with a small amount of private storage (10.19), the discrete-logarithm scheme with minimized secret key (10.22) without combination with tree authentication, and the construction with a list-shaped tree for a fixed recipient from Section 10.6. The first column of lower bounds is for standard fail-stop signature schemes (Sections 11.3 and 11.4), the second one for standard information-theoretically secure signature schemes (Section 11.5) here the length of a test key has been entered in the row with the public keys. 

The parameters have their usual meaning from the previous sections. In particular, N is the message bound, / in the information-theoretically secure signature schemes is the number of testers (i.e., recipients or courts or both, depending on the class of schemes), and k, I, cr, tr, and cr = min(security parameters with krisk bearers. As all the constructions of fail-stop signature schemes are with prekey, and the same prekey can be used for several signers, only the main public key is shown. 

Information-theoretically secure schemes, in contrast, even with the mdimentary security requirements made above, have much higher lower bounds, at least in applications where a large number of participants may have to test any given signature. 

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. 

---