Security information-theoretic

P erez-Freire, L., Comesa na, P., P erez-Gonz alez, F. (2005). Information-theoretic analysis of security in side-informed data hiding. Proceeding of the yth Information Hiding Workshop. 

Complete and absolute security is a theoretical construction no information system can be made totally secure, unless it is locked in a room with no access at all and nobody is allowed to use it. On the other hand, security measures carry a cost, which is usually proportional to their effectiveness. Therefore, the best we can do is to secure information systems as best as possible within a given, finite, monetary budget. The purpose of all protection strategies is to reduce the risk that the information infrastructure is exposed to and, as some risk will always remain, to mitigate or accept this remaining risk. To do this, because the risk function is increasing in all its elements, one must reduce one, more, or all the elements of risk. As it is... 

Security The key assignment in this method is information theoretic, that is keys are assigned randomly and independently. Hence the key-indistinguishability property of this method follows from the fact that no u e 7 is contained in any of the subsets im, as stated in Claim 1. 

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. 

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. 

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. 

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.

In later chapters, several digital signature schemes will be presented or mentioned where at least the signer is information-theoretically secure, and sometimes even the recipient, too. The main point in overcoming the impossibility proof was to notice that digital signature schemes may have structures other than that described in [DiHe76] and made precise in the GMR definition (see Sections 2.3, 2.6). 

Moreover, the fail-stop property will only be used with two specific degrees of security low is on a cryptologic assumption and high information-theoretically . In principle, other combinations are also possible, for instance that low needs an upper bound on the number of attackers and high means that more attackers are tolerated. 

Information-theoretic security without error probability. For the simplest case, the definition can now be completed The scheme Scheme fulfils the given requirement Req information-theoretically without error probability if for all attackers A e Attackerjlass(Scheme, Req), all system parameters sys jars e Sys jars Scheme), and all interest groups i group I groups Req), all sequences of interface events at the interest group fulfil Req, i.e.,... 

Primarily, the two requirements on disputes are considered (and related additional requirements, such as fail-stop properties), and only information-theoretic and computational security are distinguished. Unforgeability, as mentioned, is a consequence of these two requirements. The other requirements are usually ftilfilled information-theoretically. 

Ordinary security is the type of security that ordinary digital signature schemes offer The requirement of the signer on disputes is fulfilled computationally only, that of the recipient information-theoretically, and there is no fail-stop property. If transferability is required, the effectiveness of transfers also holds information-theoretically. 

Fail-stop security has been described in Section 5.2.9 the degree low is now computationally and high is information-theoretically. Thus the fall-back requirements of both the signer and the recipient on disputes are fulfilled information-theoretically and the correctness of broken computationally. 

Information-theoretic security means that the requirements of both the signer and the recipient on disputes hold information-theoretically. 

One could try to achieve all information-theoretic security without an error probability. This subsection shows that this is impossible by giving proof sketches of the following statements ... 

A consequence of these statements is that subdividing the security types from Section 5.4.3, Combinations of Degrees of Security in Signature Schemes , according to the error probabilities in their information-theoretic parts does not yield many new types. 

With information-theoretic security, there is an error probability for both parties. 

The security types considered are fail-stop, dual, and information-theoretic security. In other words, the schemes considered here offer information-theoretic security for signers, i.e., either the requirement or the fail-back requirement of the signer on disputes is fulfilled information-theoretically. 

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

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

Being able to offer information-theoretic security to one out of two parties is most interesting in applications with an a-priori asymmetry between the parties. Asymmetry primarily means that there is a stronger and a weaker partner Figure 6.4 illustrates this. It is useful to make the weaker partner information-theoretically secure. 

Some reasons for making clients information-theoretically secure in a payment scheme are ... 

To see this, recall that a real court is not obliged to comply with the technical view of how it has to decide it could believe a supposed signer that an ordinary digital signature is a forgery (see Section 3.1). A court should be far less likely to do so if it is proven that clients are information-theoretically secure. ... 

Usually, at least 2 equally probable secret keys correspond to each public key if one aims at information-theoretic security with an error probability of at most 2 ... 

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. 

---