Classical Cryptography and Perfect Secrecy

Corresponds to Katz & Lindell, Introduction to Modern Cryptography, Chapters 1–2.

Motivation: from an art to a science

IntuitionWhat changed

Until late in the 20th century, cryptography meant secret communication, mostly for militaries, and good codes came from creativity rather than theory: there was no agreed notion of what a “good” code even was. Modern cryptography is the scientific study of securing digital information, transactions and distributed computations against internal or external attack. It covers authentication, signatures, key exchange, auctions, elections and digital cash, and it is used by everyone, usually without knowing it. The classical ciphers below are studied not as history but as cautionary examples that motivate definitions and proofs.

Era	Approach	Typical outcome
Classical	ad hoc design, security by intuition	broken, sometimes centuries later
Shannon (1949)	definitions + proofs, no assumptions	perfect secrecy, but keys as long as messages
Modern (Goldwasser–Micali, 1980s)	definitions + precise assumptions + proofs	practical schemes with computational security

The private-key setting

DefinitionPrivate-key (symmetric) encryption scheme

Two parties share a secret key in advance and communicate over a public channel. A scheme consists of three algorithms and a message space $\mathcal M$ :

Gen (probabilistic) outputs a key $k$ from the key space $\mathcal K$ ;
Enc takes $k$ and a plaintext $m$ , outputs a ciphertext $c = \mathrm{Enc}_k(m)$ ;
Dec takes $k$ and $c$ , outputs a plaintext $\mathrm{Dec}_k(c)$ .

$\mathcal K$ and $\mathcal M$ determine the ciphertext space $\mathcal C$ . Correctness: $\mathrm{Dec}_k(\mathrm{Enc}_k(m)) = m$ for every key output by Gen and every $m\in\mathcal M$ .

Component	Detail
Symmetric	the same key encrypts and decrypts (contrast public-key, Chapter 9)
Hidden assumption	the parties somehow shared the key secretly beforehand
Where it suffices	disk encryption (one user, two points in time), and alongside public-key methods

ImportantKerckhoffs’ principle

A cipher must stay secure even if everything except the key falls into the enemy’s hands. Security rests on the key alone. Today this is read more strongly: algorithms should be published. Reasons:

a short random key is far easier to keep secret than a program, which can leak or be reverse engineered;
a compromised key is easy to replace; a compromised algorithm isn’t, and many pairs of users can share one algorithm with different keys;
public scrutiny makes designs stronger, flaws are better found by ethical hackers than by attackers, and public designs enable standards.

Corollary: never use proprietary, secretly designed algorithms (“security by obscurity”). Kerckhoffs also asked that a system be practically, if not mathematically, indecipherable, which is exactly modern computational security.

DefinitionAttack models (increasing severity)

Attack	Adversary can	Type
Ciphertext-only	observe ciphertexts	passive
Known-plaintext	also see some plaintext–ciphertext pairs under the same key	passive
Chosen-plaintext	obtain encryptions of plaintexts of its choice	active
Chosen-ciphertext	also obtain decryptions of ciphertexts of its choice (other than the target)	active

Known-plaintext attacks are very realistic: greetings, standard headers, or earnings figures that are later published all leak plaintext. The strongest model is not always required; a scheme secure against weaker attacks may be more efficient and enough for the application.

Historical ciphers and their cryptanalysis

NoteConventions for this section

Plaintext is lower case, ciphertext UPPER CASE, letters are identified with $\{0,\ldots,25\}$ , and $[a\bmod N]$ is the remainder. Every attack assumes Kerckhoffs: the scheme is known, the key is not.

Caesar and the shift cipher

ExampleCaesar’s cipher

Rotate every letter by 3 ( $a\to D$ , wrapping $x\to A$ ). “begintheattacknow” becomes EHJLQWKHDWWDFNQRZ. There is no key: Gen does nothing, so knowing the method means decrypting everything. ROT-13 is the shift-13 variant used to hide spoilers, with no pretence of security.

DefinitionShift cipher

Gen picks $k$ uniformly from $\{0,\ldots,25\}$ ; $\mathrm{Enc}_k(m)_i = [(m_i + k)\bmod26]$ and $\mathrm{Dec}_k(c)_i = [(c_i - k)\bmod26]$ .

ExampleBreaking it by brute force

Only 26 keys: try them all. The book’s challenge ciphertext OVDTHUFWVZZPISLRLFZHYLAOLYL decrypts with $k = 7$ to “how many possible keys are there”. (Worked here.)

ImportantSufficient key space principle

A secure scheme’s key space must resist exhaustive search (today at least about $2^{60}$ – $2^{70}$ keys). This is necessary but not sufficient. It also only applies when the message space is larger than the key space: the one-time pad below is secure with $\lvert\mathcal K\rvert = \lvert\mathcal M\rvert$ .

Mono-alphabetic substitution

DefinitionSubstitution cipher

The key is a permutation of the alphabet, applied letter by letter: $26!\approx2^{88}$ keys, far beyond brute force.

WarningLarge key space, still trivially broken

Two facts kill it:

the mapping is fixed, so each plaintext letter always becomes the same ciphertext letter;
letter frequencies of a language are stable, even over a few dozen words.

Tabulate ciphertext letter frequencies, match them to English (most frequent → e, and so on), then fix mistakes with language knowledge (h between t and e; q followed by u). Newspaper cryptograms are this cipher.

AlgorithmAutomated attack on the shift cipher

Let $p_i$ be English letter frequencies, so $\sum_ip_i^2\approx0.065$ (1.1), and let $q_i$ be the ciphertext frequencies. If the key is $k$ , then $q_{i+k}\approx p_i$ . Compute

$I_j = \sum_{i=0}^{25}p_iq_{i+j}\quad\text{for }j = 0,\ldots,25$

and output the $j$ whose $I_j$ is closest to $0.065$ . This needs no judgement of whether a decryption “makes sense”, so it automates easily and works even for text that has English statistics without being English.

The Vigenère cipher

DefinitionVigenère (poly-alphabetic shift)

The key is a word $k_1\cdots k_t$ (the period $t$ ). Plaintext position $i$ is shifted by key letter $k_{((i-1)\bmod t)+1}$ , cycling through the key. Equivalently, $t$ interleaved shift ciphers. Example: “tellhimaboutme” with key “cafe” gives WFRQKJSFEPAYPF.

Why it seemed strong: the same plaintext letter maps to different ciphertext letters, which smooths the frequency distribution. It was invented in the 16th century and long considered unbreakable.

AlgorithmBreaking Vigenère once the period is known

Split the ciphertext into $t$ streams $c_j, c_{j+t}, c_{j+2t}, \ldots$ . Each is a shift cipher with key $k_j$ . Break each stream with frequency matching or the $I_j$ statistic. This needs $t$ frequency tables, not a search over $26^t$ keys.

AlgorithmFinding the period

Kasiski (mid-19th century): look for repeated 2–3 letter blocks in the ciphertext. Common words like “the” encrypt identically whenever they fall at the same offset modulo $t$ , so distances between repeats are (mostly) multiples of $t$ . Take the gcd. (Book example: with key “beads”, two occurrences of “the” both become MJJ, 40 positions apart, and $t = 5$ .)

Index of coincidence: for $\tau = 1, 2, \ldots$ , compute $I_\tau = \sum_iq_i^2$ over the stream $c_1, c_{1+\tau}, c_{1+2\tau}, \ldots$ . At $\tau = t$ the stream is a shifted English distribution, so $I_\tau\approx0.065$ . Otherwise letters look roughly uniform and $I_\tau\approx\sum_i(1/26)^2\approx0.038$ . This is easy to automate.

IntuitionLonger keys need longer ciphertexts

The shift cipher falls to a single word, substitution needs a paragraph, and Vigenère needs about $t$ times more (each of $t$ streams needs its own statistics, and Kasiski needs repeats). This is not a coincidence: it previews perfect secrecy, where a key as long as the message leaves no statistics to exploit.

TheoremAll three fall immediately to known- or chosen-plaintext attacks (Exercises 1.5–1.6)

Cipher	Known plaintext needed	Chosen plaintext needed
Shift	1 letter: $k = c_1 - m_1$	encrypt “a”
Substitution	text covering 25 distinct letters (the 26th is forced)	encrypt “abc…y” (25 letters)
Vigenère	$t$ consecutive letters, $k_i = c_i - m_i$ (if $t$ unknown, read it off a long enough sample)	encrypt “aaa…a”: the ciphertext is the key repeated, revealing $t$ and $k$

(Worked here.) Chosen plaintext is no more powerful here but makes the attack trivial to plan, since the adversary designs the plaintext.

ExampleHardened variants (Exercises 1.3–1.4)

Vigenère with $t$ substitution alphabets: split into $t$ streams (period via index of coincidence, which is invariant under substitution), then break each stream with frequency analysis.
Block-dependent shifts $k_i + j$ in block $j$ : decryption just subtracts $k_i + j$ . Kasiski weakens: identical plaintext now repeats identically only when the block distance is a multiple of 26, so the effective period is $26t$ . Better attack: by Kerckhoffs the structure is known, so subtract $j$ from every letter of block $j$ (for a guessed $t$ ) to recover ordinary Vigenère ciphertext, then attack as usual.

(Worked here.)

ImportantLessons from classical ciphers

Sufficient key space is necessary, never sufficient.
Complexity is not security. Vigenère, Enigma and others were complex and all broke. Designing ciphers is hard and should be left to experts with definitions and proofs.

The three principles of modern cryptography

DefinitionThe principles

Exact definitions: formulate a rigorous definition of security before anything else.
Precise assumptions: if security relies on an unproven assumption, state it precisely and keep it minimal.
Rigorous proofs: prove the construction meets the definition, relative to the stated assumption.

Principle 1: exact definitions

NoteWhy definitions come first

Design: without a target you can’t tell when you’ve hit it, and post hoc definitions risk stopping when patience runs out or overbuilding.
Usage: match the guarantee a scheme provides to what the application needs (the strongest scheme may be needlessly slow).
Study: compare schemes on security, not just efficiency.

ExampleFive attempts to define secure encryption

Attempt	Secure if no adversary can…	Flaw
1	find the key	Enc that outputs the plaintext is “secure”
2	find the plaintext	leaking 90% (say, all but the salary in a contract) passes
3	find any character of the plaintext	learning “salary > $100,000” passes
4	derive meaningful information	”meaningful” depends on the application
5	compute any function of the plaintext	the right idea, once formalised (Chapters 2–3)

The general principle: definitions should cover all possible applications, because libraries get reused in unforeseen ways. And it is hard to turn intuition into a correct definition: if the definition isn’t what you meant, a “proven secure” scheme may protect nothing.

DefinitionAnatomy of a security definition

A scheme is secure if no adversary of a specified power can achieve a specified break.

Break: what the adversary must achieve (here: learn any function of the plaintext).
Power: what it can do (the attack model) and how much computation it has (unbounded in Chapter 2; polynomial time elsewhere in the book).
Arbitrary adversary principle: assume things about the adversary’s abilities, never its strategy. Predicting attack strategies has always failed.

WarningModels versus reality

A definition is a mathematical model of a real need. A scheme proven secure may still leak its key through a smart card’s power consumption: the proof is fine, the model omitted side channels. The fix is to refine the definition or harden the hardware. Even a mis-specified definition tells you where you stand; without one you can’t even say what went wrong. Turing faced the same issue for computability and justified his model by intuition, equivalence of definitions, and examples. Cryptographic definitions are validated the same way, plus the test of time.

Principle 2: precise assumptions

NoteWhy state assumptions precisely

Most constructions can’t be proven secure unconditionally (that would resolve open complexity questions). So assumptions must be:

validated: only a precisely stated assumption can be studied and possibly refuted, and confidence grows as it survives scrutiny;
comparable: prefer the scheme resting on the weaker (or better-studied) assumption;
usable in proofs: “secure if X holds” needs X stated exactly.

Assuming the scheme itself is secure is technically precise but frowned upon. Simple, low-level assumptions (a mathematical problem is hard) are easier to study and can be shared across many constructions and swapped out if one instantiation fails. The book’s arc: build encryption and MACs from pseudorandom functions (Chapters 3–4), build PRFs in practice (Chapter 5), then from lower-level primitives (Chapter 6).

Principle 3: rigorous proofs

ImportantWhy proofs are essential here

Security can’t be tested like functionality: garbled-looking ciphertext proves nothing. Intuition in security has a long record of failure, the stakes are high, and unlike ordinary users, attackers actively hunt for the exact failure modes. Reductionist proofs: to show “if assumption X holds, construction Y is secure”, show how any adversary breaking Y can be used as a subroutine to break X.

Perfect secrecy

NoteSetting and conventions

Gen induces a distribution on keys $K$ , the sender’s message is a random $M$ (modelling the adversary’s prior), and $K$ and $M$ are independent (the key is fixed before the message is known). These determine the distribution of the ciphertext $C$ . Enc may be randomised; correctness is exact, so Dec can be taken deterministic. Convention for the chapter: every message and ciphertext has positive probability, so conditioning is always defined (Exercise 2.6 removes this). The adversary is computationally unbounded.

DefinitionPerfect secrecy (Def. 2.1)

$(\mathrm{Gen},\mathrm{Enc},\mathrm{Dec})$ over $\mathcal M$ is perfectly secret if for every distribution on $\mathcal M$ , every $m$ and every $c$ with $\Pr[C = c] > 0$ ,

$\Pr[M = m\mid C = c] = \Pr[M = m]$

Seeing the ciphertext doesn’t change the adversary’s beliefs: $M$ and $C$ are independent. In information-theoretic terms, $I(M;C) = 0$ (mutual information).

LemmaLemma 2.2 — Ciphertext distribution ignores the message

Perfectly secret ⟺ for every distribution on $\mathcal M$ , every $m$ , $c$ :

$\Pr[C = c\mid M = m] = \Pr[C = c]$

ProofBayes’ rule, both directions

(⇐) Multiply by $\Pr[M = m]/\Pr[C = c]$ ; by Bayes, the left side is $\Pr[M = m\mid C = c]$ . (⇒, Exercise 2.1) Reverse the same steps: $\Pr[C = c\mid M = m] = \Pr[M = m\mid C = c]\Pr[C = c]/\Pr[M = m] = \Pr[C = c]$ . Positivity of all probabilities is what licenses the divisions.

∎

LemmaLemma 2.3 — Perfect indistinguishability

Perfectly secret ⟺ for every $m_0, m_1$ and $c$ : $\Pr[C = c\mid M = m_0] = \Pr[C = c\mid M = m_1]$ . The ciphertext distribution $\mathcal C(m)$ is the same for every message.

ProofConstant conditional ⇒ equals the marginal

(⇒) Both sides equal $\Pr[C = c]$ by Lemma 2.2. (⇐) If $\Pr[C = c\mid M = m] = \gamma$ for all $m$ , total probability gives $\Pr[C = c] = \sum_m\gamma\Pr[M = m] = \gamma$ , so Lemma 2.2 applies.

∎

DefinitionAdversarial indistinguishability experiment $\mathrm{PrivK}^{\mathrm{eav}}_{\mathcal A,\Pi}$

$\mathcal A$ outputs $m_0, m_1\in\mathcal M$ .
$k\leftarrow\mathrm{Gen}$ , $b\leftarrow\{0,1\}$ uniform, $c\leftarrow\mathrm{Enc}_k(m_b)$ given to $\mathcal A$ .
$\mathcal A$ outputs $b'$ ; the experiment outputs 1 (success) iff $b' = b$ .

Definition 2.4: $\Pi$ is perfectly secret iff $\Pr[\mathrm{PrivK}^{\mathrm{eav}}_{\mathcal A,\Pi} = 1] = \frac12$ for every $\mathcal A$ , with no limit on its computation. Random guessing already achieves $\frac12$ ; the requirement is that nothing does better.

TheoremProposition 2.5 — The definitions agree

Definitions 2.1 and 2.4 are equivalent.

ProofBoth directions (Exercises 2.7–2.8)

(2.1 ⇒ 2.4) Perfect secrecy holds for the uniform distribution on $\{m_0,m_1\}$ (Exercise 2.6), so by Lemma 2.3 $c$ has the same law whatever $b$ is. Then $c$ is independent of $b$ , and no function of $c$ guesses $b$ with probability other than $\frac12$ .

(2.4 ⇒ 2.1) If not perfectly secret, Lemma 2.3 gives $m_0, m_1, c^*$ with $\Pr[C = c^*\mid m_0]\ne\Pr[C = c^*\mid m_1]$ . The adversary outputs $(m_0,m_1)$ and guesses the $b$ maximising $\Pr[C = c\mid M = m_b]$ (maximum likelihood). Its success probability is $\frac12\sum_c\max_b\Pr[C = c\mid m_b] > \frac12$ , since the max exceeds the average at $c^*$ . (Sketch worked here.)

∎

The one-time pad (Vernam’s cipher)

DefinitionOne-time pad

$\mathcal M = \mathcal K = \mathcal C = \{0,1\}^\ell$ ; Gen picks $k$ uniformly; $\mathrm{Enc}_k(m) = k\oplus m$ ; $\mathrm{Dec}_k(c) = k\oplus c$ . Correctness: $k\oplus k\oplus m = m$ . Patented by Vernam (1917); proven perfectly secret by Shannon about 25 years later.

TheoremTheorem 2.6 — The one-time pad is perfectly secret

ProofEvery ciphertext is equally likely under every message

For any $m$ , $c$ : $\Pr[C = c\mid M = m] = \Pr[m\oplus K = c] = \Pr[K = m\oplus c] = 2^{-\ell}$ , since $K$ is uniform and independent of $M$ . This doesn’t depend on $m$ , so by Bayes,

$\Pr[M = m_0\mid C = c] = \frac{2^{-\ell}\Pr[M = m_0]}{\sum_m2^{-\ell}\Pr[M = m]} = \Pr[M = m_0]$

Intuition: for any $c$ , every $m$ has exactly one key $k = m\oplus c$ producing it, and every key is equally likely.

∎

WarningDrawbacks

Key as long as the message, and an upper bound on message length must be known in advance.
One use only. With $c = m\oplus k$ , $c' = m'\oplus k$ : $c\oplus c' = m\oplus m'$ . That already breaks perfect secrecy for two messages, and with enough English message pairs, frequency analysis recovers the messages.
Known-plaintext attack: one pair $(m,c)$ gives $k = c\oplus m$ , decrypting everything else under that key.

Rumour has it that the Cold War Washington–Moscow hotline used a one-time pad: governments can afford to courier long keys. Commercial settings can’t.

ExampleExcluding the all-zero key doesn’t help (Exercise 2.3)

Drawing $k$ uniformly from $\{0,1\}^\ell\setminus\{0^\ell\}$ is not perfectly secret: now $\lvert\mathcal K\rvert < \lvert\mathcal M\rvert$ , so Theorem 2.7 applies. Concretely, $c = m$ is now impossible, so seeing $c$ rules out $m = c$ . The resolution of the paradox: $k = 0^\ell$ sends $m$ in the clear, but the adversary doesn’t know which key was used, so the ciphertext $m$ is indistinguishable from any other. Security is a property of the key distribution, not of individual keys. (Worked here.)

Limitations of perfect secrecy

TheoremTheorem 2.7 — Keys must be at least as numerous as messages

Any perfectly secret scheme has $\lvert\mathcal K\rvert\ge\lvert\mathcal M\rvert$ . For fixed-length keys and messages: the key is at least as long as the message.

ProofA ciphertext can only decrypt to

\lvert\mathcal K\rvert

messages

Suppose $\lvert\mathcal K\rvert < \lvert\mathcal M\rvert$ . Take the uniform distribution on $\mathcal M$ and any $c$ that is a possible encryption. Let $\mathcal M(c) = \{\mathrm{Dec}_{\hat k}(c) : \hat k\in\mathcal K\}$ ; since Dec is deterministic, $\lvert\mathcal M(c)\rvert\le\lvert\mathcal K\rvert < \lvert\mathcal M\rvert$ . So some $m'\notin\mathcal M(c)$ has $\Pr[M = m'\mid C = c] = 0\ne\Pr[M = m']$ .

∎

Warning“One-time-pad security with short keys”

Anyone claiming an unbreakable scheme with OTP-level security and short keys either misunderstands cryptography or is lying. Theorem 2.7 makes it impossible. (The other limitations, such as single use, are inherent too: Exercise 2.9.)

IntuitionEntropy version

The information-theoretic form of the same fact is $H(K)\ge H(M)$ for perfect secrecy: the key must carry at least as much uncertainty as the message it hides (Shannon 1949; compare mutual information).

Shannon’s theorem

TheoremTheorem 2.8 — Shannon’s characterisation

Suppose $\lvert\mathcal M\rvert = \lvert\mathcal K\rvert = \lvert\mathcal C\rvert$ (the most economical case: $\lvert\mathcal K\rvert\ge\lvert\mathcal M\rvert$ by Theorem 2.7, and $\lvert\mathcal C\rvert\ge\lvert\mathcal M\rvert$ by decryptability). The scheme is perfectly secret iff

every key is chosen with probability $1/\lvert\mathcal K\rvert$ ; and
for every $m$ and $c$ there is exactly one key $k$ with $\mathrm{Enc}_k(m) = c$ .

ProofCounting forces uniqueness, Bayes forces uniformity (deterministic Enc)

(⇒) Uniqueness. Every $(m,c)$ needs at least one key, or $\Pr[M = m\mid C = c] = 0$ . So for fixed $m$ , $\{\mathrm{Enc}_k(m)\}_k$ covers all of $\mathcal C$ . Its size is at most $\lvert\mathcal K\rvert = \lvert\mathcal C\rvert$ , so $k\mapsto\mathrm{Enc}_k(m)$ is a bijection: exactly one key per $(m,c)$ .

(⇒) Uniform keys. Fix $c$ and label keys $k_i$ so that $\mathrm{Enc}_{k_i}(m_i) = c$ (distinct by uniqueness). Perfect secrecy and Bayes give $\Pr[M = m_i] = \Pr[K = k_i]\Pr[M = m_i]/\Pr[C = c]$ , so $\Pr[K = k_i] = \Pr[C = c]$ for all $i$ : all keys are equally likely.

(⇐) Each $(m,c)$ has a single key of probability $1/\lvert\mathcal K\rvert$ , so $\Pr[C = c\mid M = m] = 1/\lvert\mathcal K\rvert$ for all $m$ . Lemma 2.3 finishes.

∎

ImportantUses of Shannon’s theorem

Complete characterisation in the economical case: perfect secrecy is the one-time pad’s structure (a Latin-square key table with uniform keys).
Distribution-free: conditions 1–2 don’t mention the message distribution, so perfect secrecy for one distribution implies it for all.
Easy checking: verify uniform keys and a unique key per pair, with no probability calculations. Theorem 2.6 is immediate.
Only when $\lvert\mathcal M\rvert = \lvert\mathcal K\rvert = \lvert\mathcal C\rvert$ .

ExampleClassical ciphers that are perfectly secret (Exercise 2.4)

Shift cipher on a single letter: $\lvert\mathcal M\rvert = \lvert\mathcal K\rvert = \lvert\mathcal C\rvert = 26$ , uniform keys, and $k = c - m$ is the unique key. Shannon applies.
Substitution: perfectly secret for messages of a fixed length $n\le26$ with all distinct letters. A uniform permutation sends any such message to a uniform distinct-letter string of length $n$ . The largest such space is all $26!$ orderings of the alphabet ( $n = 26$ ). Repeated letters leak the pattern of equalities, and different lengths leak length.
Vigenère: use a uniformly random key as long as the word. Each letter is then an independent single-letter shift, which is a one-time pad mod 26.

Reconciliation with Chapter 1: those attacks needed the key to be reused across many letters (fixed mapping, short period). Perfect secrecy holds exactly when there is no reuse. (Worked here.)

Further exercises

ExampleShort answers

2.2 (posteriors all equal?) False. Perfect secrecy gives $\Pr[M = m\mid C = c] = \Pr[M = m]$ , which differs across $m$ under a non-uniform prior.
2.5 (uniform key and $\lvert\mathcal K\rvert = \lvert\mathcal M\rvert$ suffice?) False. $\mathrm{Enc}_k(m) = m$ has both properties and is correct, but leaks everything. Shannon’s condition 2 is what matters.
2.9 (two-message perfect secrecy is impossible) Under one key, deterministic decryption forces $c = c'\Rightarrow m = m'$ . Conditioning on $c = c'$ makes $\Pr[M = m, M' = m'\mid\cdot] = 0$ for $m\ne m'$ , which differs from the prior under any distribution with two messages of positive probability.
2.10 (secrecy given distinct messages) Achievable by a uniformly random permutation of $\mathcal M$ as the key: any two distinct messages map to a uniform pair of distinct ciphertexts. The key is about $\log_2(\lvert\mathcal M\rvert!)\approx\lvert\mathcal M\rvert\log_2\lvert\mathcal M\rvert$ bits, exponentially longer than a message.
2.11 (allowing decryption error $\le1-2^{-t}$ ) Encrypt by ignoring $m$ and outputting nothing (or random bits); decrypt by guessing uniformly. Perfectly secret with $\lvert\mathcal K\rvert = 1$ , and correct with probability $1/\lvert\mathcal M\rvert\ge2^{-t}$ whenever $\lvert\mathcal M\rvert\le2^t$ .

(Answers worked here.)

TheoremAlmost-perfect secrecy (Exercise 2.12)

Take uniform $M$ and a possible ciphertext $c$ , and let $\mathcal M(c)$ be its decryptions under all keys, so $\lvert\mathcal K\rvert\ge\lvert\mathcal M(c)\rvert$ .

Pointwise version (as stated: $\lvert\Pr[M = m\mid c] - \Pr[M = m]\rvert < \varepsilon$ for all $m$ ): the posterior sums to 1 over $\mathcal M(c)$ with each term below $1/\lvert\mathcal M\rvert + \varepsilon$ , so $\lvert\mathcal K\rvert > \frac{\lvert\mathcal M\rvert}{1 + \varepsilon\lvert\mathcal M\rvert}$ . This is weak: about $1/\varepsilon$ for large message spaces.
Statistical-distance version ( $\frac12\sum_m\lvert\Pr[M = m\mid c] - \Pr[M = m]\rvert\le\varepsilon$ ): each excluded message contributes its full $1/\lvert\mathcal M\rvert$ , so at most $2\varepsilon\lvert\mathcal M\rvert$ messages are excluded and $\lvert\mathcal K\rvert\ge(1 - 2\varepsilon)\lvert\mathcal M\rvert$ . This is the hint’s ” $(1-\varepsilon)$ fraction” bound, up to the factor of 2.

Either way, near-perfect secrecy still demands keys of essentially message length. Breaking this barrier needs computational security.

Quick reference

Object	Statement	Note
Scheme	$(\mathrm{Gen},\mathrm{Enc},\mathrm{Dec})$ , $\mathrm{Dec}_k(\mathrm{Enc}_k(m)) = m$	private key
Kerckhoffs	only the key is secret; publish algorithms	no security by obscurity
Attacks	ciphertext-only < known-plaintext < chosen-plaintext < chosen-ciphertext
Shift	26 keys; brute force
Substitution	$26!\approx2^{88}$ keys; frequency analysis	large key space ≠ security
Shift statistic	$I_j = \sum p_iq_{i+j}\approx0.065$ at the key
Vigenère	$t$ interleaved shifts	Kasiski gcd; IC $0.065$ vs $0.038$
Principles	definitions, precise minimal assumptions, proofs
Definition form	no adversary of given power achieves given break	arbitrary-adversary principle
Encryption break	computing any function of the plaintext
Perfect secrecy	$\Pr[M = m\mid C = c] = \Pr[M = m]$	$I(M;C) = 0$
Equivalents	$\Pr[C = c\mid m]$ constant in $m$ ; $\mathrm{PrivK}^{\mathrm{eav}}$ success $=\frac12$	unbounded adversary
One-time pad	$c = k\oplus m$ , $k$ uniform	perfectly secret
OTP failure modes	reuse leaks $m\oplus m'$ ; known plaintext gives $k$
Key bound	$\lvert\mathcal K\rvert\ge\lvert\mathcal M\rvert$	$H(K)\ge H(M)$
Shannon	uniform keys + unique key per $(m,c)$	when $\lvert\mathcal M\rvert = \lvert\mathcal K\rvert = \lvert\mathcal C\rvert$

Facts to keep to hand

Classical ciphers fail for structural reasons. A fixed mapping or a reused short key preserves the statistics of language, so frequency analysis, Kasiski and the index of coincidence break them, and any known or chosen plaintext breaks them instantly. A huge key space is necessary but never sufficient.
Modern cryptography is definitions, assumptions and proofs. Say exactly what a break is and what the adversary can do (but never how it will attack), rest on minimal well-studied assumptions, and prove security by reduction.
Perfect secrecy means the ciphertext is independent of the message. Equivalently, every message induces the same ciphertext distribution, and no adversary, however powerful, beats a coin flip at telling two messages apart.
Perfect secrecy costs a key as long as the message. The one-time pad achieves it, Shannon’s theorem says it is essentially the only way, and the key-length bound (plus single use) is why the rest of the book relaxes to computational security.

References

Katz & Lindell, Introduction to Modern Cryptography — Chapters 1–2
Shannon, “Communication Theory of Secrecy Systems” (1949)
Kahn, The Codebreakers — history of classical ciphers

Related