Private-Key Encryption and Pseudorandomness

Corresponds to Katz & Lindell, Introduction to Modern Cryptography, Chapter 3.

Motivation: beating the one-time pad’s key bound

IntuitionGive up a little, gain everything

Perfect secrecy forces the key to be as long as all messages ever sent with it. Modern schemes are breakable in principle, but breaking them would take more than many lifetimes on the fastest computers. That is exactly Kerckhoffs’ other principle: practically, if not mathematically, indecipherable. We keep definitions and proofs, but weaken the definitions in two ways:

security only against efficient adversaries;
adversaries may succeed with some very small probability.

This currently requires assumptions: an unconditional proof that any scheme with messages longer than keys is secure would imply P ≠ NP.

The computational approach

Concrete versus asymptotic security

DefinitionConcrete security

A scheme is $(t,\varepsilon)$ -secure if every adversary running for time at most $t$ breaks it with probability at most $\varepsilon$ (for example, $t = 2^{80}$ cycles, $\varepsilon = 2^{-64}$ ).

ExampleHow big is big (Example 3.1)

Good private-key schemes with $n$ -bit keys are believed to be essentially optimal: success about $t/2^n$ for time $t$ (brute force achieves this).

$2^{60}$ cycles at 1 GHz is about 35 years, barely within reach with massive parallelism.
$2^{128}/2^{60} = 2^{68}$ , a 21-digit factor. The universe is about $2^{58}$ seconds old.
An event once a century has probability about $2^{-30}$ per second; $2^{-60}$ per second is about once per 100 billion years.

WarningPitfalls of concrete claims

“No adversary running 5 years succeeds with probability above $\varepsilon$ ”: on what hardware? Does it account for Moore’s law? Generic or optimised attacks? It says nothing about 2 or 10 years. And theoretically, there is no threshold at which $(t,\varepsilon)$ means “secure”.

DefinitionAsymptotic security

Schemes take a security parameter $n$ , known to the adversary and given in unary $1^n$ so that running time is polynomial in input length. Running times and success probabilities are functions of $n$ .

Efficient = probabilistic polynomial time (ppt). Adversaries may run much longer than honest parties, but still polynomially.
Small = negligible: smaller than every inverse polynomial eventually.

A scheme is secure if every ppt adversary succeeds with only negligible probability.

ExampleAsymptotic security only bites for large $n$ (Examples 3.2–3.4)

An attack taking $n^3$ minutes with success $2^{40}\cdot2^{-n}$ is asymptotically negligible. Yet at $n = 40$ it takes about 6 weeks and succeeds with certainty; at $n = 50$ , about 3 months with success about $1/1000$ ; at $n = 500$ , about 240 years with success $2^{-460}$ .
Faster computers help defenders: honest cost $10^6n^2$ cycles, attack $10^8n^4$ cycles for success $2^{20-n}$ . At 1 GHz with $n = 50$ : honest 2.5 s, the attack about a week for $2^{-30}$ . After everyone upgrades to 16 GHz, honest parties move to $n = 100$ and still take only 0.625 s, while the same week-long attack now succeeds with only $2^{-80}$ .
Asymptotic to concrete: “time $p(n)$ ⇒ success $\le p(n)/2^n$ ” with $n = 50$ and $p(n) = n^2$ gives $(50^2, 50^2/2^{50})$ -security.

The asymptotic approach is machine-independent (the Church–Turing thesis says all reasonable devices are polynomially related), but honest parties must still pick a concrete $n$ .

ImportantBoth relaxations are necessary

If $\lvert\mathcal K\rvert < \lvert\mathcal M\rvert$ (many long messages, one short key), two attacks work against any scheme:

Brute force: decrypt with every key. A few known plaintext–ciphertext pairs pin down the key. Success about 1, time about $\lvert\mathcal K\rvert$ .
Guessing: try one random key. Polynomial time, success about $1/\lvert\mathcal K\rvert$ .

So we must bound time and forgive tiny success. Asymptotically, the key space $\mathcal K_n$ must grow super-polynomially in $n$ .

Efficient algorithms and negligible probabilities

DefinitionProbabilistic polynomial time

Runs within $p(\lvert x\rvert)$ steps for some polynomial $p$ , with access to unbiased independent coin flips (equivalently, a random tape of length $p(n)$ ).

Why polynomial: the class is closed under composition. Otherwise nothing is special: results also hold for, say, $n^{O(\log n)}$ -time adversaries.
Why probabilistic: honest parties need randomness (keys), and adversaries should be as powerful as is realistic. Whether randomness helps is open (complexity results suggest it doesn’t); security against ppt implies security against deterministic adversaries.

WarningReal randomness is hard

Sources: hardware noise or radioactive decay, timing of keystrokes, mouse movement and disk accesses. These need post-processing to become uniform. Use a cryptographic generator: C’s random() and the current time are not random enough for keys.

DefinitionNegligible function (Def. 3.5)

$f$ is negligible if for every polynomial $p$ there is $N$ with $f(n) < 1/p(n)$ for all $n > N$ . Equivalently, $f(n) < n^{-c}$ eventually, for every $c$ . Write $\mathrm{negl}$ .

ExampleNegligible functions differ wildly (Example 3.6)

$2^{-n}$ , $2^{-\sqrt n}$ and $n^{-\log n}$ are all negligible. They drop below $10^{-6}$ at $n = 20$ , $n = 400$ and $n = 32$ respectively. Yet $2^{-\sqrt n} < n^{-\log n}$ for all $n > 65536$ (where $\sqrt n = (\log n)^2$ ). Asymptotic order and practical size can disagree.

TheoremProposition 3.7 — Closure

$\mathrm{negl}_1 + \mathrm{negl}_2$ and $p(n)\cdot\mathrm{negl}(n)$ (for any polynomial $p$ ) are negligible. So a negligible-probability event stays negligible over polynomially many repetitions (union bound). Negligible-probability breaks are not breaks: you are likelier to be hit by an asteroid, or lose the key to a disk failure.

Proofs by reduction

AlgorithmTemplate of a reduction proof

Assumption: problem $X$ is hard (every ppt algorithm solves it with negligible probability). Goal: construction $\Pi$ is secure.

Fix any ppt adversary $\mathcal A$ against $\Pi$ , with success $\varepsilon(n)$ .
Build a ppt $\mathcal A'$ $A^{'}$ that, given an instance $x$ $x$ of $X$ $X$ , simulates $\Pi$ $Π$ for $\mathcal A$ $A$ :
- (a) $\mathcal A$ ‘s view is (close to) identical to a real attack;
- (b) $\mathcal A$ ‘s success lets $\mathcal A'$ solve $x$ with probability at least $\varepsilon(n)/p(n)$ .
A non-negligible $\varepsilon$ would solve $X$ non-negligibly, a contradiction.
So $\varepsilon$ is negligible.

$\mathcal A'$ uses $\mathcal A$ as a black box, with no knowledge of how it works. Every proof in the book has this form (Principle 3).

Computationally secure encryption

DefinitionPrivate-key encryption scheme (Def. 3.8)

Ppt algorithms with $k\leftarrow\mathrm{Gen}(1^n)$ (where $\lvert k\rvert\ge n$ ), $c\leftarrow\mathrm{Enc}_k(m)$ for $m\in\{0,1\}^*$ (possibly randomised), and $m := \mathrm{Dec}_k(c)$ (deterministic), with perfect correctness. Fixed-length with parameter $\ell$ : Enc is defined only on $\{0,1\}^{\ell(n)}$ .

DefinitionEavesdropping indistinguishability experiment $\mathrm{PrivK}^{\mathrm{eav}}_{\mathcal A,\Pi}(n)$

$\mathcal A(1^n)$ outputs $m_0, m_1$ of equal length.
$k\leftarrow\mathrm{Gen}(1^n)$ , $b\leftarrow\{0,1\}$ , $c\leftarrow\mathrm{Enc}_k(m_b)$ given to $\mathcal A$ .
$\mathcal A$ outputs $b'$ ; success iff $b' = b$ .

Def. 3.9: $\Pi$ has indistinguishable encryptions in the presence of an eavesdropper (is EAV-secure) if for every ppt $\mathcal A$ ,

$\Pr[\mathrm{PrivK}^{\mathrm{eav}}_{\mathcal A,\Pi}(n) = 1]\le\frac12 + \mathrm{negl}(n)$

This is Definition 2.4 with two relaxations: ppt adversaries and a negligible advantage.

Component	Detail
Power	sees one ciphertext, chooses the two candidate messages, polynomial time
Break	guessing which message was encrypted noticeably better than ½
Strategy	unrestricted (the arbitrary-adversary principle)

WarningEncryption doesn’t hide length

Equal-length messages are required. For schemes encrypting arbitrary lengths, unequal lengths make the definition unsatisfiable: compare a 1-bit message with one longer than any 1-bit ciphertext could be (Exercise 3.3). Bounded-length schemes can drop the restriction by padding everything to the maximum (Exercise 3.4). In practice, pad when length itself is sensitive (a salary’s number of digits).

DefinitionEquivalent form (Def. 3.10)

Fixing $b$ in the experiment, $\big\lvert\Pr[\mathrm{out}(\mathrm{PrivK}^{\mathrm{eav}}(n,0)) = 1] - \Pr[\mathrm{out}(\mathrm{PrivK}^{\mathrm{eav}}(n,1)) = 1]\big\rvert\le\mathrm{negl}(n)$ : the adversary behaves the same on encryptions of $m_0$ and $m_1$ . Equivalence (Exercise 3.5): $\Pr[\text{success}] = \frac12 + \frac12(\Pr[\mathrm{out}_0 = 0] - \Pr[\mathrm{out}_1 = 0])$ .

Semantic security

TheoremClaims 3.11–3.12 — Indistinguishability hides partial information

For an EAV-secure scheme:

No bit leaks: for uniform $m\in\{0,1\}^n$ and any position $i$ , $\Pr[\mathcal A(1^n,\mathrm{Enc}_k(m)) = m^i]\le\frac12 + \mathrm{negl}$ . If $\mathcal A$ predicted bit $i$ , distinguish random messages with bit $i = 0$ from ones with bit $i = 1$ .
No function leaks (uniform over an efficiently sampleable set $S_n$ , $f$ poly-time): some $\mathcal A'$ without the ciphertext computes $f(m)$ almost as well. $\mathcal A'$ simply runs $\mathcal A$ on $\mathrm{Enc}_k(1^n)$ , a ciphertext of a fixed dummy message. A gap would distinguish $\mathrm{Enc}(m)$ from $\mathrm{Enc}(1^n)$ .

DefinitionSemantic security (Def. 3.13; Goldwasser–Micali)

For every ppt $\mathcal A$ there is a ppt $\mathcal A'$ such that for every efficiently sampleable plaintext distribution $X$ (equal lengths per $n$ ) and all poly-time $f$ (target) and $h$ (external information),

$\big\lvert\Pr[\mathcal A(1^n,\mathrm{Enc}_k(m),h(m)) = f(m)] - \Pr[\mathcal A'(1^n,h(m)) = f(m)]\big\rvert\le\mathrm{negl}(n)$

The ciphertext adds nothing beyond what external knowledge $h(m)$ already gives. This is the formal version of “no function of the plaintext can be computed”.

TheoremTheorem 3.14 — Indistinguishability ⟺ semantic security

Use indistinguishability (easier to prove) and get semantic security (what we want). Analogous equivalences hold for every definition in this chapter.

Pseudorandomness

IntuitionLooks random to anyone efficient

Pseudorandomness is a property of a distribution (strictly, a sequence of distributions), not of a string: no ppt algorithm can tell it from uniform. It is the computational relaxation of true randomness, just as indistinguishability relaxes perfect secrecy. Payoff: XOR a long pseudorandom pad, grown from a short seed, into the message. To an efficient observer this is the one-time pad.

DefinitionPseudorandom generator (Def. 3.15)

A deterministic poly-time $G$ with $\lvert G(s)\rvert = \ell(\lvert s\rvert)$ such that

Expansion: $\ell(n) > n$ ;
Pseudorandomness: for every ppt distinguisher $D$ , $\big\lvert\Pr[D(r) = 1] - \Pr[D(G(s)) = 1]\big\rvert\le\mathrm{negl}(n),\qquad r\leftarrow\{0,1\}^{\ell(n)},\ s\leftarrow\{0,1\}^n$

$\ell$ is the expansion factor.

WarningPRG outputs are far from uniform

With $\ell(n) = 2n$ , at most $2^n$ of the $2^{2n}$ strings are outputs, so a random string is in the range with probability at most $2^{-n}$ . The exponential-time brute-force distinguisher (“does some seed produce this?”) has advantage $1 - 2^{-n}$ . Pseudorandomness holds only because efficient algorithms can’t run it. Hence: the seed must be uniform, secret, and long enough to make seed search infeasible.

NoteExistence

Unproven, but implied by one-way functions (Chapter 6), which exist if, for example, factoring is hard. Practical constructions (stream and block ciphers) are believed to satisfy even stronger properties.

Constructing secure encryption schemes

The pseudorandom one-time pad

AlgorithmConstruction 3.16

With $G$ a PRG of expansion $\ell$ : $k\leftarrow\{0,1\}^n$ ; $\mathrm{Enc}_k(m) = G(k)\oplus m$ for $m\in\{0,1\}^{\ell(n)}$ ; $\mathrm{Dec}_k(c) = G(k)\oplus c$ .

TheoremTheorem 3.17 — PRG ⇒ EAV-secure encryption

If $G$ is a pseudorandom generator, Construction 3.16 has indistinguishable encryptions in the presence of an eavesdropper.

ProofReduction to the generator

Let $\varepsilon(n) = \Pr[\mathrm{PrivK}^{\mathrm{eav}}_{\mathcal A,\Pi}(n) = 1] - \frac12$ . Distinguisher $D(w)$ , $w\in\{0,1\}^{\ell(n)}$ : run $\mathcal A(1^n)$ to get $m_0, m_1$ ; pick $b$ ; give $c = w\oplus m_b$ ; output 1 iff $\mathcal A$ guesses $b$ .

If $w$ is uniform, $\mathcal A$ sees a genuine one-time pad $\tilde\Pi$ , so $\Pr[D = 1] = \frac12$ by perfect secrecy.
If $w = G(k)$ , $\mathcal A$ sees exactly $\Pi$ , so $\Pr[D = 1] = \frac12 + \varepsilon(n)$ .

The distinguishing gap is $\varepsilon(n)$ , which must be negligible.

∎

ImportantWhat was gained

Still XOR with an $\ell$ -bit pad, but the pad comes from an $n$ -bit key, so a 128-bit key encrypts megabytes. This contradicts nothing: Theorem 2.7 is about unbounded adversaries. Reducing to a lower-level primitive is preferable because primitives are easier to design, study and gain confidence in.

Variable lengths and stream ciphers

DefinitionVariable output-length PRG (Def. 3.18)

$G(s,1^\ell)$ outputs $\ell$ bits; shorter outputs are prefixes of longer ones; and for every polynomial $\ell(\cdot)$ , $s\mapsto G(s,1^{\ell(\lvert s\rvert)})$ is a PRG. Encrypt with $c = G(k,1^{\lvert m\rvert})\oplus m$ . Any PRG can be converted to one; from a PRF: $G(s,1^\ell) = F_s(\langle1\rangle)\Vert F_s(\langle2\rangle)\Vert\cdots$ , truncated (Exercise 3.9).

WarningStream ciphers in practice

The book’s terminology: a stream cipher is the pad-generating tool (ideally a variable output-length PRG), not an encryption scheme. How it is used determines security.

RC4: fast and once trusted, but early output bytes are biased, which broke WEP (802.11). The advice was to discard about the first 1024 bits. (Since then RC4 has been prohibited in TLS by RFC 7465, 2015.)
LFSRs: completely insecure, since the key is recoverable from enough output.

Stream ciphers are less well understood than block ciphers, so prefer block ciphers (perhaps in a streaming mode) unless resources are very tight. RC4 was only about twice as fast as AES on a PC.

Multiple encryptions

DefinitionMulti-message experiment $\mathrm{PrivK}^{\mathrm{mult}}$ (Def. 3.19)

$\mathcal A$ outputs two vectors $\vec m_0,\vec m_1$ of the same number of messages, with pairwise equal lengths, and receives encryptions of all of $\vec m_b$ under one key. Same success condition.

TheoremClaim 3.20, Theorem 3.21 — Deterministic encryption fails for multiple messages

Any scheme whose Enc is a deterministic function of key and message is insecure for multiple encryptions. Output $\vec m_0 = (0^n,0^n)$ and $\vec m_1 = (0^n,1^n)$ , then check whether the two ciphertexts are equal: success probability 1. Construction 3.16 is EAV-secure but not multi-message secure. Secure multi-message encryption must be probabilistic (or stateful).

WarningReusing a stream is a classic implementation error

Microsoft Word and Excel once reused the pad across documents. Even without repeated messages, $c\oplus c' = m\oplus m'$ is devastating.

AlgorithmUsing a stream cipher safely

Synchronized (stateful): both parties consume successive, never-reused portions of one stream. Within a session, the whole conversation is one long message, so Theorem 3.17 applies. Stateful, so it escapes Theorem 3.21.
Unsynchronized (IV-based): $\mathrm{Enc}_k(m) = \langle IV,\ G(k,IV)\oplus m\rangle$ with a fresh uniform $IV$ . This needs a much stronger generator: streams for independent random $IV$ s must look independent and random even given the $IV$ s. That is nearly a pseudorandom function.

Chosen-plaintext attacks

DefinitionCPA experiment $\mathrm{PrivK}^{\mathrm{cpa}}_{\mathcal A,\Pi}(n)$ (Def. 3.22)

$k\leftarrow\mathrm{Gen}(1^n)$ .
$\mathcal A^{\mathrm{Enc}_k(\cdot)}(1^n)$ , with an encryption oracle (fresh coins per query), outputs equal-length $m_0, m_1$ .
Challenge $c\leftarrow\mathrm{Enc}_k(m_b)$ .
$\mathcal A$ keeps oracle access and outputs $b'$ ; success iff $b' = b$ .

CPA-secure: success at most $\frac12 + \mathrm{negl}(n)$ for every ppt $\mathcal A$ . This implies EAV security (just ignore the oracle).

ImportantCPA security requires randomised encryption

Otherwise, query $m_0$ and $m_1$ and compare with the challenge. No deterministic (stateless) scheme is CPA-secure.

ExampleChosen-plaintext attacks happen: Midway, 1942

US Navy cryptanalysts suspected the ciphertext fragment “AF” meant Midway, but couldn’t convince Washington. They had Midway send a plaintext report of low freshwater. Japanese intercepts soon reported “AF” was short of water. The Japanese had unknowingly encrypted a chosen plaintext, confirming the target, and the resulting US victory is often called the Pacific war’s turning point. Modern analogue: servers encrypting messages derived from user-controlled requests. Always use CPA-secure encryption.

TheoremClaim 3.23 and length extension

CPA security for one message ⇒ CPA security for many (proved later in the public-key setting). Unlike EAV security, there is no separate multi-message notion.
Arbitrary lengths for free: from a CPA-secure scheme for 1-bit messages, $\mathrm{Enc}'_k(m) = \mathrm{Enc}_k(m_1),\ldots,\mathrm{Enc}_k(m_\ell)$ is CPA-secure (by the multi-message property). Inefficient, but it means fixed-length constructions lose no generality.

ExampleMulti-message EAV security does not imply CPA (Exercise 3.7)

Take $\mathrm{Enc}_k(m) = \langle r,\ F_k(r)\oplus m,\ F_k(0^n)\rangle$ for $r\ne0^n$ , but also output $k$ if $m = F_k(0^n)$ . A multi-message eavesdropper fixes all its messages before seeing anything, so it hits $F_k(0^n)$ with negligible probability. A CPA adversary queries once, reads $F_k(0^n)$ , and queries it to get the key. Adaptivity matters. (Construction worked here.)

TheoremPerfect CPA security is impossible (Exercise 3.12)

Even against unbounded adversaries. Query $m_0$ and $m_1$ once each, getting fresh $c_0', c_1'$ . Guess 0 if only $c_0'$ equals the challenge $c$ , 1 if only $c_1'$ does, at random otherwise. With $P_{k,b}$ the ciphertext distribution of $m_b$ under $k$ ,

$\Pr[\text{success}] - \tfrac12 = \tfrac14\,\mathbb E_k\Big[\sum_c\big(P_{k,0}(c) - P_{k,1}(c)\big)^2\Big] > 0$

because correctness forces $P_{k,0}$ and $P_{k,1}$ to have disjoint supports. The advantage may be negligible, but never zero. (Argument worked here.)

Pseudorandom functions and CPA-secure encryption

DefinitionKeyed functions and $\mathrm{Func}_n$

A keyed function $F(k,x)$ , written $F_k(x)$ , is efficient if poly-time computable and, here, length-preserving ( $\lvert k\rvert = \lvert x\rvert = \lvert F_k(x)\rvert = n$ ). $\mathrm{Func}_n$ is all functions $\{0,1\}^n\to\{0,1\}^n$ : a look-up table of $n2^n$ bits, so $\lvert\mathrm{Func}_n\rvert = 2^{n\cdot2^n}$ . A uniform $f$ has independent uniform values at every point. $F_k$ ranges over at most $2^n$ of these $2^{n2^n}$ functions.

DefinitionPseudorandom function (Def. 3.24; Goldreich–Goldwasser–Micali)

For every ppt $D$ with oracle access (adaptive, polynomially many queries),

$\big\lvert\Pr[D^{F_k(\cdot)}(1^n) = 1] - \Pr[D^{f(\cdot)}(1^n) = 1]\big\rvert\le\mathrm{negl}(n),\qquad k\leftarrow\{0,1\}^n,\ f\leftarrow\mathrm{Func}_n$

Oracle access is needed because a random function’s description is exponentially long.

Point	Meaning
Key stays secret	with $k$ known, query $0^n$ and compare with $F_k(0^n)$ ; distinguished with advantage $1 - 2^{-n}$
Inherits random-function behaviour	inputs differing in one bit give unrelated outputs; finding $x$ with $F_k(x) = 0^n$ is hard
Existence	PRFs exist ⟺ PRGs exist (Chapter 6); block ciphers are believed PRFs
Proof paradigm	(1) analyse with a truly random $f$ (pure probability); (2) any gap would distinguish $F_k$ from $f$

ExamplePRF counterexamples (Exercises 3.6, 3.8, 3.10)

$F_k(x) = G'(k)\oplus x$ (a truncated PRG output XOR the input) isn’t a PRF: $F_k(x)\oplus F_k(x') = x\oplus x'$ always, unlike a random function.
PRG modifications: $G'(s) = G(s\Vert0^{\lvert s\rvert})$ need not be a PRG (a valid PRG can misbehave on that negligible set of seeds). $G'(s) = G(s_1\cdots s_{n/2})$ stays pseudorandom but may fail to expand if $\lvert G(s)\rvert = 2\lvert s\rvert$ exactly.

(Worked here.)

AlgorithmConstruction 3.25 — Encrypt with $F_k$ at a fresh random point

$k\leftarrow\{0,1\}^n$ . $\mathrm{Enc}_k(m)$ : choose $r\leftarrow\{0,1\}^n$ , output $\langle r,\ F_k(r)\oplus m\rangle$ . $\mathrm{Dec}_k(\langle r,s\rangle) = F_k(r)\oplus s$ .

Naive $\mathrm{Enc}_k(m) = F_k(m)$ is deterministic, hence not CPA-secure. Here each encryption gets an (almost certainly) new pseudorandom pad.

TheoremTheorem 3.26 — PRF ⇒ CPA-secure encryption

If $F$ is a PRF, Construction 3.25 is a CPA-secure fixed-length scheme for $n$ -bit messages.

ProofRandom-function world, then reduction

Step 1: Ideal scheme $\tilde\Pi$ with a truly random $f$ . Let $r_c$ be the challenge’s randomness, and $\mathsf{Repeat}$ the event that some oracle query used $r_c$ .

$\mathsf{Repeat}$ : the adversary learns $f(r_c) = s\oplus m$ and wins. But $\Pr[\mathsf{Repeat}]\le q(n)/2^n$ for $q(n)$ queries.
$\neg\mathsf{Repeat}$ : $f(r_c)$ is uniform and independent of everything seen, a one-time pad, so success is exactly $\frac12$ .

So $\Pr[\mathrm{PrivK}^{\mathrm{cpa}}_{\mathcal A,\tilde\Pi} = 1]\le\frac12 + q(n)/2^n$ (3.4), with no computational assumption on $\mathcal A$ beyond $q$ queries.

Step 2: Distinguisher $D^{\mathcal O}$ . Run $\mathcal A$ . Answer each oracle query $m$ with a fresh $r$ and $\langle r,\mathcal O(r)\oplus m\rangle$ , the challenge likewise with $m_b$ . Output 1 iff $\mathcal A$ guesses $b$ . With $\mathcal O = F_k$ this is exactly $\Pi$ ; with $\mathcal O = f$ , exactly $\tilde\Pi$ . Then $\mathrm{negl}\ge\big(\frac12 + \varepsilon(n)\big) - \big(\frac12 + \frac{q(n)}{2^n}\big)$ , so $\varepsilon(n)\le\mathrm{negl}(n) + q(n)/2^n$ , which is negligible.

∎

NoteCorollary 3.27 and cost

Block by block with fresh $r_i$ : $\langle r_1, F_k(r_1)\oplus m_1,\ldots,r_\ell, F_k(r_\ell)\oplus m_\ell\rangle$ is CPA-secure for arbitrary lengths, but the ciphertext is twice as long as the plaintext. Modes of operation fix this.

Pseudorandom permutations and block ciphers

Definition(Strong) pseudorandom permutation (Def. 3.28)

A keyed permutation (each $F_k$ a bijection, with $F_k$ and $F_k^{-1}$ efficient) such that no ppt $D$ with oracles for both $F_k$ and $F_k^{-1}$ can distinguish them from a uniform permutation $f$ with $f^{-1}$ . (Elsewhere, the forward-only version is “PRP” and this one “strong” or “super” PRP.)

TheoremProposition 3.29 — PRP ⇒ PRF

A random permutation and a random function differ only if a collision $f(x) = f(x')$ with $x\ne x'$ is seen. With $q$ queries this has probability at most $\binom q2/2^n$ (birthday bound, Exercise 3.11), which is negligible. So PRPs can replace PRFs anywhere.

ImportantBlock ciphers are PRPs, not encryption schemes

Model block ciphers as (strong) PRPs, which makes modes, MACs and protocols analysable. $c = F_k(m)$ alone is deterministic and not CPA-secure. In practice the key length may differ from the block length, which is what the input and output share (see block-cipher-constructions).

ExampleA PRP-only scheme that is CPA (even CCA) secure (Exercise 3.13)

$\mathrm{Enc}_k(m) = F_k(r\Vert m)$ for $m, r\in\{0,1\}^{n/2}$ with $r$ fresh. Decrypt by computing $F_k^{-1}(c)$ and keeping the second half. CPA intuition: the inputs $r\Vert m$ are all distinct except with probability about $q^2/2^{n/2}$ , and a random permutation on distinct inputs gives near-uniform outputs. Since $F$ is a strong PRP, any modified ciphertext decrypts to an unrelated random-looking input, which is the basis of CCA security. (Sketch worked here.)

Modes of operation

NoteSetup

Block cipher $F$ with block length $n$ , messages of $\ell$ blocks. Pad unambiguously with “1 then 0s”, adding a whole block if the length is already a multiple. The ciphertext expansion is ciphertext length minus message length.

Mode	Encrypt	Decrypt	Security	Needs $F^{-1}$	Parallel encrypt / decrypt
ECB	$c_i = F_k(m_i)$	$m_i = F_k^{-1}(c_i)$	not even EAV-secure: equal blocks show	yes	yes / yes
CBC	$c_0 = IV$ , $c_i = F_k(c_{i-1}\oplus m_i)$	$m_i = F_k^{-1}(c_i)\oplus c_{i-1}$	CPA (PRP), random IV	yes	no / yes
OFB	$r_0 = IV$ , $r_i = F_k(r_{i-1})$ , $c_i = m_i\oplus r_i$	$m_i = c_i\oplus r_i$	CPA (PRF)	no	stream precomputable, then XOR
CTR (randomised)	$r_i = F_k(ctr + i)$ , $c_i = m_i\oplus r_i$	$m_i = c_i\oplus F_k(ctr + i)$	CPA (PRF), Theorem 3.30	no	yes / yes; random access

(The decryption column answers Exercise 3.15.) The $IV$ / $ctr$ is sent in the clear, giving one block of expansion.

WarningECB should never be used

Deterministic, and repeated plaintext blocks are visible: it leaks structure even for a single message. It is included only for history.

ExampleCBC with a counter IV is not CPA-secure (Exercise 3.14)

If the IV is incremented rather than random, it is predictable. Query $0^n$ under IV $v$ to learn $F_k(v)$ . The challenge will use $IV = v+1$ . Submit $m_0 = v\oplus(v+1)$ , so the first block is $F_k((v+1)\oplus m_0) = F_k(v)$ , a known value, and $m_1$ anything else. Win with probability 1. (This is the logic behind the 2011 BEAST attack on TLS 1.0’s chained IVs.) (Worked here.)

TheoremTheorem 3.30 — Randomised CTR mode is CPA-secure

If $F$ is a PRF, randomised counter mode has indistinguishable encryptions under chosen-plaintext attack.

ProofRandom function plus an overlap bound

Ideal world with a truly random $f$ . Bound each query and the challenge at $q = q(n)$ blocks, with $q$ queries. The challenge uses $f$ at $ctr_c + 1,\ldots,ctr_c + q$ .

No overlap with any query’s counters: the challenge pad is fresh and uniform, so success is $\frac12$ .
Overlap: query $i$ ‘s range intersects the challenge’s iff $ctr_c + 1 - q\le ctr_i\le ctr_c + q - 1$ , which is $2q - 1$ values, so probability $(2q-1)/2^n$ . A union bound over queries gives $\Pr[\mathsf{Overlap}]\le2q^2/2^n$ .

So success is at most $\frac12 + 2q(n)^2/2^n$ , again requiring only polynomially many polynomial-length queries. The step from $f$ to $F_k$ is the same reduction as in Theorem 3.26 (Exercise 3.16).

∎

ImportantBlock length matters, not just key length

Every secure mode relies on the block cipher never seeing the same input twice. Even with a perfect 64-bit block cipher, CTR’s adversary gets about $q^2/2^{64}$ advantage, which is significant at $q\approx2^{30}$ . Use larger blocks for large data volumes. (Bhargavan–Leurent’s 2016 “Sweet32” attack exploited exactly this against 64-bit ciphers like 3DES in TLS.)

ExampleCTR with other input and output lengths (Exercise 3.17)

For $F_k : \{0,1\}^{\ell_{in}}\to\{0,1\}^{\ell_{out}}$ :

CPA: need $\ell_{in}(n) = \omega(\log n)$ so random counter ranges rarely overlap ( $2q^2/2^{\ell_{in}}$ negligible). Any $\ell_{out}\ge1$ works.
Fixed length $\ell(n)\cdot\ell_{out}$ , one message (EAV): only need $2^{\ell_{in}}\ge\ell(n)$ so the counter doesn’t wrap within the message.

(Worked here.)

ExampleCombining two schemes, one of which is secure (Exercise 3.18)

Split $m = m_1\oplus m_2$ with $m_1$ uniform, and send $(\mathrm{Enc}^1_{k_1}(m_1),\mathrm{Enc}^2_{k_2}(m_2))$ under independent keys. Either share alone is uniform, so breaking the combination means seeing through the secure component’s share. The reduction simulates the other scheme itself. (Worked here.)

RemarkStream versus block ciphers, and integrity

A block cipher yields many independent streams (one per $IV$ ), while a stream cipher gives essentially one. Stream ciphers’ only advantage is speed (often about 2×). Block ciphers are better studied and harder to misuse, so prefer them. None of these modes provides integrity; that is handled separately with message-authentication-codes (Chapter 4).

Chosen-ciphertext attacks

DefinitionCCA experiment $\mathrm{PrivK}^{\mathrm{cca}}_{\mathcal A,\Pi}(n)$ (Def. 3.31)

As CPA, but $\mathcal A$ also has a decryption oracle $\mathrm{Dec}_k(\cdot)$ throughout, and may not query it on the challenge ciphertext itself (otherwise no scheme could be secure). CCA-secure: success at most $\frac12 + \mathrm{negl}(n)$ .

ExampleWhen adversaries influence decryption

Midway again: send encrypted messages and watch the enemy’s reaction.
Unauthenticated bank channels: inject ciphertexts and learn from error behaviour whether the plaintext was well formed.
Protocols where a party decrypts a challenge and returns the result: that party is a decryption oracle.

WarningMalleability breaks CCA security

Construction 3.25 is not CCA-secure. Choose $m_0 = 0^n$ and $m_1 = 1^n$ , flip the first bit of $s$ in $\langle r,s\rangle$ , and ask for a decryption: $10^{n-1}$ means $b = 0$ , $01^{n-1}$ means $b = 1$ . CBC, OFB and CTR all fail the same way (Exercise 3.19): flipping a bit of the IV in CBC flips that bit of $m_1$ , and flipping a bit of $c_i$ in OFB or CTR flips the same bit of $m_i$ . CCA security implies non-malleability: a modified ciphertext must be invalid or decrypt to something unrelated. Construction: §4.8 (encryption combined with a MAC).

Further exercises

ExampleFactoring-based key sizes (Exercise 3.2)

100 years at 4 GHz is about $1.3\times10^{19}\approx2^{63.4}$ cycles. Solve $n^{1/3}(\log n)^{2/3}\ge63.4$ . With $\log_2$ , $n\approx2{,}100$ bits (2048 gives about 62.9). With natural log, about 3,800 bits. The base of the log in a crude cost model changes the answer substantially. (Calculation worked here; the base is ambiguous in the exercise.)

Quick reference

Object	Statement	Note
Relaxations	ppt adversaries + negligible success	both necessary when $\lvert\mathcal K\rvert<\lvert\mathcal M\rvert$
Negligible	$< 1/p(n)$ eventually, for every polynomial $p$	closed under $+$ and $\times\,\mathrm{poly}$
Reduction	adversary for $\Pi$ ⇒ solver for $X$	black-box simulation
EAV	$\Pr[\mathrm{PrivK}^{\mathrm{eav}} = 1]\le\frac12 + \mathrm{negl}$	equal-length messages
Semantic security	ciphertext adds nothing beyond $h(m)$	⟺ indistinguishability
PRG	$G(s)$ indistinguishable from uniform, $\ell(n)>n$	brute force advantage $1 - 2^{-n}$
PRG-OTP	$G(k)\oplus m$	EAV-secure, not multi-message
Deterministic	insecure for multiple messages and CPA	must randomise or keep state
CPA	encryption oracle	one-message ⇒ many-message
PRF	$F_k$ vs $f\leftarrow\mathrm{Func}_n$ via oracle	$\lvert\mathrm{Func}_n\rvert = 2^{n2^n}$
$\langle r, F_k(r)\oplus m\rangle$	CPA-secure, $\varepsilon\le\mathrm{negl} + q/2^n$	2× expansion
Strong PRP	oracles for $F_k, F_k^{-1}$	⇒ PRF (birthday)
Modes	ECB ✗; CBC, OFB, CTR CPA-secure with random IV	CTR: parallel, random access
CTR bound	$\frac12 + 2q^2/2^n$	block length matters
CCA	plus decryption oracle (not on the challenge)	implies non-malleability; all modes fail

Facts to keep to hand

Computational security trades a little for a lot. Restricting to efficient adversaries and forgiving negligible success makes short keys possible, at the cost of assumptions. Asymptotic statements must still be turned into concrete parameter choices.
Indistinguishability is the working definition. No efficient adversary can tell encryptions of two chosen messages apart. It is equivalent to semantic security (no function of the plaintext leaks), and it never hides length.
Pseudorandomness is the engine. A PRG stretches a short key into a pad (EAV-secure). A PRF gives a fresh pad per encryption (CPA-secure). Proofs first use a truly random object, then reduce. Pad reuse, deterministic encryption and predictable IVs are the classic failures.
Block ciphers are PRPs, used through modes. CBC, OFB and CTR with random IVs are CPA-secure up to birthday-type bounds in the block length. None is non-malleable, so CCA security needs integrity protection on top.

References

Katz & Lindell, Introduction to Modern Cryptography — Chapter 3
Goldwasser & Micali, “Probabilistic Encryption” (1984) — semantic security
Goldreich, Goldwasser & Micali, “How to Construct Random Functions” (1986)
Bellare, Desai, Jokipii & Rogaway, “A Concrete Security Treatment of Symmetric Encryption” (1997) — CPA proofs for CBC and CTR

Related