Message authentication and (digital) signatures were the first tasks that joined encryption to form modern cryptography. Both message authentication and digital signatures are concerned with the “authenticity” of data, and the difference between them is analogous to the difference between private–key and public–key encryption schemes.

In this chapter, we define message authentication and digital signatures, and the security notions associated with them. We show how to construct message–authentication schemes using pseudorandom functions, and how to construct signature schemes using one–way permutations. We stress that the latter construction employs arbitrary one–way permutations, which do not necessarily have a trapdoor.

Organization. The basic definitions are presented in Section 6.1. Constructions of message–authentication schemes and signature schemes are presented in Sections 6.3 and 6.4, respectively. Toward presenting these constructions, we discuss restricted types of message authentication and signature schemes, which are of independent interest, such as length–restricted schemes (see Section 6.2) and one–time signature schemes (see Section 6.4.1). Additional issues are discussed in Sections 6.5 and 6.6.

Teaching Tip. In contrast to the case of encryption schemes (cf. Chapter 5), the definitional treatment of signatures (and message authentication) is quite simple. The treatment of length–restricted schemes (see Section 6.2) plays an important role in the construction of standard schemes, and thus we strongly recommend highlighting this treatment. We suggest focusing on the presentation of the simplest construction of message–authentication schemes (provided in Section 6.3.1) and on the (not–so–simple) construction of signature schemes that is provided in Sections 6.4.1 and 6.4.2.

Up to the 1970s, Cryptography was understood as the art of building encryption schemes, that is, the art of constructing schemes allowing secret data exchange over insecure channels. Since the 1970s, other tasks (e.g., signature schemes) have been recognized as falling within the domain of Cryptography (and even being at least as central to Cryptography). Yet the construction of encryption schemes remains, and is likely to remain, a central enterprise of Cryptography.

In this chapter we review the well–known notions of private–key and public–key encryption schemes. More importantly, we define what is meant by saying that such schemes are secure. This definitional treatment is a cornerstone of the entire area, and much of this chapter is devoted to various aspects of it. We also present several constructions of secure (private–key and public–key) encryption schemes. It turns out that using randomness during the encryption process (i.e., not only at the key–generation phase) is essential to security.

Organization. Our main treatment (i.e., Sections 5.1–5.3) refers to security under “passive” (eavesdropping) attacks. In contrast, in Section 5.4, we discuss notions of security under active attacks, culminating in robustness against chosen ciphertext attacks. Additional issues are discussed in Section 5.5.

Teaching Tip. We suggest to focus on the basic definitional treatment (i.e., Sections 5.1 and 5.2.1 – 5.2.4) and on the the feasibility of satisfying these definitions (as demonstarted by the simplest constructions provided in Sections 5.3.3 and 5.3.4.1). The overview to security under active attacks (i.e., Section 5.4.1) is also recommended.

The design of secure protocols that implement arbitrarily desired functionalities is a major part of modern cryptography. Taking the opposite perspective, the design of any cryptographic scheme may be viewed as the design of a secure protocol for implementing a suitable functionality. Still, we believe that it makes sense to differentiate between basic cryptographic primitives (which involve little interaction) like encryption and signature schemes, on the one hand, and general cryptographic protocols, on the other hand.

In this chapter we consider general results concerning secure multi–party computations, where the two–party case is an important special case. In a nutshell, these results assert that one can construct protocols for securely computing any desirable multi–party functionality (see the following terminology). Indeed, what is striking about these results is their generality, and we believe that the wonder is not diminished by the (various alternative) conditions under which these results hold.

Our focus on the general study of secure multi–party computation (rather than on protocols for solving specific problems) is natural in the context of the theoretical treatment of the subject matter. We wish to highlight the importance of this general study to practice. Firstly, this study clarifies fundamental issues regarding security in a multi–party environment. Secondly, it draws the lines between what is possible in principle and what is not. Thirdly, it develops general techniques for designing secure protocols. And last, sometimes it may even yield schemes (or modules) that may be incorporated in practical systems.

Cryptography is concerned with the construction of schemes that withstand any abuse. Such schemes are constructed so as to maintain a desired functionality, even under malicious attempts aimed at making them deviate from their prescribed functionality.

The design of cryptographic schemes is a very difficult task. One cannot rely on intuitions regarding the typical state of the environment in which the system operates. For sure, the adversary attacking the system will try to manipulate the environment into untypical states. Nor can one be content with countermeasures designed to withstand specific attacks because the adversary (which acts after the design of the system is completed) will try to attack the schemes in ways that are typically different from the ones envisioned by the designer. The validity of the foregoing assertions seems self–evident; still, some people hope that in practice, ignoring these tautologies will not result in actual damage. Experience shows that these hopes rarely come true; cryptographic schemes based on make–believe are broken, typically sooner than later.

In view of these assertions, we believe that it makes little sense to make assumptions regarding the specific strategy that the adversary may use. The only assumptions that can be justified refer to the computational abilities of the adversary.

From the previous chapter, we know that a code alphabet A is a finite set. In order to play mathematical games, we are going to equip A with some algebraic structures. As we know, a field, such as the real field R or the complex field C, has two operations, namely addition and multiplication. Our idea is to define two operations for A so that A becomes a field. Of course, then A is a field with only finitely many elements, whilst R and C are fields with infinitely many elements. Fields with finitely many elements are quite different from those that we have learnt about before.

The theory of finite fields goes back to the seventeenth and eighteenth centuries, with eminent mathematicians such as Pierre de Fermat (1601–1665) and Leonhard Euler (1707–1783) contributing to the structure theory of special finite fields. The general theory of finite fields began with the work of Carl Friedrich Gauss (1777–1855) and Evariste Galois (1811–1832), but it only became of interest for applied mathematicians and engineers in recent decades because of its many applications to mathematics, computer science and communication theory. Nowadays, the theory of finite fields has become very rich. In this chapter, we only study a small portion of this theory. The reader already familiar with the elementary properties of finite fields may wish to proceed directly to the next chapter.

In the seminal paper ‘A mathematical theory of communication’ published in 1948, Claude Shannon showed that, given a noisy communication channel, there is a number, called the capacity of the channel, such that reliable communication can be achieved at any rate below the channel capacity, if proper encoding and decoding techniques are used. This marked the birth of coding theory, a field of study concerned with the transmission of data across noisy channels and the recovery of corrupted messages.

In barely more than half a century, coding, theory has seen phenomenal growth. It has found widespread application in areas ranging from communication systems, to compact disc players, to storage technology. In the effort to find good codes for practical purposes, researchers have moved beyond block codes to other paradigms, such as convolutional codes, turbo codes, space-time codes, low-density-parity-check (LDPC) codes and even quantum codes. While the problems in coding theory often arise from engineering applications, it is fascinating to note the crucial role played by mathematics in the development of the field. The importance of algebra, combinatorics and geometry in coding theory is a commonly acknowledged fact, with many deep mathematical results being used in elegant ways in the advancement of coding theory.

Coding theory therefore appeals not just to engineers and computer scientists, but also to mathematicians. It has become increasingly common to find the subject taught as part of undergraduate or graduate curricula in mathematics.