Foundations of Information Security: Entropy, Uncertainty, and Computational Hardness

At the heart of modern cryptography lies a fundamental question: how can we mathematically formalize and achieve security in the presence of adversarial entities? This chapter lays the rigorous groundwork by transitioning from the ideal but often impractical world of information-theoretic security to the computationally bounded reality that defines modern systems. We begin with Claude Shannon's foundational work on entropy and uncertainty, which provides the language to quantify secrecy. We then explore the pinnacle of information-theoretic security—perfect secrecy—exemplified by the one-time pad, and understand its inherent limitations that necessitate a shift in paradigm. This shift leads us to computational security, where security is based on the assumed difficulty of certain mathematical problems. To formalize this, we introduce core concepts from complexity theory—P, NP, BPP—and the pivotal notion of a one-way function. We survey the fundamental hardness assumptions that underpin contemporary cryptography: integer factorization, the discrete logarithm problem, and the family of lattice problems, which are central to post-quantum cryptography. Finally, we model the adversary not as an omnipotent entity but as an algorithm interacting with a system through a structured security game, defining the crucial hierarchies of KPA, CPA, and CCA security. This chapter establishes the precise definitions and mental models that will be used to construct and analyze every cipher and protocol discussed in the subsequent chapters.

1.1 Information-Theoretic Security: Quantifying Secrecy with Entropy

Before we can build secure systems, we must define what "secrecy" or "uncertainty" means in a mathematical sense. Claude Shannon's 1948 seminal paper, "A Mathematical Theory of Communication," provided the tools. The central concept is entropy, which quantifies the uncertainty or randomness of a random variable.

1.1.1 Shannon Entropy: The Average Uncertainty

For a discrete random variable $X$ taking values in an alphabet $\mathcal{X}$ with probability mass function $p(x) = \Pr[X=x]$, the Shannon entropy is defined as:

$$ H(X) = -\sum_{x \in \mathcal{X}} p(x) \log_2 p(x) $$

The unit is the bit when using log base 2. Entropy can be interpreted as the expected value of the self-information $I(x) = -\log_2 p(x)$, which measures the "surprise" or information content of observing an outcome $x$: rarer events carry more information.

Example 1.1 (Entropy of a Fair vs. Biased Coin). Consider a coin toss.

• **Fair coin**: $p(H)=p(T)=0.5$. Then $H(X) = -[0.5 \log_2 0.5 + 0.5 \log_2 0.5] = -[0.5 \times (-1) + 0.5 \times (-1)] = 1$ bit. Maximum uncertainty for two outcomes.
• **Biased coin**: $p(H)=0.9, p(T)=0.1$. Then $H(X) = -[0.9 \log_2 0.9 + 0.1 \log_2 0.1] \approx -[0.9 \times (-0.152) + 0.1 \times (-3.322)] \approx 0.469$ bits. We are more certain of the outcome (heads), so the uncertainty is lower.

Entropy reaches its maximum, $\log_2 |\mathcal{X}|$, when the distribution is uniform. This concept is directly applicable to cryptographic keys: a key space of size $2^{128}$ with a uniform distribution has 128 bits of entropy, meaning an adversary must, on average, perform $2^{127}$ guesses to find the key by brute force.

1.1.2 Conditional Entropy and Joint Entropy

Often, we care about the uncertainty of one variable given knowledge of another. The conditional entropy $H(Y|X)$ measures the average uncertainty remaining about $Y$ after $X$ is known:

$$ H(Y|X) = \sum_{x \in \mathcal{X}} p(x) H(Y|X=x) = H(X,Y) - H(X) $$

where $H(X,Y)$ is the joint entropy. If $X$ and $Y$ are independent, $H(Y|X) = H(Y)$. If $X$ completely determines $Y$, then $H(Y|X)=0$.

In cryptography, consider a plaintext message $M$ and its corresponding ciphertext $C$ under a fixed key $K$. The conditional entropy $H(M|C)$ measures the adversary's uncertainty about the original message after seeing the ciphertext. A perfectly secure cipher aims to make $H(M|C) = H(M)$, meaning the ciphertext reveals no information about the plaintext.

Example 1.2 (Conditional Entropy in a Simple Cipher). Suppose a substitution cipher where each letter is mapped to another. If the ciphertext is "KHOOR", an adversary with knowledge of English statistics can make educated guesses. $H(M|C)$ is low because the structure of English (letter frequencies, common words) leaks through. In contrast, for a one-time pad, as we will see, $H(M|C) = H(M)$ regardless of the adversary's computational power.

1.1.3 The Limits of Information-Theoretic Security

Shannon's framework is powerful because it is unconditional: security holds even against an adversary with infinite computational resources. However, this strength comes at a steep price. Shannon proved a fundamental result: for any perfectly secret encryption scheme, the key must be at least as long as the message. This is the Shannon's theorem on perfect secrecy:

> In a perfectly secret cryptosystem, $|K| \ge |M|$, where $|K|$ is the size of the key space and $|M|$ is the size of the message space.

The proof is elegant. If $|K| < |M|$, then by the pigeonhole principle, some ciphertext $c$ can be produced by encrypting at most $|K|$ different messages. Since each key is equally likely, the a posteriori probability $\Pr[M=m | C=c]$ cannot equal the a priori $\Pr[M=m]$ for all $m$, violating perfect secrecy.

The one-time pad (OTP), invented by Gilbert Vernam and Joseph Mauborgne, achieves this bound. Encryption: $C = M \oplus K$, where $K$ is a uniformly random key of the same length as $M$, and $\oplus$ is bitwise XOR. Decryption: $M = C \oplus K$. OTP is perfectly secret because for any fixed ciphertext $c$, every possible plaintext $m$ is equally likely: $\Pr[M=m | C=c] = \Pr[K = m \oplus c] = 2^{-n}$ (if keys are uniform and independent). Thus, $H(M|C) = H(M)$.

Practical Implication: OTP's requirement for a truly random, secret key as long as the message, and the need for secure key distribution and synchronization, makes it impractical for most applications (e.g., encrypting a gigabyte file requires a gigabyte of pre-shared random key). This impossibility result forces us to seek a different notion of security—one that is computational, not information-theoretic.

1.2 The Computational Turn: Security Against Bounded Adversaries

The central insight of modern cryptography is to relax the requirement of perfect secrecy. Instead of demanding that an adversary gains *zero* information, we require that any information gained cannot be *efficiently* exploited. This is computational security.

1.2.1 From Perfect Secrecy to Computational Indistinguishability

We replace the information-theoretic condition $H(M|C) = H(M)$ with a computational one: the ciphertext should be computationally indistinguishable from a random string to any efficient adversary.

Definition 1.1 (Computational Indistinguishability). Two probability distributions $D_0$ and $D_1$ over a set $\mathcal{S}$ are $(t, \epsilon)$-indistinguishable if for every algorithm $\mathcal{A}$ running in time at most $t$, $$ |\Pr[\mathcal{A}(x) = 1 \text{ for } x \sim D_0] - \Pr[\mathcal{A}(x) = 1 \text{ for } x \sim D_1]| \le \epsilon $$ If this holds for all polynomial-time algorithms (i.e., $t$ is any polynomial in the security parameter) and $\epsilon$ is negligible (smaller than any inverse polynomial), we say $D_0$ and $D_1$ are computationally indistinguishable.

Applied to encryption: the distribution of ciphertexts of two different messages should be computationally indistinguishable. More formally, for any two messages $m_0, m_1$, the distributions $\{ \mathsf{Enc}_k(m_0) \}$ and $\{ \mathsf{Enc}_k(m_1) \}$ (over random key $k$) are indistinguishable. This is the core of semantic security under a chosen-plaintext attack (CPA), which we will formalize later.

Example 1.3 (Pseudorandomness). A classic example is