Foundations of Cryptography: Information Theory & Security Models

The Big Picture

Cryptography is the study of techniques to allow secure communication and data storage in the presence of attackers.

That's a good start, but it doesn't tell us much on its own. If we want to define cryptography in a more formal and precise way, we have to refer to the information theory, credited by Claude Shannon:

A communication is a flow of information over a channel that takes place between two endpoints: a sender, made of an information source and an encoder, and a receiver, made of an information destination and a decoder.

As convention, the two endpoints are usually called "Alice" and "Bob": you'll see these names everywhere in cryptography. The "information" can be modeled as strings of symbols belonging to a finite alphabet. Being in the computer science discipline, this alphabet is usually $\Sigma=\lbrace 0,1\rbrace$ . The ordinary readable string containing the information the sender wants to transmit is called message (or plaintext), while the encoded version of the message that is actually transmitted over the channel is the ciphertext.

A cryptosystem is a tuple $(P,C,K,E,D)$ , where:

• The plaintext space $P=\lbrace 0,1\rbrace ^{l}$ is the set of all possible plaintexts $ptx$ ;

• The ciphertext space $C=\lbrace 0,1\rbrace ^{l'}$ is the set of all possible ciphertexts $ctx$ . Please note that, in general, $l{\neq}l'$ , i.e. the length of the plaintext does not necessarily have to coincide with that of the ciphertext;

• The key space $K=\lbrace 0,1\rbrace ^{\lambda}$ is the set of all possible keys $k$ ;

• The encryption function $E$ is a function defined as $E:P\times K\rightarrow C$ ;

• The decryption function $D$ is a function defined as $D:C\times K\rightarrow P$ .

A cipher is an implementation of the encryption function $E$ and decryption function $D$ such that, for every plaintext $ptx\in P$ , $\exists k,k'\in K$ such that $D(E(ptx, k),k')=ptx$ . In case $k=k'$ the cipher is called symmetric cipher, if instead $k\neq k'$ asymmetric cipher.

A cipher includes therefore an encryption algorithm that, given a key and a plaintext, produces a ciphertext, and a decryption algorithm that, given another key and any ciphertext produced during the encryption, returns the original plaintext. As we'll see, the functions $E$ and $D$ can also coincide.

How Do We Know If a Cipher Is Secure?

Before diving into the different kinds of ciphers, we should understand how to evaluate them, that is, what security requirements the ciphers must meet.

Here's the first thing that might surprise you:

An ideal attacker has complete knowledge of the cryptosystem in use.

This means that the attacker can access the plaintext, ciphertext and key space, and call the functions $E$ and $D$ as many times as he/she wants. Therefore, contrary to what some may think, hiding these elements cannot be considered a security requirement.
We will understand the importance of this assumption later on, and the reason why we can safely make it lies in Kerckhoff's second principle for a good cipher:

A cipher must be secure even if the cryptosystem is known to the enemy.

This means that the only thing that the attacker doesn't know is the specific plaintext the sender is communicating during a particular communication, or the specific keys in use. The main features a cipher can offer are the following (and depending on what you're building, some of these will matter more than others):

• Confidentiality: The plaintext cannot be derived from the ciphertext without having the decryption key;

• Integrity: The information transmitted cannot be tampered with along the channel;

• Authenticity: The identity of the sender is guaranteed to the receiver.

Now that we've covered a high-level overview of ciphers, it's time to dive into how they actually work. We'll start with the most intuitive category: symmetric ciphers.