Notation

• x \xleftarrow{R} S$x \xleftarrow{R} S$: sample x$x$ uniformly at random from S$S$ (needs S$S$ efficiently sampleable)
• \Pi=(E,D)$\Pi=(E,D)$: cipher over (\mathcal K,\mathcal M,\mathcal C)$(\mathcal K,\mathcal M,\mathcal C)$; \mathcal I=(S,V)$\mathcal I=(S,V)$: MAC; \mathcal S=(G,S,V)$\mathcal S=(G,S,V)$: signature; \mathcal E=(G,E,D)$\mathcal E=(G,E,D)$: KEM/PKE; \mathcal T=(G,F,I)$\mathcal T=(G,F,I)$: trapdoor function
• W_b$W_b$ / W$W$: event "\mathcal A$\mathcal A$ outputs 1 in Experiment b$b$" / "\mathcal A$\mathcal A$ wins (or guesses b$b$)"
• \mathsf{Xadv}[\mathcal A,\Pi]:=|\Pr[W_0]-\Pr[W_1]|$\mathsf{Xadv}[\mathcal A,\Pi]:=|\Pr[W_0]-\Pr[W_1]|$ (two-experiment form); \mathsf{Xadv}^*[\mathcal A,\Pi]:=|\Pr[W]-\tfrac12|$\mathsf{Xadv}^*[\mathcal A,\Pi]:=|\Pr[W]-\tfrac12|$ (bit-guessing form); always \mathsf{Xadv}=2\cdot\mathsf{Xadv}^*$\mathsf{Xadv}=2\cdot\mathsf{Xadv}^*$
• [[P]]$[[P]]$: 1 if predicate P$P$ holds, else 0
• \mathcal Y^{\mathcal X}$\mathcal Y^{\mathcal X}$ / \mathrm{Sym}(\mathcal X)$\mathrm{Sym}(\mathcal X)$: all functions \mathcal X\to\mathcal Y$\mathcal X\to\mathcal Y$ / all permutations of \mathcal X$\mathcal X$
• Q, Q_e, Q_d, Q_{ro}$Q, Q_e, Q_d, Q_{ro}$: query budgets: total / encryption / decryption / random-oracle
• \lambda$\lambda$: security parameter; \Lambda$\Lambda$: system parameter (bit string determined by \lambda$\lambda$)

Foundations: Shannon ciphers, perfect security, semantic security

• Kerckhoffs' principle: a cipher's security rests on the secrecy of a dedicated key only, never on the secrecy of the mechanism (1883)
  • consequence: every attack game hands the adversary the full scheme description and withholds only the key; "security through obscurity" never appears as an assumption
• Shannon cipher: a pair of deterministic algorithms over spaces (\mathcal K,\mathcal M,\mathcal C)$(\mathcal K,\mathcal M,\mathcal C)$
  • formally: c\leftarrow E(k,m)$c\leftarrow E(k,m)$, E:\mathcal K\times\mathcal M\to\mathcal C$E:\mathcal K\times\mathcal M\to\mathcal C$; m\leftarrow D(k,c)$m\leftarrow D(k,c)$, D:\mathcal K\times\mathcal C\to\mathcal M$D:\mathcal K\times\mathcal C\to\mathcal M$; correctness: \forall k\in\mathcal K,\ m\in\mathcal M:\ D(k,E(k,m))=m$\forall k\in\mathcal K,\ m\in\mathcal M:\ D(k,E(k,m))=m$
  • note: keys uniform unless stated otherwise: \Pr[k=k_0]=1/|\mathcal K|$\Pr[k=k_0]=1/|\mathcal K|$
• OTP: the reference Shannon cipher; mask the message with the key by XOR (XOR is its own inverse)
  • formally: \mathcal K=\mathcal M=\mathcal C=\{0,1\}^L$\mathcal K=\mathcal M=\mathcal C=\{0,1\}^L$, E(k,m)=k\oplus m$E(k,m)=k\oplus m$, D(k,c)=k\oplus c$D(k,c)=k\oplus c$; correctness: k\oplus(k\oplus m)=(k\oplus k)\oplus m=m$k\oplus(k\oplus m)=(k\oplus k)\oplus m=m$
  • note (two-time pad): reusing k$k$ for m_0,m_1$m_0,m_1$ gives c_0\oplus c_1=m_0\oplus m_1$c_0\oplus c_1=m_0\oplus m_1$: the key cancels and the message XOR leaks; hence one message per key
• perfect security: the ciphertext is a dead end: it reveals nothing about the message
  • formally: \forall m_0,m_1\in\mathcal M,\ c\in\mathcal C:\ \Pr[E(k,m_0)=c]=\Pr[E(k,m_1)=c]$\forall m_0,m_1\in\mathcal M,\ c\in\mathcal C:\ \Pr[E(k,m_0)=c]=\Pr[E(k,m_1)=c]$
  • equivalent: \Pr[\mathbf m=m\mid\mathbf c=c]=\Pr[\mathbf m=m]$\Pr[\mathbf m=m\mid\mathbf c=c]=\Pr[\mathbf m=m]$ (message and ciphertext statistically independent)
  • equivalent (counting, uniform keys): \forall m_0,m_1,c:\ N_{m_0,c}=N_{m_1,c}$\forall m_0,m_1,c:\ N_{m_0,c}=N_{m_1,c}$ with N_{m,c}:=|\{k: E(k,m)=c\}|$N_{m,c}:=|\{k: E(k,m)=c\}|$: the number of keys mapping m$m$ to c$c$ does not depend on m$m$
  • equivalent (predicate): \forall\phi\in\{0,1\}^{\mathcal C}, m_0,m_1:\ \Pr[\phi(E(k,m_0))]=\Pr[\phi(E(k,m_1))]$\forall\phi\in\{0,1\}^{\mathcal C}, m_0,m_1:\ \Pr[\phi(E(k,m_0))]=\Pr[\phi(E(k,m_1))]$
• recipe: "show \Pi$\Pi$ IS perfectly secure" (counting is nearly always the shortest route):
  1. correctness first (usually a separate point): plug E$E$ into D$D$ and simplify with the algebraic law available (group/bijection inverse)
  2. existence: exhibit a key: e.g. group-OTP k:=c\circ m^{-1}$k:=c\circ m^{-1}$ gives E(k,m)=c$E(k,m)=c$ ✔
  3. uniqueness: E(k_1,m)=E(k_2,m)$E(k_1,m)=E(k_2,m)$ ⟹ cancel m$m$ using the group/bijection structure ⟹ k_1=k_2$k_1=k_2$ ✔
  4. conclude: N_{m,c}=1$N_{m,c}=1$ (or a constant) independent of m$m$ ⟹ \Pr[E(k,m)=c]=N_{m,c}/|\mathcal K|$\Pr[E(k,m)=c]=N_{m,c}/|\mathcal K|$ independent of m$m$ ∎
  • variant (\mathcal K$\mathcal K$ a set of bijections): N_{m,c}=|\{k\ \text{bijection}: k(m)=c\}|=(|\mathcal M|-1)!$N_{m,c}=|\{k\ \text{bijection}: k(m)=c\}|=(|\mathcal M|-1)!$: still independent of m$m$
• recipe: "show \Pi$\Pi$ is NOT perfectly secure" (one of two one-liners):
  1. cardinality: |\mathcal K|<|\mathcal M|$|\mathcal K|<|\mathcal M|$ ⟹ done by Shannon's theorem
  2. explicit witness: find m_0,m_1,c$m_0,m_1,c$ with N_{m_0,c}\ne N_{m_1,c}$N_{m_0,c}\ne N_{m_1,c}$: easiest when some c$c$ is reachable from one message under all keys and from another under none (e.g. Hill cipher: c=0^n$c=0^n$; N_{0^n,0^n}=|\mathcal K|$N_{0^n,0^n}=|\mathcal K|$ but N_{1^n,0^n}=0$N_{1^n,0^n}=0$)
• Shannon's theorem: perfect security costs a key at least as big as the message
  • formally: \Pi$\Pi$ perfectly secure ⟹ |\mathcal K|\ge|\mathcal M|$|\mathcal K|\ge|\mathcal M|$
  • proof shape (the template for impossibility arguments): assume |\mathcal K|<|\mathcal M|$|\mathcal K|<|\mathcal M|$; fix m_0,k'$m_0,k'$ and c:=E(k',m_0)$c:=E(k',m_0)$ so \Pr[E(k,m_0)=c]>0$\Pr[E(k,m_0)=c]>0$; let S=\{D(\hat k,c):\hat k\in\mathcal K\}$S=\{D(\hat k,c):\hat k\in\mathcal K\}$, so |S|\le|\mathcal K|<|\mathcal M|$|S|\le|\mathcal K|<|\mathcal M|$; pick m_1\in\mathcal M\setminus S$m_1\in\mathcal M\setminus S$; by correctness \Pr[E(k,m_1)=c]=0$\Pr[E(k,m_1)=c]=0$, contradiction ∎
  • in other words: brute-forcing all keys returns every message of that length equally often, so the enumeration tells you nothing; the price is a key as big as the message (1 GB file ⟹ 1 GB key)
• efficiency notions:
  • poly-bounded: \exists c,n_0\ \forall n\ge n_0:\ |f(n)|\le n^c$\exists c,n_0\ \forall n\ge n_0:\ |f(n)|\le n^c$ (e.g. n^3+5n$n^3+5n$)
  • PPT / efficient: probabilistic; runtime poly-bounded in the input length
  • negligible: \forall c\ \exists n_0\ \forall n\ge n_0:\ |f(n)|\le n^{-c}$\forall c\ \exists n_0\ \forall n\ge n_0:\ |f(n)|\le n^{-c}$ (e.g. 2^{-n}$2^{-n}$, n^{-\log n}$n^{-\log n}$)
  • super-poly: 1/f$1/f$ negligible (e.g. 2^n$2^n$: key-enumeration time)
  • efficiently sampleable: a set S$S$ for which a PPT algorithm draws s\xleftarrow{R}S$s\xleftarrow{R}S$ uniformly
  • closure (memorise the surprising cells): sum: neg+neg=neg, neg+poly=poly, anything+s-poly=s-poly; product: neg·neg=neg, neg·poly=neg (the one used constantly: a polynomial number of hybrids times a negligible per-hybrid advantage is still negligible), neg·s-poly undetermined, poly·poly=poly
• computational cipher: the Shannon cipher with computable, possibly randomised algorithms
  • formally: efficient algorithms E,D$E,D$; E$E$ may be non-deterministic: c\xleftarrow{R}E(k,m)$c\xleftarrow{R}E(k,m)$ abbreviates r\xleftarrow{R}\mathcal R;\ c\leftarrow E(k,m;r)$r\xleftarrow{R}\mathcal R;\ c\leftarrow E(k,m;r)$; correctness still for every choice of randomness: \forall c\xleftarrow{R}E(k,m):\ D(k,c)=m$\forall c\xleftarrow{R}E(k,m):\ D(k,c)=m$
  • in other words: every deterministic computational cipher is a Shannon cipher, not conversely; allowing randomised encryption is not cosmetic, since no deterministic scheme can be IND-CPA
• ciphertext indistinguishability, two-experiment form:
  • game: \mathcal A$\mathcal A$ outputs equal-length m_0,m_1\in\mathcal M$m_0,m_1\in\mathcal M$; challenger: k\xleftarrow{R}\mathcal K$k\xleftarrow{R}\mathcal K$, c\xleftarrow{R}E(k,m_b)$c\xleftarrow{R}E(k,m_b)$, sends c$c$; \mathcal A$\mathcal A$ outputs \hat b$\hat b$; W_b$W_b$ = "\mathcal A$\mathcal A$ outputs 1"
  • formally: \mathsf{SCadv}[\mathcal A,\Pi]:=|\Pr[W_0]-\Pr[W_1]|$\mathsf{SCadv}[\mathcal A,\Pi]:=|\Pr[W_0]-\Pr[W_1]|$; \Pi$\Pi$ is semantically secure (has indistinguishable ciphertexts) iff \mathsf{SCadv}$\mathsf{SCadv}$ is negligible for all PPT \mathcal A$\mathcal A$
• bit-guessing form: the challenger flips b\xleftarrow{R}\{0,1\}$b\xleftarrow{R}\{0,1\}$ itself; W$W$ = "\hat b=b$\hat b=b$"; \mathsf{SCadv}^*[\mathcal A,\Pi]:=|\Pr[W]-\tfrac12|$\mathsf{SCadv}^*[\mathcal A,\Pi]:=|\Pr[W]-\tfrac12|$
  • bridge (appears verbatim on the slides, reusable for CPA/CCA/KEM): \Pr[W]=\tfrac12\big(1-\Pr[W_0]+\Pr[W_1]\big)$\Pr[W]=\tfrac12\big(1-\Pr[W_0]+\Pr[W_1]\big)$ ⟹ \mathsf{SCadv}^*=\tfrac12\,\mathsf{SCadv}$\mathsf{SCadv}^*=\tfrac12\,\mathsf{SCadv}$
  • in other words: use whichever form fits your last game: bit-guessing when the chain must end at exactly \tfrac12$\tfrac12$ ("the view is independent of b$b$"), two-experiment when the last game is literally the other experiment
  • sanity (what an advantage measures: not the probability of guessing right, but the gap between the two worlds): always output 1 / flip a coin ⟹ adv 0$0$; random m_0,m_1$m_0,m_1$ ⟹ adv \le 1-\frac1{|\mathcal M|}$\le 1-\frac1{|\mathcal M|}$; E(k,m):=(\mathrm{parity}(m),E'(k,m))$E(k,m):=(\mathrm{parity}(m),E'(k,m))$ ⟹ adv 1$1$ no matter how good E'$E'$ is; perfectly secure cipher ⟹ adv 0$0$ for every adversary, even unbounded
• theorem: the OTP is semantically secure
  • proof: k$k$ uniform ⟹ m_b\oplus k$m_b\oplus k$ uniform, independent of b$b$ ⟹ \mathcal A$\mathcal A$'s view independent of b$b$ ⟹ \Pr[W]=\tfrac12$\Pr[W]=\tfrac12$ ⟹ \mathsf{SCadv}^*=0$\mathsf{SCadv}^*=0$ ∎
  • in other words: "the view is independent of b$b$, hence exactly \tfrac12$\tfrac12$" is how almost every game chain is closed
• key-guessing adversary (must be reproducible): \mathcal A$\mathcal A$ picks m_0,m_1\xleftarrow{R}\mathcal M$m_0,m_1\xleftarrow{R}\mathcal M$, receives c$c$, picks k_{\mathcal A}\xleftarrow{R}\mathcal K$k_{\mathcal A}\xleftarrow{R}\mathcal K$, outputs [[D(k_{\mathcal A},c)=m_0]]$[[D(k_{\mathcal A},c)=m_0]]$
  • Exp. 0: succeeds at least whenever k_{\mathcal A}=k_{\mathcal C}$k_{\mathcal A}=k_{\mathcal C}$ ⟹ \Pr\ge\tfrac1{|\mathcal K|}$\Pr\ge\tfrac1{|\mathcal K|}$; Exp. 1: m_0$m_0$ statistically independent of c$c$ ⟹ \Pr=\tfrac1{|\mathcal M|}$\Pr=\tfrac1{|\mathcal M|}$
  • in other words: if |\mathcal M|>|\mathcal K|$|\mathcal M|>|\mathcal K|$ the two differ ⟹ not perfectly secure; but the advantage \frac1{|\mathcal K|}-\frac1{|\mathcal M|}$\frac1{|\mathcal K|}-\frac1{|\mathcal M|}$ is negligible ⟹ semantically secure. The two escape hatches of the computational definition are exactly PPT (rules out brute force) and negligible (rules out lucky guessing)
• f(m,k):=(m,E(k,m))$f(m,k):=(m,E(k,m))$ is a OWF if \Pi$\Pi$ is semantically secure and |\mathcal K|/|\mathcal M|$|\mathcal K|/|\mathcal M|$ is negligible
  • proof: contrapositive + upgraded key-guesser: a PPT inverter \mathcal B$\mathcal B$ (adv \epsilon(n)$\epsilon(n)$) becomes a distinguisher with \mathsf{SCadv}[\mathcal A,\Pi]\ge\epsilon(n)-\frac{|\mathcal K|}{|\mathcal M|}$\mathsf{SCadv}[\mathcal A,\Pi]\ge\epsilon(n)-\frac{|\mathcal K|}{|\mathcal M|}$, non-negligible, contradiction
  • pattern name: "non-negligible minus negligible is non-negligible": reused whenever a hypothetical inverter/forger is turned into a distinguisher
• computational indistinguishability: D^1_n\stackrel{c}{\equiv}D^2_n$D^1_n\stackrel{c}{\equiv}D^2_n$
  • formally: \forall$\forall$ PPT \mathcal A:\ \big|\Pr[\mathcal A(D^1_n)=1]-\Pr[\mathcal A(D^2_n)=1]\big|\le\epsilon(n)$\mathcal A:\ \big|\Pr[\mathcal A(D^1_n)=1]-\Pr[\mathcal A(D^2_n)=1]\big|\le\epsilon(n)$ negligible
  • in other words: an equivalence relation (reflexive, symmetric, transitive via the triangle inequality: sum of negligibles is negligible); closed under PPT functions: given a distinguisher \mathcal A$\mathcal A$ for f_n(D^i_n)$f_n(D^i_n)$, the machine \mathcal B(x):=\mathcal A(f_n(x))$\mathcal B(x):=\mathcal A(f_n(x))$ is PPT and distinguishes the D^i_n$D^i_n$ with the same advantage (the wrapper pattern in its purest form)
  • restated definitions: G$G$ is a PRG iff G(U_n)\stackrel{c}{\equiv}U_{p(n)}$G(U_n)\stackrel{c}{\equiv}U_{p(n)}$ with p(n)>n$p(n)>n$; \Pi$\Pi$ semantically secure iff \forall m_0,m_1:\ E(U_{\mathcal K},m_0;U_{\mathcal R})\stackrel{c}{\equiv}E(U_{\mathcal K},m_1;U_{\mathcal R})$\forall m_0,m_1:\ E(U_{\mathcal K},m_0;U_{\mathcal R})\stackrel{c}{\equiv}E(U_{\mathcal K},m_1;U_{\mathcal R})$
• traps (over-reading a definition):
  • perfect security says nothing about two messages: c_1\oplus c_2=m_1\oplus m_2$c_1\oplus c_2=m_1\oplus m_2$ (OTP) resp. c_1^{-1}\circ c_2=m_1^{-1}\circ m_2$c_1^{-1}\circ c_2=m_1^{-1}\circ m_2$ (group OTP): key-free, so the single-message proof does not cover it (Project VENONA)
  • the attack-game definition of perfect security differs from the attack game in exactly two ways: no PPT restriction and no negligible slack (\Pr[W_0]=\Pr[W_1]$\Pr[W_0]=\Pr[W_1]$ exactly)
  • \mathcal A$\mathcal A$ must output messages of equal length: length leakage is unavoidable and therefore excluded by definition

PRGs, stream ciphers, OWFs

• PRG: stretch a short seed into a long string indistinguishable from uniform
  • formally: efficiently computable G:\mathcal S\to\mathcal R$G:\mathcal S\to\mathcal R$ with |\mathcal S|<|\mathcal R|$|\mathcal S|<|\mathcal R|$ (\mathcal S$\mathcal S$ seed space, \mathcal R$\mathcal R$ output space)
  • game: Exp. 0: s\xleftarrow{R}\mathcal S$s\xleftarrow{R}\mathcal S$, r\leftarrow G(s)$r\leftarrow G(s)$; Exp. 1: r\xleftarrow{R}\mathcal R$r\xleftarrow{R}\mathcal R$; \mathcal A$\mathcal A$ receives r$r$, outputs \hat b$\hat b$; \mathsf{PRGadv}[\mathcal A,G]:=|\Pr[W_0]-\Pr[W_1]|$\mathsf{PRGadv}[\mathcal A,G]:=|\Pr[W_0]-\Pr[W_1]|$; G$G$ is a secure PRG iff negligible for all PPT
  • rule of thumb for spotting a fake: look for any checkable relation among the output bits that a random string would violate (e.g. G(s)=s\|s$G(s)=s\|s$, G(s)=s\|\mathrm{parity}(s)$G(s)=s\|\mathrm{parity}(s)$)
• stream cipher: the OTP with a computationally stretched pad
  • formally: E(k,m):=G(k)\oplus m$E(k,m):=G(k)\oplus m$, D(k,c):=G(k)\oplus c$D(k,c):=G(k)\oplus c$ (truncating G$G$'s output to L$L$ bits is fine: truncation of a secure PRG is secure)
  • in other words: a 128-bit key instead of a 1-Mbit pad: exactly the practicality problem the OTP had, now solved computationally (Shannon's theorem is not violated because the scheme is no longer perfectly secure); one message per key: reuse is a two-time pad
• theorem: the archetypal reduction: \mathsf{PRGadv}[\mathcal B,G]=\mathsf{SCadv}^*[\mathcal A,\Pi]$\mathsf{PRGadv}[\mathcal B,G]=\mathsf{SCadv}^*[\mathcal A,\Pi]$
  • wrapper \mathcal B$\mathcal B$: receives k'$k'$ from the PRG challenger; picks b$b$, gets m_0,m_1$m_0,m_1$ from \mathcal A$\mathcal A$; sends k'\oplus m_b$k'\oplus m_b$ to \mathcal A$\mathcal A$; outputs [[\hat b=b]]$[[\hat b=b]]$
  • analysis: Exp. 0 ⟹ k'=G(k)$k'=G(k)$ ⟹ \mathcal A$\mathcal A$ plays the real bit-guessing game, \Pr[W_0]=\tfrac12\pm\mathsf{SCadv}^*$\Pr[W_0]=\tfrac12\pm\mathsf{SCadv}^*$; Exp. 1 ⟹ k'$k'$ uniform ⟹ \mathcal A$\mathcal A$ plays against the OTP, \Pr[W_1]=\tfrac12$\Pr[W_1]=\tfrac12$; subtract
  • rule of thumb: inner game bit-guessing, outer game distinguishing ⟹ output [[\hat b=b]]$[[\hat b=b]]$ (\mathcal A$\mathcal A$ only beats a coin when the pad is pseudorandom, and \mathcal B$\mathcal B$ chose b$b$ itself so it can check success)
• parallel composition: G'(s_0,\dots,s_{n-1}):=(G(s_0),\dots,G(s_{n-1}))$G'(s_0,\dots,s_{n-1}):=(G(s_0),\dots,G(s_{n-1}))$; \mathsf{PRGadv}[\mathcal A,G']\le n\cdot\mathsf{PRGadv}[\mathcal B,G]$\mathsf{PRGadv}[\mathcal A,G']\le n\cdot\mathsf{PRGadv}[\mathcal B,G]$
  • hybrid skeleton (the template: the hybrid technique is born here):
    1. why one wrapper is not enough: a PRG challenger hands over one value, but games 0 and n$n$ differ in n$n$ places
    2. define hybrids: Hybrid \gamma$\gamma$ uses r_j\xleftarrow{R}\mathcal R$r_j\xleftarrow{R}\mathcal R$ for j<\gamma$j<\gamma$ and r_j\leftarrow G(s_j)$r_j\leftarrow G(s_j)$ for j\ge\gamma$j\ge\gamma$; check the endpoints (Hybrid 0 = all pseudorandom = Exp. 0, Hybrid n$n$ = all random = Exp. 1): worth points
    3. define a wrapper per gap: \mathcal B_i$\mathcal B_i$ answers uniform for j<i$j<i$, plugs its challenge at position i$i$, G$G$ for j>i$j>i$; forwards \mathcal A$\mathcal A$'s bit unchanged
    4. match: Exp. 0 of \mathcal B_i$\mathcal B_i$'s challenger ⟹ Hybrid i$i$; Exp. 1 ⟹ Hybrid i+1$i+1$; since \mathcal B_i$\mathcal B_i$ echoes: \mathsf{PRGadv}[\mathcal B_i,G]=|p_i-p_{i+1}|$\mathsf{PRGadv}[\mathcal B_i,G]=|p_i-p_{i+1}|$
    5. telescope + triangle: |p_0-p_n|\le\sum_i|p_i-p_{i+1}|=\sum_i\mathsf{PRGadv}[\mathcal B_i,G]\le n\cdot\mathsf{PRGadv}[\mathcal B_{i^*},G]$|p_0-p_n|\le\sum_i|p_i-p_{i+1}|=\sum_i\mathsf{PRGadv}[\mathcal B_i,G]\le n\cdot\mathsf{PRGadv}[\mathcal B_{i^*},G]$ with i^*=\arg\max_i$i^*=\arg\max_i$ ∎
• sequential / Blum–Micali composition: G:\mathcal S\to\mathcal R\times\mathcal S$G:\mathcal S\to\mathcal R\times\mathcal S$, iterate (r_i,s_{i+1})\leftarrow G(s_i)$(r_i,s_{i+1})\leftarrow G(s_i)$; \mathsf{PRGadv}[\mathcal A,G_{BM}]\le n\cdot\mathsf{PRGadv}[\mathcal B,G]$\mathsf{PRGadv}[\mathcal A,G_{BM}]\le n\cdot\mathsf{PRGadv}[\mathcal B,G]$
  • hybrid twist: after sampling r_\gamma$r_\gamma$ uniform, resample s_\gamma\xleftarrow{R}\mathcal S$s_\gamma\xleftarrow{R}\mathcal S$ and continue the chain honestly from there; same 5 steps as parallel
  • in other words: huge output from a tiny seed, and consumed seeds can be deleted ⟹ perfect forward secrecy; this is literally the shape of the OWTP-KEM later
• the 5 classic hybrid mistakes (an exam favourite for "explain the error"):
  1. confusing hybrid challengers with wrappers: hybrids are games played with \mathcal A$\mathcal A$; wrappers are adversaries against a primitive challenger with \mathcal A$\mathcal A$ inside
  2. letting the wrapper's behaviour depend on which experiment its challenger is in: illegal, it does not know
  3. letting the wrapper use its challenger's secrets (k,s,sk$k,s,sk$…): it does not have them
  4. assuming "\mathcal A$\mathcal A$ probably knows x$x$ internally": \mathcal A$\mathcal A$ is a black box
  5. always reaching for a wrapper: if two hybrids are merely statistically close, use the difference lemma
• OWF: easy to evaluate, hard to invert: the weakest and most fundamental object in the course
  • game: x\xleftarrow{R}\mathcal X$x\xleftarrow{R}\mathcal X$, y\leftarrow f(x)$y\leftarrow f(x)$, \mathcal A$\mathcal A$ receives y$y$, outputs \hat x$\hat x$; wins if f(\hat x)=y$f(\hat x)=y$ (any preimage counts, not necessarily x$x$); \mathsf{OWFadv}[\mathcal A,f]=\Pr[W]$\mathsf{OWFadv}[\mathcal A,f]=\Pr[W]$; f$f$ one-way iff negligible for all PPT
• hard-core predicate: a single bit of the input that stays a coin flip even when f(x)$f(x)$ is public
  • game: same setup; \mathcal A$\mathcal A$ outputs a bit \hat b$\hat b$; wins if hc(x)=\hat b$hc(x)=\hat b$; \mathsf{HCadv}[\mathcal A,f,hc]=|\Pr[W]-\tfrac12|$\mathsf{HCadv}[\mathcal A,f,hc]=|\Pr[W]-\tfrac12|$; hc$hc$ hard-core for f$f$ iff negligible for all PPT
  • in other words: f(x)$f(x)$ may reveal a great deal about x$x$ (one-wayness only forbids recovering it entirely); hc(x)$hc(x)$ is one bit that remains as good as a coin flip
• theorem: 1-bit PRG from a one-way permutation + hard-core bit: f:\mathcal X\to\mathcal X$f:\mathcal X\to\mathcal X$ a permutation, hc$hc$ hard-core; G(x):=(hc(x),f(x))$G(x):=(hc(x),f(x))$; \mathsf{PRGadv}[\mathcal A,G]=\mathsf{HCadv}[\mathcal B,f,hc]$\mathsf{PRGadv}[\mathcal A,G]=\mathsf{HCadv}[\mathcal B,f,hc]$
  • wrapper \mathcal B$\mathcal B$ (worth remembering): receives y=f(x)$y=f(x)$; picks b\xleftarrow{R}\{0,1\}$b\xleftarrow{R}\{0,1\}$; runs \mathcal A(b,y)\to\hat b$\mathcal A(b,y)\to\hat b$; outputs \hat b\oplus b$\hat b\oplus b$
  • in other words: "guess the hard-core bit, then let \mathcal A$\mathcal A$ correct the guess": since f$f$ is a permutation, f(x)$f(x)$ is uniform, so a random first bit is exactly the "wrong pairing"
• the full pipeline (know by heart): OWF →(trivial modification)→ OWP + hc → G(x)=(hc(x),f(x)): 1-bit PRG → Blum–Micali: n-bit PRG → stream cipher E(k,m)=G(k)⊕m (concrete believed instance: f(x)=g^x\bmod p$f(x)=g^x\bmod p$, hc(x)=[[x<p/2]]$hc(x)=[[x<p/2]]$)
• existence results (the backbone of the one-liners):
  • a semantically secure cipher with |\mathcal K|\ll|\mathcal M|$|\mathcal K|\ll|\mathcal M|$ ⟹ OWFs exist (via f(m,k)=(m,E(k,m))$f(m,k)=(m,E(k,m))$: inverting = key recovery)
  • OWFs exist ⟹ P≠NP: L:=\{(y,x_1):\exists x_2: f(x_1\|x_2)=y\}\in\mathrm{NP}$L:=\{(y,x_1):\exists x_2: f(x_1\|x_2)=y\}\in\mathrm{NP}$; if P=NP$P=NP$, decide L$L$ and recover a preimage bit-by-bit (extend the prefix with 0, test membership, else 1) ⟹ f$f$ not one-way ∎
  • corollary for one-liners: "if X-secure schemes exist, do Y-secure schemes exist?" is almost always yes, justified by a path through OWF: X ⟹ OWF ⟹ PRG ⟹ PRF ⟹ PRP/MAC/AE/CCA/signatures
• exam constructions:
  • PRG \{0,1\}^n\to\{0,1\}^{3n}$\{0,1\}^n\to\{0,1\}^{3n}$ from a PRP: G(s):=P(s,[0])\,\|\,P(s,[1])\,\|\,P(s,[2])$G(s):=P(s,[0])\,\|\,P(s,[1])\,\|\,P(s,[2])$: the seed is the PRP key, evaluate at fixed distinct points (same trick answers "PRFs ⟹ PRGs": G(k):=F(k,0)\|F(k,1)\|\dots$G(k):=F(k,0)\|F(k,1)\|\dots$)
  • IND-CPA cipher for n$n$-bit messages from a PRG \{0,1\}^n\to\{0,1\}^{2n}$\{0,1\}^n\to\{0,1\}^{2n}$: write G(x)=G_0(x)\|G_1(x)$G(x)=G_0(x)\|G_1(x)$; E(k,m)$E(k,m)$: walk b_1,\dots,b_n\xleftarrow{R}\{0,1\}$b_1,\dots,b_n\xleftarrow{R}\{0,1\}$ with k\leftarrow G_{b_i}(k)$k\leftarrow G_{b_i}(k)$, return (b_1,\dots,b_n,\ k\oplus m)$(b_1,\dots,b_n,\ k\oplus m)$: the path bits are the nonce; each leaf key is pseudorandom and (whp) fresh, so each encryption is an independent OTP (GGM)
• decision procedure: "is this derived cipher still secure?":
  1. key-free relation between ciphertext parts (combining two components cancels the key: E(k,m)=(E_1(k,\rho),E_1(k,\rho)\oplus m)$E(k,m)=(E_1(k,\rho),E_1(k,\rho)\oplus m)$: XOR the halves ⟹ m$m$) ⟹ insecure
  2. a part usable as a key/oracle (E(k,(m_1,m_2))=(E_1(k,m_1),E_2(m_1,m_2))$E(k,(m_1,m_2))=(E_1(k,m_1),E_2(m_1,m_2))$: guess m_1$m_1$, decrypt the second part) ⟹ insecure
  3. key reuse across independent parts ((E_1(k,m_1),E_2(k,m_2))$(E_1(k,m_1),E_2(k,m_2))$ with both OTP = two-time pad; secure only if the parts are keyed differently, e.g. F(k,i)\oplus m$F(k,i)\oplus m$: that's CTR) ⟹ insecure in general
  4. otherwise reduce (wrapper; the fresh-randomness variant ends at a pure OTP where the win probability is exactly \tfrac12$\tfrac12$)

PRFs, IND-CPA, rCTR

• PRF: a keyed family indistinguishable from a truly random function
  • formally: efficiently computable F:\mathcal K\times\mathcal X\to\mathcal Y$F:\mathcal K\times\mathcal X\to\mathcal Y$
  • game: Exp. 0: k\xleftarrow{R}\mathcal K$k\xleftarrow{R}\mathcal K$, f\leftarrow F(k,\cdot)$f\leftarrow F(k,\cdot)$; Exp. 1: f\xleftarrow{R}\mathcal Y^{\mathcal X}$f\xleftarrow{R}\mathcal Y^{\mathcal X}$; \mathcal A$\mathcal A$ adaptively queries x_i$x_i$, receives f(x_i)$f(x_i)$, outputs \hat b$\hat b$; \mathsf{PRFadv}[\mathcal A,F]=|\Pr[W_0]-\Pr[W_1]|$\mathsf{PRFadv}[\mathcal A,F]=|\Pr[W_0]-\Pr[W_1]|$ (\mathsf{PRFadv}[\mathcal A,F,Q]$\mathsf{PRFadv}[\mathcal A,F,Q]$ for Q$Q$-query adversaries)
  • in other words (lazy sampling): the "random function" is built in a dictionary: answer a fresh uniform value on first query, remember it for repeats; the three notations (dictionary / f\xleftarrow{R}\mathcal Y^{\mathcal X}$f\xleftarrow{R}\mathcal Y^{\mathcal X}$ / fresh randoms per query) are interchangeable, and you should feel free to move between them
  • caching lemma: for every \mathcal A$\mathcal A$ there is a \mathcal B$\mathcal B$ that never repeats a query and is just as good: so "WLOG \mathcal A$\mathcal A$ never repeats a query" is a free move (write it)
  • example (a linear function is NOT a PRF): F((k_1,k_2),x)=k_1x+k_2$F((k_1,k_2),x)=k_1x+k_2$ over \mathbb F$\mathbb F$, |\mathbb F|\ge3$|\mathbb F|\ge3$: query 3 distinct points; solve the key from the first two (k_1=(f_1-f_2)/(x_1-x_2)$k_1=(f_1-f_2)/(x_1-x_2)$, k_2=f_1-k_1x_1$k_2=f_1-k_1x_1$); predict the third; adv =1-\frac1{|\mathbb F|}$=1-\frac1{|\mathbb F|}$; with only 2 queries the optimal adv is 0$0$ (for x_1\ne x_2$x_1\ne x_2$ the map k\mapsto(F(k,x_1),F(k,x_2))$k\mapsto(F(k,x_1),F(k,x_2))$ is a bijection)
  • pattern: "d+1$d+1$ queries determine a degree-d$d$ structure ⟹ predict query d+2$d+2$"
• IND-CPA: the stream cipher is one-message secure; many messages under one key need many independent-looking pads on demand
  • game: encryption oracle m_i\mapsto c_i\xleftarrow{R}E(k,m_i)$m_i\mapsto c_i\xleftarrow{R}E(k,m_i)$ before and after the challenge; one challenge \hat c\xleftarrow{R}E(k,\hat m_b)$\hat c\xleftarrow{R}E(k,\hat m_b)$ for equal-length \hat m_0,\hat m_1$\hat m_0,\hat m_1$; \mathsf{CPAadv}=|\Pr[W_0]-\Pr[W_1]|$\mathsf{CPAadv}=|\Pr[W_0]-\Pr[W_1]|$, bit-guessing \mathsf{CPAadv}^*=\tfrac12\mathsf{CPAadv}$\mathsf{CPAadv}^*=\tfrac12\mathsf{CPAadv}$; \mathsf{CPAadv}[\mathcal A,\Pi,Q]$\mathsf{CPAadv}[\mathcal A,\Pi,Q]$ for Q$Q$ encryption queries
  • immediate consequence: no deterministic cipher can be IND-CPA: pick \hat m_0\ne\hat m_1$\hat m_0\ne\hat m_1$, receive \hat c$\hat c$, then ask the oracle for \hat m_0$\hat m_0$ and output [[\hat c=c_0]]$[[\hat c=c_0]]$ (adv 1); every IND-CPA scheme is randomised or stateful; the attack uses an encryption query after the challenge: that is what "adaptive" buys
• rCTR: the model construction and proof of the course
  • formally: E(k,m)$E(k,m)$: iv\xleftarrow{R}\mathcal X$iv\xleftarrow{R}\mathcal X$; c[i]\leftarrow m[i]\oplus F(k,iv+i)$c[i]\leftarrow m[i]\oplus F(k,iv+i)$ for all i$i$; return (iv,c)$(iv,c)$ (F:\mathcal K\times\mathbb Z_{2^\lambda}\to\{0,1\}^n$F:\mathcal K\times\mathbb Z_{2^\lambda}\to\{0,1\}^n$, l$l$ = max blocks per message)
  • theorem: \mathsf{CPAadv}^*[\mathcal A,\Pi_{rCTR},Q]\le\mathsf{PRFadv}[\mathcal B,F,(Q+1)l]+\frac{2Ql}{|\mathcal X|}$\mathsf{CPAadv}^*[\mathcal A,\Pi_{rCTR},Q]\le\mathsf{PRFadv}[\mathcal B,F,(Q+1)l]+\frac{2Ql}{|\mathcal X|}$
  • three-game skeleton (copy this structure for any "PRF-based cipher is IND-CPA" task):
    • intuition first (earn partial credit): if (1) F$F$ is a secure PRF we are XOR-ing with random values; if (2) the inputs to F$F$ never overlap, those values are independent; then (3) the scheme is just a bunch of one-time pads
    • G_0$G_0$ (real) ⟶ G_1$G_1$: replace F(k,\cdot)$F(k,\cdot)$ by a random function (dictionary): wrapper \mathcal B$\mathcal B$ runs the challenger but asks its PRF challenger for every F$F$-value, outputs [[\hat b=b]]$[[\hat b=b]]$
    • G_1$G_1$ ⟶ G_2$G_2$: resample the iv$iv$'s so counter ranges never overlap (do\ x_i\leftarrow R\ \mathcal X\ while\ \|x_i-\hat x\|<l$do\ x_i\leftarrow R\ \mathcal X\ while\ \|x_i-\hat x\|<l$): difference lemma with Z$Z$ = "some |x_i-\hat x|<l$|x_i-\hat x|<l$", \Pr[Z]\le Q\frac{2l-1}{|\mathcal X|}\le\frac{2Ql}{|\mathcal X|}$\Pr[Z]\le Q\frac{2l-1}{|\mathcal X|}\le\frac{2Ql}{|\mathcal X|}$ (at most 2l-1$2l-1$ bad values of \hat x$\hat x$ per query window, union bound over Q$Q$)
    • end: the challenge uses a fresh independent pad ⟹ view independent of b$b$ ⟹ \Pr[W_2]=\tfrac12$\Pr[W_2]=\tfrac12$ (OTP argument)
  • same skeleton, OFB: IV_0\xleftarrow{R}\{0,1\}^n$IV_0\xleftarrow{R}\{0,1\}^n$; IV_i\leftarrow F(k,IV_{i-1})$IV_i\leftarrow F(k,IV_{i-1})$; c_i\leftarrow m_i\oplus IV_i$c_i\leftarrow m_i\oplus IV_i$; bound \mathsf{CPAadv}^*\le\mathsf{PRFadv}[\mathcal B,F]+\frac{(Q+1)L^2}{2^n}$\mathsf{CPAadv}^*\le\mathsf{PRFadv}[\mathcal B,F]+\frac{(Q+1)L^2}{2^n}$
• difference lemma: your second-most-used tool
  • formally: let Z,W_0,W_1$Z,W_0,W_1$ be events with W_0\cap\bar Z$W_0\cap\bar Z$ occurs iff W_1\cap\bar Z$W_1\cap\bar Z$ occurs ("the games are identical unless Z$Z$"); then |\Pr[W_0]-\Pr[W_1]|\le\Pr[Z]$|\Pr[W_0]-\Pr[W_1]|\le\Pr[Z]$
  • proof: split both probabilities on Z/\bar Z$Z/\bar Z$; the \bar Z$\bar Z$ parts cancel; the remaining two terms both lie in [0,\Pr[Z]]$[0,\Pr[Z]]$
  • in other words: you may "give away" the whole probability mass of the bad event: that is why bounding \Pr[Z]$\Pr[Z]$ by a crude union bound is fine
  • how to use it in the exam: always write: (1) the definition of Z$Z$ ("the event that …"); (2) the argument that the games coincide unless Z$Z$; (3) a numeric bound on \Pr[Z]$\Pr[Z]$ (usually #opportunities / size of the random space)
• "there and back again": E'(k,m)$E'(k,m)$: r\xleftarrow{R}\{0,1\}^n$r\xleftarrow{R}\{0,1\}^n$, k'\leftarrow F(k,r)$k'\leftarrow F(k,r)$, return (r,E(k',m))$(r,E(k',m))$ over a base \Pi$\Pi$ that is only semantically secure
  • in other words: the base is single-message secure, so you must reach a game where the challenge key is used exactly once; 6-game chain: real → F$F$ random (wrapper) → fresh k'$k'$ in the challenge only (difference lemma, \le\frac{Q}{2^n}$\le\frac{Q}{2^n}$ on "\hat r$\hat r$ collides with some r_i$r_i$") → challenge encrypts m_1$m_1$ instead (wrapper outsourcing only the challenge encryption to a semantic-security challenger: legal now, that key is used once) → and back again; \mathsf{CPAadv}\le2\,\mathsf{PRFadv}[\mathcal B,F]+\tfrac{2Q}{2^n}+\mathsf{SSadv}[\mathcal C,\Pi]$\mathsf{CPAadv}\le2\,\mathsf{PRFadv}[\mathcal B,F]+\tfrac{2Q}{2^n}+\mathsf{SSadv}[\mathcal C,\Pi]$
  • pattern: when the primitive you reduce to and the notion you prove are both two-experiment, walk from "encrypt m_0$m_0$" to a neutral middle game, swap, and walk back: each step is mirrored, argue each bound once
• PRF constructions:
  • from a PRG: G:\mathcal K\to\mathcal Y^2$G:\mathcal K\to\mathcal Y^2$; F(k,x)$F(k,x)$: (y_0,y_1)\leftarrow G(k)$(y_0,y_1)\leftarrow G(k)$, return y_x$y_x$ (1-bit domain; \le\mathsf{PRGadv}$\le\mathsf{PRGadv}$)
  • tree / GGM domain extension: F^*(k,(x_0,\dots,x_{l-1}))$F^*(k,(x_0,\dots,x_{l-1}))$: iterate k\leftarrow F(k,x_i)$k\leftarrow F(k,x_i)$, return k$k$
    • theorem: for PPT \mathcal A$\mathcal A$ with prefix-free queries totalling n$n$ symbols: \mathsf{PRFadv}[\mathcal A,F^*]\le n\cdot\mathsf{PRFadv}[\mathcal B,F]$\mathsf{PRFadv}[\mathcal A,F^*]\le n\cdot\mathsf{PRFadv}[\mathcal B,F]$; in particular fixed length l$l$: \le Ql\cdot\mathsf{PRFadv}$\le Ql\cdot\mathsf{PRFadv}$
    • why prefix-freeness is needed: the key returned for a query is the key used internally for any extension of that query: if \mathcal A$\mathcal A$ may ask both m$m$ and m\|a$m\|a$, it computes F^*(k,m\|a)=F(F^*(k,m),a)$F^*(k,m\|a)=F(F^*(k,m),a)$ itself (extension attack, like MD length extension); fix: prefix the length, \mathrm{enc}(m)=(\mathrm{len}(m),m_0,\dots)$\mathrm{enc}(m)=(\mathrm{len}(m),m_0,\dots)$
    • hybrid: over the first \gamma$\gamma$ visited tree nodes, replaced by independent random functions; \mathcal B_\gamma$\mathcal B_\gamma$ outsources node \gamma$\gamma$
  • arbitrary length, efficiently: NMAC F'((k_0,k_1),x):=F(k_0,H(k_1,x))$F'((k_0,k_1),x):=F(k_0,H(k_1,x))$ with a UHF H$H$
• comparing notions: "CPA vs non-adaptive CPA":
  • CPA ⟹ NA-CPA (weaker game is a special case): wrapper \mathcal B$\mathcal B$ plays the CPA game, buffers \mathcal A$\mathcal A$'s batch, forwards each query to its own oracle, forwards the challenge, echoes \mathcal A$\mathcal A$'s bit: both experiments perfectly emulated (general rule: to show "stronger ⟹ weaker", write a wrapper that just relays)
  • NA-CPA ⇏ CPA (separation by backdoor): take CPA-secure \Pi$\Pi$ and E'((k_1,k_2),m)=\begin{cases}(E(k_1,m),k_2)&m\ne k_2\\(k_1,\bot)&m=k_2\end{cases}$E'((k_1,k_2),m)=\begin{cases}(E(k_1,m),k_2)&m\ne k_2\\(k_1,\bot)&m=k_2\end{cases}$: the adaptive attacker reads k_2$k_2$ off a ciphertext, encrypts k_2$k_2$, receives k_1$k_1$, decrypts the challenge (adv \approx\tfrac12$\approx\tfrac12$); the non-adaptive one triggers the backdoor with probability \le Q/|\mathcal K_2|$\le Q/|\mathcal K_2|$ = negligible, and conditioned on not triggering it plays NA-CPA against \Pi$\Pi$ ∎
  • separation template: a secure scheme + a backdoor reachable only with information obtained from an earlier response

PRPs, IND-CCA2, Luby–Rackoff

• why CCA at all: the receiver's observable reaction to a tampered ciphertext (an error, a protocol action, a timing difference) is a decryption oracle; requirement: modified ciphertexts must yield no useful information (history: PKCS1-RSA, AES-CBC padding oracles)
• IND-CCA2: CPA plus a decryption oracle
  • game: decryption queries c_j\mapsto D(k,c_j)$c_j\mapsto D(k,c_j)$ before and after the challenge, with the single restriction c_j\ne\hat c$c_j\ne\hat c$; \mathsf{CCAadv}[\mathcal A,\Pi]=|\Pr[W_0]-\Pr[W_1]|$\mathsf{CCAadv}[\mathcal A,\Pi]=|\Pr[W_0]-\Pr[W_1]|$, \mathsf{CCAadv}^*=\tfrac12\mathsf{CCAadv}$\mathsf{CCAadv}^*=\tfrac12\mathsf{CCAadv}$, \mathsf{CCAadv}[\mathcal A,\Pi,Q_e,Q_d]$\mathsf{CCAadv}[\mathcal A,\Pi,Q_e,Q_d]$
  • in other words: c_j\ne\hat c$c_j\ne\hat c$ is the only thing standing between the adversary and a trivial win: every CCA proof revolves around what happens near \hat c$\hat c$; CCA security essentially forces non-malleability: every neighbour of \hat c$\hat c$ must be useless (for rCTR, \hat c$\hat c$ with one bit flipped decrypts to \hat m_b$\hat m_b$ with that bit flipped ⟹ recover b$b$)
• PRP: a permutation whose two directions both look like a random shuffle
  • formally: F:\mathcal K\times\mathcal X\to\mathcal X$F:\mathcal K\times\mathcal X\to\mathcal X$ such that for every k$k$ both F(k,\cdot)$F(k,\cdot)$ and F^{-1}(k,\cdot)$F^{-1}(k,\cdot)$ are efficiently computable permutations of \mathcal X$\mathcal X$ (that is the correctness property)
  • game: Exp. 0: f\leftarrow F(k,\cdot)$f\leftarrow F(k,\cdot)$; Exp. 1: f\xleftarrow{R}\mathrm{Sym}(\mathcal X)$f\xleftarrow{R}\mathrm{Sym}(\mathcal X)$; \mathcal A$\mathcal A$ may query forward (x\mapsto f(x)$x\mapsto f(x)$) and backward (y\mapsto f^{-1}(y)$y\mapsto f^{-1}(y)$), then outputs \hat b$\hat b$; \mathsf{PRPadv}[\mathcal A,F,Q_f,Q_b]$\mathsf{PRPadv}[\mathcal A,F,Q_f,Q_b]$
  • strongly secure PRP: \mathsf{PRPadv}$\mathsf{PRPadv}$ negligible for all PPT; weak PRP: \mathsf{wPRPadv}[\mathcal A,F,Q_f]:=\mathsf{PRPadv}[\mathcal A,F,Q_f,0]$\mathsf{wPRPadv}[\mathcal A,F,Q_f]:=\mathsf{PRPadv}[\mathcal A,F,Q_f,0]$ negligible (forward only); strong ⟹ weak
  • in other words: unlike a PRF a PRP is invertible (which is what lets us decrypt), but to anyone without the key both directions look like a random shuffle of the space; the relation between ciphertext and plaintext is not just hidden but rigid
• theorem: CCA-secure cipher from a strong PRP: P$P$ over (\mathcal K,\mathcal M\times\mathcal R)$(\mathcal K,\mathcal M\times\mathcal R)$
  • formally: E(k,m)$E(k,m)$: r\xleftarrow{R}\mathcal R$r\xleftarrow{R}\mathcal R$, return P(k,(m,r))$P(k,(m,r))$; D(k,c)$D(k,c)$: (m,r)\leftarrow P^{-1}(k,c)$(m,r)\leftarrow P^{-1}(k,c)$, return m$m$
  • bound: \mathsf{CCAadv}^*[\mathcal A,\Pi,Q_e,Q_d]\le\mathsf{PRPadv}[\mathcal B,P,Q_e{+}1,Q_d]+\frac{Q_e+Q_d}{|\mathcal M||\mathcal R|}+\frac{Q_e+Q_d}{|\mathcal R|}$\mathsf{CCAadv}^*[\mathcal A,\Pi,Q_e,Q_d]\le\mathsf{PRPadv}[\mathcal B,P,Q_e{+}1,Q_d]+\frac{Q_e+Q_d}{|\mathcal M||\mathcal R|}+\frac{Q_e+Q_d}{|\mathcal R|}$
  • proof (2 games): replace P(k,\cdot)$P(k,\cdot)$ by a random permutation: wrapper, \le\mathsf{PRPadv}$\le\mathsf{PRPadv}$; replace the challenge ciphertext by fresh \hat c\xleftarrow{R}\mathcal M\times\mathcal R$\hat c\xleftarrow{R}\mathcal M\times\mathcal R$: difference lemma with three bad events: Z_1$Z_1$ = the fresh ciphertext collides with an existing query ciphertext (space |\mathcal M||\mathcal R|$|\mathcal M||\mathcal R|$); Z_2$Z_2$ = (\hat m_b,\hat r)$(\hat m_b,\hat r)$ was produced by a decryption query (space |\mathcal R|$|\mathcal R|$); Z_3$Z_3$ = (\hat m_b,\hat r)$(\hat m_b,\hat r)$ was ever permuted during an encryption query (space |\mathcal R|$|\mathcal R|$); then \Pr[W_2]=\tfrac12$\Pr[W_2]=\tfrac12$ (view independent of b$b$)
  • pattern: when the "unless" condition has several independent causes, enumerate them as Z_1,Z_2,Z_3$Z_1,Z_2,Z_3$ and union-bound (graders look for exactly this); read off which space each denominator is: a fresh ciphertext is a full pair, a fresh nonce is not
  • footnote: \mathcal R=\{\varepsilon\}$\mathcal R=\{\varepsilon\}$ = deterministic, length-preserving (full-disk encryption): fine if a message is never re-encrypted twice; per-sector independence from tweakable PRPs E(k,s,m):=P(F(k,s),m)$E(k,s,m):=P(F(k,s),m)$ with a PRF F$F$ deriving a per-sector key
• Feistel permutation: \pi_f(x,y):=(y,\ x\oplus f(y))$\pi_f(x,y):=(y,\ x\oplus f(y))$, inverse \pi_f^{-1}(u,v)=(f(u)\oplus v,\ u)$\pi_f^{-1}(u,v)=(f(u)\oplus v,\ u)$
  • in other words: a permutation for any f$f$: no invertibility of f$f$ required; the swap-and-XOR structure guarantees invertibility because f$f$ only ever gets added, never inverted; that is why a PRF suffices to build a PRP
• Luby–Rackoff: 4 Feistel rounds, 4 independent keys (k_0,k_1,k_2,k_3)$(k_0,k_1,k_2,k_3)$
  • theorem: \mathsf{PRPadv}[\mathcal A,P,Q_f,Q_b]\le 4\cdot\mathsf{PRFadv}[\mathcal B,F,Q_f{+}Q_b]+\frac{Q^2}{|\mathcal X|}$\mathsf{PRPadv}[\mathcal A,P,Q_f,Q_b]\le 4\cdot\mathsf{PRFadv}[\mathcal B,F,Q_f{+}Q_b]+\frac{Q^2}{|\mathcal X|}$
  • game chain (8 games: mixes all three techniques): G_1..G_4$G_1..G_4$ replace the rounds one by one (4 wrappers, independent keys allow it: a hybrid with n=4$n=4$, hence the factor 4); G_5$G_5$ rewrite the two middle rounds as "sample x'_i,y'_i$x'_i,y'_i$ fresh, reusing an old value only on an input collision" (pure bookkeeping, gap 0); G_6$G_6$ drop the collision handling (difference lemma, Z$Z$ = "a collision in w$w$ or x$x$ occurs", per-query chance \le\frac{2i}{|\mathcal X|}$\le\frac{2i}{|\mathcal X|}$, \Pr[Z]\le\frac{Q^2-Q}{|\mathcal X|}$\Pr[Z]\le\frac{Q^2-Q}{|\mathcal X|}$); G_7$G_7$ = truly random permutation (differs only on output collisions, \le\frac{Q}{|\mathcal X|}$\le\frac{Q}{|\mathcal X|}$)
• PRP/PRF switching lemma: \big|\mathsf{wPRPadv}[\mathcal A,P,Q]-\mathsf{PRFadv}[\mathcal A,P,Q]\big|\le\frac{Q^2}{2|\mathcal X|}$\big|\mathsf{wPRPadv}[\mathcal A,P,Q]-\mathsf{PRFadv}[\mathcal A,P,Q]\big|\le\frac{Q^2}{2|\mathcal X|}$
  • proof: the two notions differ only in the ideal object (random permutation vs random function); write both challengers identically except the RP one resamples on output collisions; Z$Z$ : = "y_i=y_j$y_i=y_j$ for some j<i$j<i$": \binom Q2\le\frac{Q^2}{2}$\binom Q2\le\frac{Q^2}{2}$ unordered pairs, each colliding with probability \frac1{|\mathcal X|}$\frac1{|\mathcal X|}$; difference lemma ∎
  • in other words: a collision does not need a specific repeat: any two of the Q$Q$ answers; count unordered pairs (the \tfrac12$\tfrac12$ is the difference between ordered and unordered pairs); the same count produces every birthday-style term in the course
  • standard numeric exercise: AES-CTR, trusting AES as a perfect PRP, no nonce reuse, want \ge65$\ge65$ bits: \frac{Q^2}{2\cdot2^{128}}\le2^{-65}$\frac{Q^2}{2\cdot2^{128}}\le2^{-65}$ ⟹ Q\le2^{32}$Q\le2^{32}$ blocks =2^{32}\cdot16\ \mathrm{B}=64$=2^{32}\cdot16\ \mathrm{B}=64$ GiB; method: set the birthday term \le2^{-\kappa}$\le2^{-\kappa}$, solve for Q$Q$
• why PRPs are not the endgame: PRPs never repeat outputs ⟹ birthday-bounded security, artificially limited invocations; two passes over the input; length-preserving (real ciphers want PRFs); better PRF from PRPs when needed: F((k_1,k_2),m):=P(k_1,m)\oplus P(k_2,m)$F((k_1,k_2),m):=P(k_1,m)\oplus P(k_2,m)$
• exam task: S(k,m):=P(k,H(m))$S(k,m):=P(k,H(m))$ is EUF-CMA for a strong PRP P$P$ (super-poly |\mathcal X|$|\mathcal X|$) and CR H$H$
  • three transferable moves: (i) idealise the primitive: replace P$P$ by a lazily sampled random permutation (wrapper outsourcing every P$P$ value); (ii) excise the collision case by weakening the win condition: add "\forall m'\in Q: H(m')\ne H(m)$\forall m'\in Q: H(m')\ne H(m)$" (difference lemma, \le\mathsf{CRadv}$\le\mathsf{CRadv}$); (iii) bound the final guessing probability directly: the tag is a fresh uniform value from \mathcal X\setminus$\mathcal X\setminus$ used values: \Pr[W_2]\le\frac1{|\mathcal X|-q}$\Pr[W_2]\le\frac1{|\mathcal X|-q}$
  • in other words: nearly every MAC/signature proof in the course is exactly these three moves

MACs, UHFs, NMAC, keyless hashing

• MAC: make tampering detectable (the alternative to making it useless)
  • formally: \mathcal I=(S,V)$\mathcal I=(S,V)$ over (\mathcal K,\mathcal M,\mathcal T)$(\mathcal K,\mathcal M,\mathcal T)$; t\xleftarrow{R}S(k,m)$t\xleftarrow{R}S(k,m)$, S:\mathcal K\times\mathcal M\to\mathcal T$S:\mathcal K\times\mathcal M\to\mathcal T$: signing/tagging; v\leftarrow V(k,m,t)\in\{\text{accept},\text{reject}\}$v\leftarrow V(k,m,t)\in\{\text{accept},\text{reject}\}$: verification; correctness: \forall m,k,\ t\xleftarrow{R}S(k,m):\ V(k,m,t)=\text{accept}$\forall m,k,\ t\xleftarrow{R}S(k,m):\ V(k,m,t)=\text{accept}$
  • game: tag queries m_i\mapsto t_i\xleftarrow{R}S(k,m_i)$m_i\mapsto t_i\xleftarrow{R}S(k,m_i)$; then a forgery (\hat m,\hat t)$(\hat m,\hat t)$
  • SUF-CMA (the lecture's default \mathsf{MACadv}$\mathsf{MACadv}$): wins if accept and (\hat m,\hat t)\notin\{(m_i,t_i)\}$(\hat m,\hat t)\notin\{(m_i,t_i)\}$: a new pair suffices; EUF-CMA: wins if accept and \hat m\notin\{m_i\}$\hat m\notin\{m_i\}$: must be a new message
  • in other words: a replay (m_i,t_i)$(m_i,t_i)$ breaks nothing (explicitly excluded); a second valid tag for an old message breaks only SUF-CMA; a deterministic MAC with a unique valid tag per message makes the middle case impossible ⟹ EUF-CMA ⟺ SUF-CMA (PRF-MAC, FDH)
  • note: guessing a tag is a trivial baseline (success \ge\tfrac1{|\mathcal T|}$\ge\tfrac1{|\mathcal T|}$), so |\mathcal T|$|\mathcal T|$ must be super-poly
• theorem: PRF ⟹ MAC: S(k,m):=F(k,m)$S(k,m):=F(k,m)$, V(k,m,t):=[[F(k,m)=t]]$V(k,m,t):=[[F(k,m)=t]]$
  • bound: \mathsf{MACadv}[\mathcal A,\mathcal I,Q]\le\mathsf{PRFadv}[\mathcal B,F,Q{+}1]+\frac1{|\mathcal T|}$\mathsf{MACadv}[\mathcal A,\mathcal I,Q]\le\mathsf{PRFadv}[\mathcal B,F,Q{+}1]+\frac1{|\mathcal T|}$
  • proof (2 games): replace F$F$ by a random function: wrapper relays the queries; on forgery (\hat m,\hat t)$(\hat m,\hat t)$ it spends one extra query \hat m\mapsto t_Q$\hat m\mapsto t_Q$ and outputs [[\hat t=t_Q]]$[[\hat t=t_Q]]$ (that is where every Q+1$Q+1$ in the course comes from); since each message has exactly one valid tag, \mathcal B$\mathcal B$ outputs 1 iff \mathcal A$\mathcal A$ forges; in game 1, \mathcal A$\mathcal A$ must predict a random function at a fresh point: \Pr[W_1]\le\frac1{|\mathcal T|}$\Pr[W_1]\le\frac1{|\mathcal T|}$ ∎
• converse is false: a MAC that is not a PRF: S'(k,m):=(0,S(k,m))$S'(k,m):=(0,S(k,m))$, V'(k,m,(t_1,t_2)):=[[t_1=0]]\wedge V(k,m,t_2)$V'(k,m,(t_1,t_2)):=[[t_1=0]]\wedge V(k,m,t_2)$: still unforgeable (a forgery contains a forgery), trivially distinguishable from random
  • pattern: "append a predictable component": the generic way to break pseudorandomness while keeping unforgeability
• the "drop one field" attack catalogue (why every tag-input field is needed) for a block MAC S_{det}(k,(m_0,\dots,m_{d-1}),r):=(F_k(r,i,d,m_i))_{i<d}$S_{det}(k,(m_0,\dots,m_{d-1}),r):=(F_k(r,i,d,m_i))_{i<d}$:
  • drop r$r$ (nonce) ⟹ mix-and-match blocks across messages (forge (m_0,m_3)$(m_0,m_3)$ from tags of (m_0,m_1)$(m_0,m_1)$ and (m_2,m_3)$(m_2,m_3)$); drop i$i$ (index) ⟹ permute blocks within a message; drop d$d$ (length) ⟹ truncate; drop m_i$m_i$ (content) ⟹ the tag is message-independent: the same tag validates any m'$m'$ of the same length
  • in other words: if asked "why is field X in the input?", answer with the corresponding forgery: this table is the design rationale for every real MAC (why CBC-MAC needs length prefixing, why GCM binds the nonce, …)
• the "exhaustive case analysis on the forgery" pattern: after idealising to a random function, argue that in every case the winning forgery needs a function value the challenger never revealed; enumerate the cases so the grader can see the coverage is complete (nonce collision: \Pr\le\frac{Q^2}{2\cdot2^n}$\Pr\le\frac{Q^2}{2\cdot2^n}$; otherwise predict a fresh uniform n$n$-bit value: \le2^{-n}$\le2^{-n}$)
• one-time MACs from \epsilon$\epsilon$-almost-XOR-universal hashing: H:\mathcal K\times\mathcal M\to\mathbb F$H:\mathcal K\times\mathcal M\to\mathbb F$ with \forall m_0\ne m_1,\delta:\ \Pr_k[H(k,m_0)-H(k,m_1)=\delta]\le\epsilon$\forall m_0\ne m_1,\delta:\ \Pr_k[H(k,m_0)-H(k,m_1)=\delta]\le\epsilon$
  • formally: S((k,k'),m):=H(k,m)+k'\quad\Longrightarrow\quad\mathsf{MACadv}[\mathcal A,S,1]\le\epsilon$S((k,k'),m):=H(k,m)+k'\quad\Longrightarrow\quad\mathsf{MACadv}[\mathcal A,S,1]\le\epsilon$ for all adversaries \mathcal A$\mathcal A$: including computationally unbounded ones (information-theoretic)
  • why the extra key k'$k'$ is essential: without it the tag would be H(k,m_0)$H(k,m_0)$ itself: one tag leaks one equation in k$k$. With k'$k'$, the observed tag is a one-time-pad encryption of H(k,m_0)$H(k,m_0)$ under fresh k'$k'$, uniform and independent of k$k$; so the forger must predict the difference H(k,m_1)-H(k,m_0)=t_1-t_0$H(k,m_1)-H(k,m_0)=t_1-t_0$; the conditioning drops: \Pr[\cdot\mid\cdot]=\Pr[H(k,m_1)-H(k,m_0)=t_1-t_0]\le\epsilon$\Pr[\cdot\mid\cdot]=\Pr[H(k,m_1)-H(k,m_0)=t_1-t_0]\le\epsilon$
  • polynomial instantiation: H(k,m):=\mathrm{Poly}_{\mathbb F}(k,\mathrm{inj}(m))$H(k,m):=\mathrm{Poly}_{\mathbb F}(k,\mathrm{inj}(m))$, \mathrm{Poly}_{\mathbb F}(k,(m_1..m_L)):=(m_1k^L+\dots+m_Lk)$\mathrm{Poly}_{\mathbb F}(k,(m_1..m_L)):=(m_1k^L+\dots+m_Lk)$: the difference minus \delta$\delta$ is a non-zero polynomial in k$k$ of degree \le L$\le L$ ⟹ at most L$L$ roots ⟹ \epsilon=\frac{L}{|\mathbb F|}$\epsilon=\frac{L}{|\mathbb F|}$
  • counting argument: "non-zero polynomial of degree d$d$ has \le d$\le d$ roots" is the single most reusable counting argument in the course (also proves the UHF bound and the one-liner "integrity for a single message does not need OWFs")
  • note: reuse k'$k'$ and two tags immediately reveal H(k,m_1)-H(k,m_0)$H(k,m_1)-H(k,m_0)$: strictly one-time
• one-time ⟹ many-time (two standard fixes); the three bound terms are always the same story: PRF idealisation + nonce-collision birthday term + one-time MAC break:
  • fresh key per message: S'(k,m)$S'(k,m)$: r\xleftarrow{R}\mathcal R$r\xleftarrow{R}\mathcal R$, return (r,S(F(k,r),m))$(r,S(F(k,r),m))$; \le\mathsf{PRFadv}[\mathcal B,F,Q{+}1]+\frac{Q(Q-1)}{2|\mathcal R|}+Q\cdot\mathsf{MACadv}[\mathcal C,S,1]$\le\mathsf{PRFadv}[\mathcal B,F,Q{+}1]+\frac{Q(Q-1)}{2|\mathcal R|}+Q\cdot\mathsf{MACadv}[\mathcal C,S,1]$
  • Carter–Wegman: only the one-time-pad part is refreshed: S'((k,k'),m)$S'((k,k'),m)$: (r,\ H(k,m)\oplus F(k',r))$(r,\ H(k,m)\oplus F(k',r))$; \le\mathsf{PRFadv}[\mathcal B,F,Q{+}1]+\frac{Q(Q-1)}{2|\mathcal R|}+\mathsf{MACadv}[S,1]$\le\mathsf{PRFadv}[\mathcal B,F,Q{+}1]+\frac{Q(Q-1)}{2|\mathcal R|}+\mathsf{MACadv}[S,1]$; the PRF input is r$r$ only, independent of the message: which is why it is fast (this is Poly1305/GMAC)
• UHF: keyed hashing, committed before the key is known
  • game: k\xleftarrow{R}\mathcal K$k\xleftarrow{R}\mathcal K$ kept secret; \mathcal A$\mathcal A$ outputs m_0\ne m_1$m_0\ne m_1$; wins if H(k,m_0)=H(k,m_1)$H(k,m_0)=H(k,m_1)$; \mathsf{UHFadv}=\Pr[W]$\mathsf{UHFadv}=\Pr[W]$
  • crucial difference from collision resistance: the adversary must commit to the pair without knowing the key (this is what makes an unconditional bound like l/|\mathbb F|$l/|\mathbb F|$ possible)
  • polynomial UHF: H(k,x):=1\cdot k^l+x_0k^{l-1}+\dots+x_{l-1}k^0$H(k,x):=1\cdot k^l+x_0k^{l-1}+\dots+x_{l-1}k^0$ (Horner: t\leftarrow1$t\leftarrow1$; t\leftarrow k\cdot t+x_i$t\leftarrow k\cdot t+x_i$); \mathsf{UHFadv}[\mathcal A,H]\le\frac{l}{|\mathbb F|}$\mathsf{UHFadv}[\mathcal A,H]\le\frac{l}{|\mathbb F|}$ for every (unbounded!) \mathcal A$\mathcal A$ with messages of length \le l$\le l$: H(\cdot,m_0)-H(\cdot,m_1)$H(\cdot,m_0)-H(\cdot,m_1)$ is a non-zero polynomial of degree \le l$\le l$, a random key is a root with probability \le l/|\mathbb F|$\le l/|\mathbb F|$
  • recipe for "advantage 1" breaks of candidates: find a key-independent symmetry: permuting inputs of a commutative combiner, cancelling a repeated block, exploiting linearity; state (i) the two inputs, (ii) they are distinct, (iii) they collide for all keys; e.g. H(k,(x_1,\dots,x_m)):=k\oplus x_1\oplus\dots\oplus x_m$H(k,(x_1,\dots,x_m)):=k\oplus x_1\oplus\dots\oplus x_m$: output (x_1,x_2,x_3,\dots)$(x_1,x_2,x_3,\dots)$ and (x_2,x_1,x_3,\dots)$(x_2,x_1,x_3,\dots)$: XOR is commutative, both hash identically for every key
  • F^*$F^*$ is itself a UHF: \mathsf{UHFadv}[\mathcal A,F^*]\le\mathsf{PRFadv}[\mathcal B,F^*,2]+\frac1{|\mathcal K|}$\mathsf{UHFadv}[\mathcal A,F^*]\le\mathsf{PRFadv}[\mathcal B,F^*,2]+\frac1{|\mathcal K|}$: trick: \mathcal B$\mathcal B$ cannot query a prefix pair, so it appends a suffix a$a$ to both messages (collision probability only increases; in the random world it equals \frac1{|\mathcal K|}$\frac1{|\mathcal K|}$)
• PRF∘UHF: NMAC / Carter–Wegman: F'((k_0,k_1),x):=F(k_0,H(k_1,x))$F'((k_0,k_1),x):=F(k_0,H(k_1,x))$
  • bound: \mathsf{PRFadv}[\mathcal A,F',Q]\le\mathsf{PRFadv}[\mathcal B_F,F,Q]+\frac{Q^2}{2}\cdot\mathsf{UHFadv}[\mathcal B_H,H]$\mathsf{PRFadv}[\mathcal A,F',Q]\le\mathsf{PRFadv}[\mathcal B_F,F,Q]+\frac{Q^2}{2}\cdot\mathsf{UHFadv}[\mathcal B_H,H]$
  • the guessing factor \frac{Q^2}{2}$\frac{Q^2}{2}$: \mathcal B_H$\mathcal B_H$ must output the colliding pair but does not know which: it guesses two indices, right with probability \frac{2}{Q^2}$\frac{2}{Q^2}$ (Pattern G: it always costs a multiplicative factor equal to the number of possibilities)
  • NMAC = F'$F'$ instantiated with F^*$F^*$ (hash with the cascade under k_0$k_0$, one closing call under k_1$k_1$); HMAC = NMAC in disguise: \mathrm{SHA2}(k\oplus opad\,\|\,\mathrm{SHA2}(k\oplus ipad\,\|\,m))$\mathrm{SHA2}(k\oplus opad\,\|\,\mathrm{SHA2}(k\oplus ipad\,\|\,m))$ (the two derived keys stand in for independent keys)
• hash function: H:\mathcal M\to\mathcal T$H:\mathcal M\to\mathcal T$ with \mathcal M$\mathcal M$ the message space, \mathcal T$\mathcal T$ the digest space, usually |\mathcal M|\gg|\mathcal T|$|\mathcal M|\gg|\mathcal T|$
  • in other words: no key ⟹ security cannot be phrased as "the adversary does not know something": it has to be phrased as "finding a certain pair of inputs is hard"
• second-preimage resistant: challenger picks m_0\xleftarrow{R}\mathcal M$m_0\xleftarrow{R}\mathcal M$ and gives it to \mathcal A$\mathcal A$; \mathcal A$\mathcal A$ outputs m_1\ne m_0$m_1\ne m_0$; wins if H(m_0)=H(m_1)$H(m_0)=H(m_1)$; \mathsf{SPRadv}$\mathsf{SPRadv}$
• collision resistant: \mathcal A$\mathcal A$ outputs both m_0\ne m_1$m_0\ne m_1$ from scratch; wins if H(m_0)=H(m_1)$H(m_0)=H(m_1)$; \mathsf{CRadv}$\mathsf{CRadv}$ (strictly more freedom ⟹ the stronger requirement)
  • formally these only make sense for families \{H_{\lambda,\Lambda}\}$\{H_{\lambda,\Lambda}\}$: otherwise \mathcal A$\mathcal A$ hard-codes a collision; in practice we fix one function and declare it broken at the first published collision
  • the implication triangle: CR ⟹ SPR (wrapper \mathcal B$\mathcal B$ picks x$x$, hands it to the SPR-attacker, outputs the pair: wins whenever \mathcal A$\mathcal A$ wins); SPR + \frac{|\mathcal Y|}{|\mathcal X|}$\frac{|\mathcal Y|}{|\mathcal X|}$ negligible ⟹ OWF (partition \mathcal Y$\mathcal Y$ by preimage count: \mathsf{OWadv}[\mathcal A,H]\le\frac{|\mathcal Y|}{|\mathcal X|}+2\,\mathsf{SPRadv}[\mathcal B,H]$\mathsf{OWadv}[\mathcal A,H]\le\frac{|\mathcal Y|}{|\mathcal X|}+2\,\mathsf{SPRadv}[\mathcal B,H]$: on a \ge2$\ge2$-preimage point \mathcal A$\mathcal A$'s answer differs from x$x$ with probability \ge\tfrac12$\ge\tfrac12$)
  • CR & SPR but not OWF: the identity function (no collisions at all, trivially invertible): verbatim the one-liner "every collision-resistant function is one-way" = false
• hash-then-MAC: S'(k,m):=S(k,H(m))$S'(k,m):=S(k,H(m))$, V'(k,m,t):=V(k,H(m),t)$V'(k,m,t):=V(k,H(m),t)$; \mathsf{MACadv}[\mathcal A,\mathcal I']\le\mathsf{MACadv}[\mathcal B_I,\mathcal I]+\mathsf{CRadv}[\mathcal B_H,H]$\mathsf{MACadv}[\mathcal A,\mathcal I']\le\mathsf{MACadv}[\mathcal B_I,\mathcal I]+\mathsf{CRadv}[\mathcal B_H,H]$
  • proof = the canonical event split: whenever \mathcal A$\mathcal A$ forges (\hat m,\hat t)$(\hat m,\hat t)$, exactly one holds: (1) H(\hat m)=H(m_i)$H(\hat m)=H(m_i)$ for some queried m_i\ne\hat m$m_i\ne\hat m$ ⟹ \mathcal B_H$\mathcal B_H$ outputs the collision; (2) H(\hat m)$H(\hat m)$ fresh ⟹ (H(\hat m),\hat t)$(H(\hat m),\hat t)$ is a fresh valid forgery for \mathcal I$\mathcal I$; \Pr[W]=\Pr[W\cap Z]+\Pr[W\setminus Z]\le\mathsf{CRadv}+\mathsf{MACadv}$\Pr[W]=\Pr[W\cap Z]+\Pr[W\setminus Z]\le\mathsf{CRadv}+\mathsf{MACadv}$ ∎
  • strategic warning: H$H$ is unkeyed: the attacker hunts collisions offline, on its own hardware, without the key; the moment it finds m\ne m'$m\ne m'$ with H(m)=H(m')$H(m)=H(m')$, a tag for one is a tag for both; this is exactly why the requirement is collision resistance, not merely SPR
• Merkle–Damgård: a CR hash for long inputs from a CR compression function h:\mathcal T\times\mathcal M\to\mathcal T$h:\mathcal T\times\mathcal M\to\mathcal T$
  • formally: pad injectively (1000\dots0\,\|\,\mathrm{len}(m)$1000\dots0\,\|\,\mathrm{len}(m)$), iterate t_{i+1}\leftarrow h(t_i,m_i)$t_{i+1}\leftarrow h(t_i,m_i)$ from a fixed t_0$t_0$; \mathsf{CRadv}[\mathcal A,H_{MD}]=\mathsf{CRadv}[\mathcal B,h]$\mathsf{CRadv}[\mathcal A,H_{MD}]=\mathsf{CRadv}[\mathcal B,h]$
  • extraction (walk backwards): recompute both chains; at the last block, if the pairs differ: collision, output it; else the length encoding forces u=v$u=v$; walk i=u-1$i=u-1$ down to 0 and output the first (t_i,m_i)\ne(t'_i,m'_i)$(t_i,m_i)\ne(t'_i,m'_i)$: it exists because m\ne m'$m\ne m'$, and it is a collision because t_{i+1}=t'_{i+1}$t_{i+1}=t'_{i+1}$ was already verified ∎
  • two concrete compression functions: DL-based h(x,y):=a^xb^y\bmod p$h(x,y):=a^xb^y\bmod p$ (provably CR); Davies–Meyer h_{DM}(x,k):=E(k,x)\oplus x$h_{DM}(x,k):=E(k,x)\oplus x$ from a PRP (heuristic, ideal-cipher model; the message block is the key, the chaining value the plaintext; the feed-forward \oplus x$\oplus x$ destroys invertibility); SHA-2 = MD + Davies–Meyer
  • length extension: given t=H_{MD}(k\|M)$t=H_{MD}(k\|M)$ you can compute H_{MD}(k\|M\|\mathrm{pad}\|M')=h(t,M'\|\mathrm{pad}')$H_{MD}(k\|M\|\mathrm{pad}\|M')=h(t,M'\|\mathrm{pad}')$ without k$k$: the output is the internal state, so it can always be continued; hence F(k,x):=H_{MD}(k\|x)$F(k,x):=H_{MD}(k\|x)$ is not a PRF (a favourite one-liner and the reason HMAC exists)
• Merkle trees: H_0(x)=x$H_0(x)=x$; H_d(x_0,\dots,x_{2^d-1})=h(H_{d-1}(\text{left}),H_{d-1}(\text{right}))$H_d(x_0,\dots,x_{2^d-1})=h(H_{d-1}(\text{left}),H_{d-1}(\text{right}))$
  • a Merkle proof for (i,x_i)$(i,x_i)$ is the sibling path p\in\mathcal X^d$p\in\mathcal X^d$; verification recomputes upward from x_i$x_i$, choosing the argument order by the bits of i$i$ (LSB first), and compares with the root: only d$d$ hashes instead of all 2^d$2^d$ leaves
  • claim: \mathsf{MTadv}[\mathcal A,h]\le\mathsf{CRadv}[\mathcal B,h]$\mathsf{MTadv}[\mathcal A,h]\le\mathsf{CRadv}[\mathcal B,h]$; \mathcal B$\mathcal B$'s algorithm: run both verifications in lockstep: the first level where t_{k+1}=t^*_{k+1}$t_{k+1}=t^*_{k+1}$ while the inputs differ is a collision; failure is impossible (both chains end at the same root but start at x_i\ne x_i^*$x_i\ne x_i^*$)
  • pattern: identical to Merkle–Damgård: two different input paths converge to one output ⟹ a collision somewhere along the way; find it by scanning; expect this for any tree/chain hash construction
• applied counting: leaked DB with N$N$ users, passwords = 6 random base64 chars (64^6=2^{36}$64^6=2^{36}$): unsalted (\mathrm{user},H(pw))$(\mathrm{user},H(pw))$ ⟹ a guessed password checks against all N$N$ hashes ⟹ expected 2^{36}/N$2^{36}/N$ calls; salted (\mathrm{user},H(\mathrm{user},pw))$(\mathrm{user},H(\mathrm{user},pw))$ ⟹ expected 2^{36}$2^{36}$ calls: salting removes the factor N$N$

Ciphertext integrity, AE, Encrypt-then-MAC

• ciphertext integrity: the adversary must not be able to manufacture a ciphertext that the receiver accepts: not "decrypts to a chosen message", just any fresh c$c$ that does not bounce off with \bot$\bot$
  • game: encryption queries m_i\mapsto c_i\xleftarrow{R}E(k,m_i)$m_i\mapsto c_i\xleftarrow{R}E(k,m_i)$; \mathcal A$\mathcal A$ outputs \hat c\notin\{c_0,\dots,c_{Q-1}\}$\hat c\notin\{c_0,\dots,c_{Q-1}\}$; wins iff D(k,\hat c)\ne\bot$D(k,\hat c)\ne\bot$; \mathsf{CIadv}[\mathcal A,\Pi]:=\Pr[W]$\mathsf{CIadv}[\mathcal A,\Pi]:=\Pr[W]$; INT-CTXT = negligible for all PPT; D$D$ must be allowed to output \bot$\bot$
  • why it matters for confidentiality: an active attacker gains something from tampering only if the receiver does something observable with the tampered ciphertext; if every forgery is rejected, the decryption oracle stops being a source of information
  • example: rCTR has NO ciphertext integrity: query m=\texttt{0000}$m=\texttt{0000}$, receive (iv,c)$(iv,c)$, output (iv,c\oplus\texttt{1111})$(iv,c\oplus\texttt{1111})$ (never returned by the oracle): it decrypts to \texttt{1111}$\texttt{1111}$, not \bot$\bot$, so \mathsf{CIadv}=1$\mathsf{CIadv}=1$; this is malleability: CPA security says nothing about integrity
• AE: \Pi$\Pi$ is an authenticated-encryption scheme iff it is IND-CPA and provides ciphertext integrity
• theorem: AE ⟹ CCA ("kill the decryption oracle"): \mathsf{CCAadv}^*[\mathcal A,\Pi,Q_e,Q_d]\le Q_d\cdot\mathsf{CIadv}[\mathcal B_{CI},\Pi,Q_e{+}1]+\mathsf{CPAadv}^*[\mathcal B_{CPA},\Pi,Q_e]$\mathsf{CCAadv}^*[\mathcal A,\Pi,Q_e,Q_d]\le Q_d\cdot\mathsf{CIadv}[\mathcal B_{CI},\Pi,Q_e{+}1]+\mathsf{CPAadv}^*[\mathcal B_{CPA},\Pi,Q_e]$
  • proof: with ciphertext integrity, every decryption query that was not produced by the encryption oracle is doomed to return \bot$\bot$: predictably, so the oracle can be simulated by a lookup table:
    1. G_0$G_0$: real CCA game, but the challenger keeps Map[c_i]←m_i for its encryptions and, for a decryption query c_j$c_j$, sets Map[c_j]←D(k,c_j) if unknown, answers Map[c_j]
    2. G_1$G_1$: same, except the challenger answers only from Map and returns \bot$\bot$ for anything unseen (it never actually decrypts)
    3. gap = the forgery event: Z$Z$ : = "\mathcal A$\mathcal A$ submits a decryption query that is a valid forgery"; unless Z$Z$ the games are identical ⟹ difference lemma 4. bounding \Pr[Z]$\Pr[Z]$ needs an index guess: \mathcal B_{CI}$\mathcal B_{CI}$ picks \omega\xleftarrow{R}\{0,\dots,Q_d-1\}$\omega\xleftarrow{R}\{0,\dots,Q_d-1\}$, simulates, answers the first \omega$\omega$ decryption queries from Map, and submits the \omega$\omega$-th ciphertext to its CI challenger; given Z$Z$, \omega$\omega$ is the index of the first forgery with probability \frac1{Q_d}$\frac1{Q_d}$ ⟹ \mathsf{CIadv}[\mathcal B_{CI}]\ge\frac{\Pr[Z]}{Q_d}$\mathsf{CIadv}[\mathcal B_{CI}]\ge\frac{\Pr[Z]}{Q_d}$
    4. close with CPA: \mathcal B_{CPA}$\mathcal B_{CPA}$ simulates G_1$G_1$ using only its encryption oracle plus Map and echoes \mathcal A$\mathcal A$: |\Pr[W_1]-\tfrac12|=\mathsf{CPAadv}^*[\mathcal B_{CPA},\Pi,Q_e]$|\Pr[W_1]-\tfrac12|=\mathsf{CPAadv}^*[\mathcal B_{CPA},\Pi,Q_e]$; triangle inequality ∎
  • memorise the trio: (1) replace the real decryption oracle by a table-lookup oracle; (2) difference lemma on "a forgery slipped through"; (3) guess-the-index to convert "some query was a forgery" into "this specific query is my forgery"
• the three paradigms:
  • Encrypt-then-MAC: c\leftarrow E(k_e,m)$c\leftarrow E(k_e,m)$; t\leftarrow S(k_m,c)$t\leftarrow S(k_m,c)$; output (c,t)$(c,t)$: always secure given secure parts
  • MAC-then-Encrypt: t\leftarrow S(k_m,m)$t\leftarrow S(k_m,m)$; output E(k_e,m\|t)$E(k_e,m\|t)$: instance-dependent (the receiver must decrypt first to see the tag, so malformed ciphertexts get processed: precisely the padding-oracle situation that broke AES-CBC in TLS)
  • Encrypt-and-MAC: (E(k_e,m),S(k_m,m))$(E(k_e,m),S(k_m,m))$: instance-dependent; the naive version leaks (deterministic MAC over m$m$ ⟹ repeated messages detectable ⟹ not IND-CPA)
• Encrypt-then-MAC: independent keys are essential
  • formally: E_{EtM}((k_e,k_m),m)$E_{EtM}((k_e,k_m),m)$: c\leftarrow E(k_e,m)$c\leftarrow E(k_e,m)$; t\leftarrow S(k_m,c)$t\leftarrow S(k_m,c)$; return (c,t)$(c,t)$; D_{EtM}((k_e,k_m),(c,t))$D_{EtM}((k_e,k_m),(c,t))$: if V(k_m,c,t)\ne\text{accept}$V(k_m,c,t)\ne\text{accept}$ return \bot$\bot$; else return D(k_e,c)$D(k_e,c)$
  • theorem (equalities: no loss at all): \mathsf{CIadv}[\mathcal A_{CI},\Pi_{EtM},Q]=\mathsf{MACadv}[\mathcal B_{MAC},\mathcal I,Q]$\mathsf{CIadv}[\mathcal A_{CI},\Pi_{EtM},Q]=\mathsf{MACadv}[\mathcal B_{MAC},\mathcal I,Q]$ and \mathsf{CPAadv}[\mathcal A_{CPA},\Pi_{EtM},Q]=\mathsf{CPAadv}[\mathcal B_{CPA},\Pi,Q]$\mathsf{CPAadv}[\mathcal A_{CPA},\Pi_{EtM},Q]=\mathsf{CPAadv}[\mathcal B_{CPA},\Pi,Q]$
  • in other words: the cleanest "the wrapper owns one key, the challenger owns the other": \mathcal B_{MAC}$\mathcal B_{MAC}$ generates k_e$k_e$ itself, computes c_i=E(k_e,m_i)$c_i=E(k_e,m_i)$, asks its MAC challenger to tag c_i$c_i$ (a new valid ciphertext is a MAC forgery); \mathcal B_{CPA}$\mathcal B_{CPA}$ generates k_m$k_m$ itself, forwards messages to its CPA challenger, appends tags, echoes \mathcal A$\mathcal A$'s bit
  • why the order matters: with EtM, flipping bits of c$c$ invalidates t$t$: decryption returns \bot$\bot$ before the plaintext is ever touched
• AEAD: AD ciphers take an extra associated-data input d\in\mathcal D$d\in\mathcal D$ (E:\mathcal K\times\mathcal M\times\mathcal D\to\mathcal C$E:\mathcal K\times\mathcal M\times\mathcal D\to\mathcal C$); the pair (c,d)$(c,d)$ counts as "the ciphertext" for all security notions (IND-CCA2: any (c,d)\ne(\hat c,\hat d)$(c,d)\ne(\hat c,\hat d)$ to the decryption oracle; CI: a fresh tuple (\hat c,\hat d)$(\hat c,\hat d)$); EtM with AD tags the pair (c,d)$(c,d)$
  • use case: routing/metadata headers that intermediaries must read but nobody may alter; real: AES-GCM, AES-CCM (RFC 5116), ChaCha20-Poly1305 (RFC 8439)
• Encrypt-and-MAC done right: the MAC value is used as the encryption randomness: E'((k,k'),m)$E'((k,k'),m)$: r\xleftarrow{R}\mathcal R$r\xleftarrow{R}\mathcal R$, c\leftarrow E(k,m;F(k',(r,m)))$c\leftarrow E(k,m;F(k',(r,m)))$, return (r,c)$(r,c)$; D'$D'$ decrypts, then re-checks c=E(k,m;F(k',(r,m)))$c=E(k,m;F(k',(r,m)))$, else \bot$\bot$
  • IND-CPA (3 games): F\to$F\to$ random function (\mathsf{PRFadv}[\mathcal B,F,Q{+}1]$\mathsf{PRFadv}[\mathcal B,F,Q{+}1]$); then fresh honest randomness in E$E$ (difference lemma, \le\frac{(Q+1)^2}{2|\mathcal R|}$\le\frac{(Q+1)^2}{2|\mathcal R|}$ on a repeated input to f$f$); then \mathsf{CPAadv}^*[\mathcal C,\Pi,Q]$\mathsf{CPAadv}^*[\mathcal C,\Pi,Q]$
  • ciphertext integrity, assuming E$E$ is "strongly nondeterministic" (\Pr[E(k,m)=c]\le\epsilon$\Pr[E(k,m)=c]\le\epsilon$ for all k,m,c$k,m,c$): a forgery must have (\hat r,\hat m)\ne(r_i,m_i)$(\hat r,\hat m)\ne(r_i,m_i)$ for all i$i$ ⟹ f(\hat r,\hat m)$f(\hat r,\hat m)$ is fresh uniform ⟹ p_1=\Pr[\hat c=E(k,\hat m)]=\Pr[\hat c=E(k,\hat m;f(\hat r,\hat m))]\le\epsilon$p_1=\Pr[\hat c=E(k,\hat m)]=\Pr[\hat c=E(k,\hat m;f(\hat r,\hat m))]\le\epsilon$; total \le\mathsf{PRFadv}[\mathcal B,F,Q{+}1]+\epsilon$\le\mathsf{PRFadv}[\mathcal B,F,Q{+}1]+\epsilon$
  • nonce reuse: integrity is unaffected by r$r$-reuse; CPA security degrades only when the pair (r,m)$(r,m)$ repeats (the same ciphertext is produced, leaking only "these two messages were equal"): nonce-reuse resilience
• exam construction: AE from a single PRF: F:\{0,1\}^n\times\{0,1\}^*\to\{0,1\}^n$F:\{0,1\}^n\times\{0,1\}^*\to\{0,1\}^n$, messages m\cdot n$m\cdot n$ bits
  • \mathsf{Stream}(k,M,iv):=(M[0]\oplus F(k,(iv,0)),\ \dots,\ M[m-1]\oplus F(k,(iv,m-1)))$\mathsf{Stream}(k,M,iv):=(M[0]\oplus F(k,(iv,0)),\ \dots,\ M[m-1]\oplus F(k,(iv,m-1)))$
  • E(k,m)$E(k,m)$: iv\xleftarrow{R}\{0,1\}^n$iv\xleftarrow{R}\{0,1\}^n$; c\leftarrow\mathsf{Stream}(F(k,0),m,iv)$c\leftarrow\mathsf{Stream}(F(k,0),m,iv)$ (CTR under the encryption subkey F(k,0)$F(k,0)$); return (iv,\ c,\ F(k,(1,iv,c)))$(iv,\ c,\ F(k,(1,iv,c)))$ (domain 1: the tag covers iv$iv$ and c$c$); D(k,(iv,c,t))$D(k,(iv,c,t))$: if t\ne F(k,(1,iv,c))$t\ne F(k,(1,iv,c))$ return \bot$\bot$; else \mathsf{Stream}(F(k,0),c,iv)$\mathsf{Stream}(F(k,0),c,iv)$
  • checklist that earns the points: (1) Encrypt-then-MAC order: the tag covers (iv,c)$(iv,c)$, not m$m$; (2) key separation: encryption uses F(k,0)$F(k,0)$, authentication uses domain-tagged inputs (1,\dots)$(1,\dots)$; the leading 0/1$0/1$ is domain separation: the two uses of k$k$ can never produce the same PRF call; (3) randomised: fresh iv$iv$ per encryption, included in the tag; (4) decrypt returns \bot$\bot$ before touching the plaintext
  • standard traps in AE constructions: MAC-ing the plaintext instead of the ciphertext with a deterministic MAC; one key for both E$E$ and S$S$ without domain separation; forgetting the iv$iv$/nonce inside the authenticated data (attacker can swap iv$iv$'s); decrypting before verifying (padding-oracle-style leaks)

KEMs, OWTFs, the random oracle model, Diffie–Hellman

• KEM: with no shared secret, agree on one over a public channel: the sender never picks the key; it falls out of encapsulation
  • formally: \mathcal E=(G,E,D)$\mathcal E=(G,E,D)$ over (\mathcal K,\mathcal C)$(\mathcal K,\mathcal C)$; (pk,sk)\xleftarrow{R}G()$(pk,sk)\xleftarrow{R}G()$; (k,c)\xleftarrow{R}E(pk)$(k,c)\xleftarrow{R}E(pk)$: encapsulation takes no message; k\leftarrow D(sk,c)$k\leftarrow D(sk,c)$: decapsulation; correctness: D(sk,c)=k$D(sk,c)=k$ for all honest (k,c)$(k,c)$
  • contrast with PKE: a PKE takes a message you choose; a KEM manufactures a random key and its ciphertext together: so the attack game gives \mathcal A$\mathcal A$ nothing to choose
  • IND-CPA: (k_0,c)\xleftarrow{R}E(pk)$(k_0,c)\xleftarrow{R}E(pk)$, k_1\xleftarrow{R}\mathcal K$k_1\xleftarrow{R}\mathcal K$, send (pk,c,k_b)$(pk,c,k_b)$; \mathsf{KEMCPAadv}=|\Pr[W_0]-\Pr[W_1]|$\mathsf{KEMCPAadv}=|\Pr[W_0]-\Pr[W_1]|$; secure iff negligible for all PPT
  • IND-CCA2: same, plus decapsulation queries c_i\ne c\mapsto k_i\leftarrow D(sk,c_i)$c_i\ne c\mapsto k_i\leftarrow D(sk,c_i)$; \mathsf{KEMCCAadv}[\mathcal A,\mathcal E,Q]$\mathsf{KEMCCAadv}[\mathcal A,\mathcal E,Q]$
• trapdoor function: (pk,sk)\xleftarrow{R}G()$(pk,sk)\xleftarrow{R}G()$; y\leftarrow F(pk,x)$y\leftarrow F(pk,x)$, F:\mathcal X\to\mathcal Y$F:\mathcal X\to\mathcal Y$; x\leftarrow I(sk,y)$x\leftarrow I(sk,y)$: inversion only with the trapdoor; correctness: I(sk,F(pk,x))=x$I(sk,F(pk,x))=x$; if \mathcal X=\mathcal Y$\mathcal X=\mathcal Y$: trapdoor permutation (OWTP)
• OWTF: \mathsf{OWTFadv}[\mathcal A,\mathcal T]$\mathsf{OWTFadv}[\mathcal A,\mathcal T]$ negligible for all PPT
  • game: x\xleftarrow{R}\mathcal X$x\xleftarrow{R}\mathcal X$ (the challenger picks a uniformly random preimage: nothing is promised for structured inputs), y\leftarrow F(pk,x)$y\leftarrow F(pk,x)$; \mathcal A$\mathcal A$ wins on any \hat x$\hat x$ with F(pk,\hat x)=y$F(pk,\hat x)=y$
  • do NOT use a OWTF as encryption: "encrypt a random key k$k$ as F(pk,k)$F(pk,k)$" is broken in general: if F$F$ is a OWTF then so is F'(pk,(x_0,x_1)):=(x_0,F(pk,x_1))$F'(pk,(x_0,x_1)):=(x_0,F(pk,x_1))$ (one-wayness permits leaking half the input); one-wayness is about inverting completely; textbook RSA is a OWTF under the RSA assumption, not an IND-CPA PKE
• Blum–Micali KEM: from a OWTP, without random oracles: the only public-key construction in the course that needs no RO
  • formally: E(pk)$E(pk)$: s_0\xleftarrow{R}\mathcal S$s_0\xleftarrow{R}\mathcal S$; ((r_0..r_{n-1}),s_n)\leftarrow G^{pk}_{BM}(s_0)$((r_0..r_{n-1}),s_n)\leftarrow G^{pk}_{BM}(s_0)$; return (k=(r_0..r_{n-1}),\ c=s_n)$(k=(r_0..r_{n-1}),\ c=s_n)$; D(sk,c)$D(sk,c)$: invert n$n$ times, recompute the chain forwards, return the bits
  • bound: \mathsf{KEMCPAadv}[\mathcal A,\mathcal E_{BM}]\le\mathsf{PRGadv}[\mathcal B,G^{pk}_{BM}]$\mathsf{KEMCPAadv}[\mathcal A,\mathcal E_{BM}]\le\mathsf{PRGadv}[\mathcal B,G^{pk}_{BM}]$ (2 games: the whole PRG output replaced by random: s_n$s_n$ is uniform in \mathcal S$\mathcal S$ anyway, so the games are exactly the two KEM experiments)
  • in other words: the trapdoor turns "the seed is unrecoverable" into "the receiver can recover it"; the hard-core predicate does in the standard model what a random oracle does elsewhere, one bit at a time; price: a permutation (so s_n$s_n$ is uniform and the chain walks back) and n$n$ evaluations of F$F$ for an n$n$-bit key
• the Random Oracle Model: model the hash \mathcal O:\mathcal M\to\mathcal T$\mathcal O:\mathcal M\to\mathcal T$ as a uniformly random function; the challenger keeps a dictionary, filling entries lazily, and the adversary may query it at any time (Q_{ro}$Q_{ro}$ queries); advantages become \mathsf{X}ro\mathsf{adv}$\mathsf{X}ro\mathsf{adv}$; a heuristic ("standard model" = no RO)
  • template: in the ROM the "bad event" is always "the adversary queried the oracle at the one secret point"; bound it by (#RO queries)/(size of the secret space), or reduce it to a computational assumption
  • canonical proof: F_{pre}(k,x):=\mathcal O(k\|x)$F_{pre}(k,x):=\mathcal O(k\|x)$ is a PRF in the ROM: \mathsf{PRFroadv}[\mathcal A,F_{pre}]\le\frac{Q_{ro}}{|\mathcal K|}$\mathsf{PRFroadv}[\mathcal A,F_{pre}]\le\frac{Q_{ro}}{|\mathcal K|}$; G_0$G_0$: one dictionary, F$F$-queries fill D[k\|x]$D[k\|x]$, \mathcal O$\mathcal O$-queries fill D[m]$D[m]$; G_1$G_1$: identical text but declaring F$F$- and \mathcal O$\mathcal O$-queries to live in separate worlds; Z$Z$ : = "\mathcal A$\mathcal A$ ever queries \mathcal O$\mathcal O$ at some k\|\hat x$k\|\hat x$" (i.e. guessed the key); difference lemma; k$k$ is never revealed ⟹ \Pr[Z]\le\frac{Q_{ro}}{|\mathcal K|}$\Pr[Z]\le\frac{Q_{ro}}{|\mathcal K|}$ ∎
  • the bound is tight: an adversary that queries \mathcal O(k_i\|x)$\mathcal O(k_i\|x)$ for Q_{ro}$Q_{ro}$ candidate keys matches iff it guessed k$k$: guessing the key is the only attack
  • the ROM's limits (needed for one-liners): not always instantiable: there exist schemes secure in the ROM that no PPT function can instantiate securely; F(k,m):=H(m)$F(k,m):=H(m)$ is not a PRF in the ROM (the adversary computes H$H$ itself, no F$F$-queries needed); H_{MD}(k\|x)$H_{MD}(k\|x)$ is not a PRF (length extension); still useful: rules out all black-box-hash attacks, standard-model security implies ROM security, focuses cryptanalysis
  • QROM caveat: the proofs assume the adversary queries \mathcal O$\mathcal O$ classically; a quantum adversary queries in superposition: the constructions remain secure in the QROM, potentially with some loss
• KEM from a OWTF in the ROM: the construction the whole public-key chapter builds on:
  • formally: E(pk)$E(pk)$: x\xleftarrow{R}\mathcal X$x\xleftarrow{R}\mathcal X$; c\leftarrow F(pk,x)$c\leftarrow F(pk,x)$; k\leftarrow\mathcal O(x)$k\leftarrow\mathcal O(x)$; return (k,c)$(k,c)$; D(sk,c)$D(sk,c)$: return \mathcal O(I(sk,c))$\mathcal O(I(sk,c))$
  • bound: \mathsf{KEMCPAroadv}[\mathcal A,\mathcal E]\le\mathsf{OWTFadv}[\mathcal B,\mathcal T]$\mathsf{KEMCPAroadv}[\mathcal A,\mathcal E]\le\mathsf{OWTFadv}[\mathcal B,\mathcal T]$
  • in other words: the hash is not decoration: one-wayness permits a function that leaks half of x$x$; in the ROM, \mathcal O(x)$\mathcal O(x)$ is a uniformly random key the adversary has never seen unless it queried \mathcal O$\mathcal O$ at exactly x$x$; the whole proof reduces to "does the adversary ever ask the oracle about x$x$?", and asking means it has inverted F$F$
  • the reusable trick: "the reduction detects the bad event by re-evaluating the public function on every RO query": \mathcal B$\mathcal B$ picks k\xleftarrow{R}\mathcal K$k\xleftarrow{R}\mathcal K$, sends (pk,c,k)$(pk,c,k)$ to \mathcal A$\mathcal A$, answers RO queries at random but on each query x$x$ first checks F(pk,x)\stackrel{?}{=}c$F(pk,x)\stackrel{?}{=}c$; if yes outputs x$x$ and wins; so \mathsf{OWTFadv}[\mathcal B]\ge\Pr[Z]$\mathsf{OWTFadv}[\mathcal B]\ge\Pr[Z]$; this works because F(pk,\cdot)$F(pk,\cdot)$ is public: why deterministic OWTFs are easier than randomised ones (see FO)
• RSA: G()$G()$: random l$l$-bit primes p\ne q$p\ne q$ with \gcd(e,p-1)=\gcd(e,q-1)=1$\gcd(e,p-1)=\gcd(e,q-1)=1$; n\leftarrow pq$n\leftarrow pq$; d\leftarrow e^{-1}\bmod\mathrm{lcm}(p-1,q-1)$d\leftarrow e^{-1}\bmod\mathrm{lcm}(p-1,q-1)$; pk=(n,e)$pk=(n,e)$, sk=(n,d)$sk=(n,d)$; F((n,e),x)=x^e\bmod n$F((n,e),x)=x^e\bmod n$; I((n,d),y)=y^d\bmod n$I((n,d),y)=y^d\bmod n$
  • correctness: ed\equiv1\bmod\mathrm{lcm}(p-1,q-1)$ed\equiv1\bmod\mathrm{lcm}(p-1,q-1)$; Fermat mod p$p$ (and mod q$q$); CRT ⟹ x^{ed}\equiv x\bmod n$x^{ed}\equiv x\bmod n$
  • note: F$F$ is deterministic: hence textbook RSA is a OWTF, never an IND-CPA encryption scheme
  • RSA assumption: RSA is a secure OWTF; best classical attack factors n$n$ (sub-exponential) ⟹ 2048/4096-bit keys; no proof that factoring-hardness implies RSA-hardness
  • one-liner ammo: RSA gives OWTF ⟹ OWF ⟹ PRG ⟹ PRF ⟹ MAC: "secure MACs without random oracles under the RSA assumption" is true; the constructions work for any OWTF (McEliece, …), so swapping the assumption changes neither schemes nor proofs
• DH KEM: \mathbb G$\mathbb G$ cyclic of prime order q$q$, generator g$g$, hash H:\mathbb G^3\to\mathcal K$H:\mathbb G^3\to\mathcal K$
  • formally: G()$G()$: \alpha\xleftarrow{R}\mathbb Z_q$\alpha\xleftarrow{R}\mathbb Z_q$, A\leftarrow g^\alpha$A\leftarrow g^\alpha$, return (\alpha,A)$(\alpha,A)$; E(A)$E(A)$: \beta\xleftarrow{R}\mathbb Z_q$\beta\xleftarrow{R}\mathbb Z_q$, B\leftarrow g^\beta$B\leftarrow g^\beta$, k\leftarrow H(A^\beta,A,B)$k\leftarrow H(A^\beta,A,B)$, return (k,B)$(k,B)$; D(\alpha,B)$D(\alpha,B)$: return H(B^\alpha,g^\alpha,B)$H(B^\alpha,g^\alpha,B)$
  • in other words: both parties compute w=g^{\alpha\beta}$w=g^{\alpha\beta}$; a non-interactive key exchange (A$A$ and B$B$ sent simultaneously); the key is H(w,A,B)$H(w,A,B)$: never w$w$ itself (why H$H$ must be an extractor or RO); as a KEM: Alice's A$A$ is the public key, Bob's B$B$ is the ciphertext, Eve sees only (A,B)$(A,B)$ and would have to solve CDH for w$w$
• the DH assumptions:
  • DL: given g^\alpha$g^\alpha$, find \alpha$\alpha$ (i.e. f_{\mathbb G}(\alpha)=g^\alpha$f_{\mathbb G}(\alpha)=g^\alpha$ is a OWF)
  • CDH: given (g^\alpha,g^\beta)$(g^\alpha,g^\beta)$, output g^{\alpha\beta}$g^{\alpha\beta}$; \mathsf{CDHadv}=\Pr[W]$\mathsf{CDHadv}=\Pr[W]$
  • DDH: distinguish (g^\alpha,g^\beta,g^{\alpha\beta})$(g^\alpha,g^\beta,g^{\alpha\beta})$ from (g^\alpha,g^\beta,g^\gamma)$(g^\alpha,g^\beta,g^\gamma)$; \mathsf{DDHadv}=|\Pr[W_0]-\Pr[W_1]|$\mathsf{DDHadv}=|\Pr[W_0]-\Pr[W_1]|$
  • GDH: CDH plus a DDH-triple oracle; \mathsf{GDHadv}=\Pr[W]$\mathsf{GDHadv}=\Pr[W]$: strongest
  • relative strength: breaking DL breaks CDH breaks DDH, so as assumptions "DDH holds" is the strongest requirement, then CDH, then DL; GDH gives the adversary a decision oracle on top of CDH, so "GDH holds" is stronger than CDH, and it can only hold in groups where DDH is easy (pairing groups, exactly the situation it was invented for); CDH ≡ DL is open
• two security theorems for the same KEM: know both and when to use which:
  • (a) ROM + CDH: \mathsf{KEMCPAroadv}[\mathcal A,\mathcal E_{DH}]\le Q\cdot\mathsf{CDHadv}[\mathcal B,\mathbb G]$\mathsf{KEMCPAroadv}[\mathcal A,\mathcal E_{DH}]\le Q\cdot\mathsf{CDHadv}[\mathcal B,\mathbb G]$: G_1$G_1$ decouples the challenge key from H[\hat w,A,B]$H[\hat w,A,B]$; Z$Z$ : = "\mathcal A$\mathcal A$ queries H(\hat w,\cdot,\cdot)$H(\hat w,\cdot,\cdot)$"; \mathcal B$\mathcal B$ picks j\xleftarrow{R}[Q]$j\xleftarrow{R}[Q]$, answers the first j-1$j-1$ RO queries randomly, and on the j$j$-th query (w,a,b)$(w,a,b)$ submits w$w$ to the CDH challenger: right index with probability \frac1Q$\frac1Q$
  • (b) standard model + DDH + extractor: \mathsf{KEMCPAadv}[\mathcal A,\mathcal E_{DH}]\le\mathsf{DDHadv}[\mathcal B_{\mathbb G},\mathbb G]+\mathsf{EXTadv}[\mathcal B_H,H]$\mathsf{KEMCPAadv}[\mathcal A,\mathcal E_{DH}]\le\mathsf{DDHadv}[\mathcal B_{\mathbb G},\mathbb G]+\mathsf{EXTadv}[\mathcal B_H,H]$: G_0\to G_1$G_0\to G_1$: replace g^{\alpha\beta}$g^{\alpha\beta}$ by g^\gamma$g^\gamma$ (\mathcal B_{\mathbb G}$\mathcal B_{\mathbb G}$ just forwards its DDH triple, no guessing); G_1\to G_2$G_1\to G_2$: replace H(\hat w,A,B)$H(\hat w,A,B)$ by a random key
  • in other words (the "assumption trade-off"): the factor Q$Q$ in (a) is the price of not being able to check which query is the right one (contrast the OWTF-KEM, where F(pk,\cdot)$F(pk,\cdot)$ lets you test each query for free); under DDH you need only an extractor (no RO) but DDH is strong and fails in some groups; under CDH you need an RO but survive DDH failure: choosing H$H$ to be both a good extractor and a plausible RO gives a fallback: provable under DDH, heuristically fine under CDH alone
• strong randomness extractor: F:\mathcal X\times\mathcal R\to\mathcal K$F:\mathcal X\times\mathcal R\to\mathcal K$; game: x\xleftarrow{R}\mathcal D()$x\xleftarrow{R}\mathcal D()$, r\xleftarrow{R}\mathcal R$r\xleftarrow{R}\mathcal R$, k_0\leftarrow F(x,r)$k_0\leftarrow F(x,r)$, k_1\xleftarrow{R}\mathcal K$k_1\xleftarrow{R}\mathcal K$, send (k_b,r)$(k_b,r)$; \mathsf{EXTadv}=|\Pr[W_0]-\Pr[W_1]|$\mathsf{EXTadv}=|\Pr[W_0]-\Pr[W_1]|$
  • constructions: \mathcal D$\mathcal D$ uniform on \mathcal X=\mathcal K$\mathcal X=\mathcal K$ ⟹ F(x,r)=x$F(x,r)=x$ works with advantage exactly 0 (the trivial extractor: used by ElGamal); leftover hash lemma: UHFs extract from any distribution with enough min-entropy; RO with Q$Q$ queries, min-entropy m$m$ ⟹ \mathsf{EXTadv}\le Q\cdot2^{-m}$\mathsf{EXTadv}\le Q\cdot2^{-m}$
• key derivation: which primitive depends on what kind of entropy you start from:
  • an existing cryptographic key ⟹ PRF (can also stretch to many/long keys)
  • a computational secret (OWTF preimage, CDH value) ⟹ random oracle / hard-core function
  • a non-uniform high-entropy source (DDH value, hardware randomness) ⟹ strong randomness extractor
  • a low-entropy source (password) ⟹ as above, but deliberately slow
  • HKDF = extract-then-expand: k\leftarrow\mathrm{HMAC}(salt,s)$k\leftarrow\mathrm{HMAC}(salt,s)$, then z_i\leftarrow\mathrm{HMAC}(k,z_{i-1}\|info\|i)$z_i\leftarrow\mathrm{HMAC}(k,z_{i-1}\|info\|i)$ in CTR mode
• exercise patterns:
  • "build an IND-CCA2 KEM from …": (1) from any OWTF: FO with two ROs H_1,H_2$H_1,H_2$: E(pk)$E(pk)$: m\xleftarrow{R}\mathcal X$m\xleftarrow{R}\mathcal X$, r\leftarrow H_1(m)$r\leftarrow H_1(m)$, c\leftarrow F(pk,m)$c\leftarrow F(pk,m)$, return ((c,r),H_2(m))$((c,r),H_2(m))$; D$D$: invert, if (c,r)\ne(F(pk,m),H_1(m))$(c,r)\ne(F(pk,m),H_1(m))$ return \bot$\bot$, else H_2(m)$H_2(m)$; (2) from RSA: simplify as far as possible: E$E$: c\leftarrow m^e\bmod N$c\leftarrow m^e\bmod N$, return (c,H(m))$(c,H(m))$; D$D$: H(c^d\bmod N)$H(c^d\bmod N)$: RSA is a permutation, so the validity check can be dropped (OW ⟹ OW-VA); (3) from a CCA PKE: encrypt a random message and use it as the key: E_{kem}(pk)$E_{kem}(pk)$: m\xleftarrow{R}\mathcal M$m\xleftarrow{R}\mathcal M$, c\leftarrow E(pk,m)$c\leftarrow E(pk,m)$, return (c,m)$(c,m)$; D_{kem}(sk,c)$D_{kem}(sk,c)$: D(sk,c)$D(sk,c)$: the reduction hands (c,m_0)$(c,m_0)$ to the KEM-attacker; encrypting m_0$m_0$ is Exp. 0, m_1$m_1$ is Exp. 1 ⟹ equality of advantages
  • AD-KEM (extending a definition): CCA-secure KEM + PRF: E'(pk,d)$E'(pk,d)$: (c,k)\xleftarrow{R}E(pk)$(c,k)\xleftarrow{R}E(pk)$, return (c,F(k,d))$(c,F(k,d))$; D'(sk,c,d)$D'(sk,c,d)$: F(D(sk,c),d)$F(D(sk,c),d)$; 3 games: overwrite k^*\xleftarrow{R}\mathcal K$k^*\xleftarrow{R}\mathcal K$ (\le\mathsf{KEMCCAadv}$\le\mathsf{KEMCCAadv}$) → replace F(k^*,\cdot)$F(k^*,\cdot)$ by random (\le\mathsf{PRFadv}$\le\mathsf{PRFadv}$) → \Pr[W_2]=\tfrac12$\Pr[W_2]=\tfrac12$
  • the recurring "if c=c^*$c=c^*$" bookkeeping: whenever you replace an encapsulated/challenge key with a random one, you must also patch every oracle that would have recomputed that key: otherwise the games are not equivalent and \mathcal A$\mathcal A$ detects the change with a single query
  • KEM combiner: combine \mathcal E_1,\mathcal E_2$\mathcal E_1,\mathcal E_2$ into \mathcal E$\mathcal E$ that is CCA-secure if either is: E((pk_1,pk_2))$E((pk_1,pk_2))$: return ((c_1,c_2),\ H'(k_1,k_2,H(c_1,c_2)))$((c_1,c_2),\ H'(k_1,k_2,H(c_1,c_2)))$; assume \mathcal E_1$\mathcal E_1$ CCA, H$H$ CR, H'$H'$ a PRF with key k_1$k_1$; 4 games (overwrite k_1$k_1$ → replace H'$H'$ by random → k^0\xleftarrow{R}\mathcal K$k^0\xleftarrow{R}\mathcal K$): \mathsf{KEMCCAadv}^*[\mathcal A,\mathcal E]\le\mathsf{KEMCCAadv}[\mathcal B,\mathcal E_1]+\mathsf{PRFadv}[\mathcal C,H']+\mathsf{CRadv}[\mathcal D,H]$\mathsf{KEMCCAadv}^*[\mathcal A,\mathcal E]\le\mathsf{KEMCCAadv}[\mathcal B,\mathcal E_1]+\mathsf{PRFadv}[\mathcal C,H']+\mathsf{CRadv}[\mathcal D,H]$
    • ordering principle: idealise the primitive you assume secure first, then the primitive that consumes its output, then clean up collisions, then read off \tfrac12$\tfrac12$

PKE, hybrid encryption, FO

• PKE: \Pi=(G,E,D)$\Pi=(G,E,D)$ over (\mathcal M,\mathcal C)$(\mathcal M,\mathcal C)$; (pk,sk)\xleftarrow{R}G()$(pk,sk)\xleftarrow{R}G()$; c\xleftarrow{R}E(pk,m)$c\xleftarrow{R}E(pk,m)$ (must be randomised); m\leftarrow D(sk,c)$m\leftarrow D(sk,c)$; correctness: D(sk,c)=m$D(sk,c)=m$ for all honest (pk,sk),m,c$(pk,sk),m,c$
  • IND-CPA: \mathcal A$\mathcal A$ gets pk$pk$, submits equal-length \hat m_0,\hat m_1$\hat m_0,\hat m_1$, gets \hat c\xleftarrow{R}E(pk,\hat m_b)$\hat c\xleftarrow{R}E(pk,\hat m_b)$, outputs \hat b$\hat b$; \mathsf{PKCPAadv}$\mathsf{PKCPAadv}$
  • in other words: no encryption oracle is needed: \mathcal A$\mathcal A$ has pk$pk$ and can encrypt anything itself
  • IND-CCA2: additionally a decryption oracle for all c_i\ne\hat c$c_i\ne\hat c$; \mathsf{PKCCAadv}[\mathcal A,\Pi,Q]$\mathsf{PKCCAadv}[\mathcal A,\Pi,Q]$
• hybrid encryption: KEM ships the key, symmetric ships the message: what every real system does (1 GB file: one RSA operation + AES-GCM)
  • formally: symmetric \Pi_s=(E_s,D_s)$\Pi_s=(E_s,D_s)$ + KEM \mathcal E_k=(G_k,E_k,D_k)$\mathcal E_k=(G_k,E_k,D_k)$; E(pk,m)$E(pk,m)$: (k,c_k)\xleftarrow{R}E_k(pk)$(k,c_k)\xleftarrow{R}E_k(pk)$; c_s\xleftarrow{R}E_s(k,m)$c_s\xleftarrow{R}E_s(k,m)$; return (c_k,c_s)$(c_k,c_s)$; D(sk,(c_k,c_s))$D(sk,(c_k,c_s))$: k\leftarrow D_k(sk,c_k)$k\leftarrow D_k(sk,c_k)$, return D_s(k,c_s)$D_s(k,c_s)$
  • in other words: public-key operations are slow and bounded by the modulus size: keep the message-length work in symmetric crypto; ElGamal is literally this construction (DH-KEM + group one-time-pad)
  • CPA: \mathsf{PKCPAadv}^*[\mathcal A,\Pi]\le\mathsf{KEMCPAadv}[\mathcal B_k,\mathcal E_k]+\mathsf{SCadv}^*[\mathcal B_s,\Pi_s]$\mathsf{PKCPAadv}^*[\mathcal A,\Pi]\le\mathsf{KEMCPAadv}[\mathcal B_k,\mathcal E_k]+\mathsf{SCadv}^*[\mathcal B_s,\Pi_s]$; CCA: \mathsf{PKCCAadv}[\mathcal A,\Pi,Q]\le\mathsf{KEMCCAadv}[\mathcal B_k,\mathcal E_k,Q]+\mathsf{CCAadv}^*[\mathcal B_s,\Pi_s,0,Q]$\mathsf{PKCCAadv}[\mathcal A,\Pi,Q]\le\mathsf{KEMCCAadv}[\mathcal B_k,\mathcal E_k,Q]+\mathsf{CCAadv}^*[\mathcal B_s,\Pi_s,0,Q]$
  • the single game step in both cases: G_1$G_1$ = "pretend the encapsulated key is a fresh random \hat k$\hat k$": \mathcal B_k$\mathcal B_k$ takes (pk,\hat c_k,\hat k)$(pk,\hat c_k,\hat k)$ from the KEM challenger, encrypts \hat m_b$\hat m_b$ under \hat k$\hat k$, outputs [[\hat b=b]]$[[\hat b=b]]$ (real key ⟹ G_0$G_0$, random key ⟹ G_1$G_1$)
  • why the CCA version needs strictly more: in G_1$G_1$ the wrapper must still answer decryption queries (c_k,c_s)\ne(\hat c_k,\hat c_s)$(c_k,c_s)\ne(\hat c_k,\hat c_s)$: if c_k\ne\hat c_k$c_k\ne\hat c_k$ it asks its KEM decapsulation oracle ⟹ the KEM must be CCA-secure; if c_k=\hat c_k$c_k=\hat c_k$ but c_s\ne\hat c_s$c_s\ne\hat c_s$ it must decrypt c_s$c_s$ under the challenge key ⟹ the symmetric cipher must be CCA-secure (0 encryption, Q$Q$ decryption queries)
  • in other words ("formality-guided design"): write the reduction, see what the wrapper cannot do, and let that define the requirement on the primitive: expect "which properties must X$X$ have so that the construction is secure?"
• ElGamal: the hybrid paradigm hiding in plain sight
  • formally: G()$G()$: \alpha\xleftarrow{R}\mathbb Z_q$\alpha\xleftarrow{R}\mathbb Z_q$, A\leftarrow g^\alpha$A\leftarrow g^\alpha$ (sk=\alpha$sk=\alpha$, pk=A$pk=A$); E(A,m)$E(A,m)$: \beta\xleftarrow{R}\mathbb Z_q$\beta\xleftarrow{R}\mathbb Z_q$, B\leftarrow g^\beta$B\leftarrow g^\beta$, k\leftarrow A^\beta$k\leftarrow A^\beta$, return (B,k\circ m)$(B,k\circ m)$; D(\alpha,(B,c))$D(\alpha,(B,c))$: (B^\alpha)^{-1}\circ c$(B^\alpha)^{-1}\circ c$
  • bound: \mathsf{PKCPAadv}^*=\mathsf{DDHadv}$\mathsf{PKCPAadv}^*=\mathsf{DDHadv}$ (the DH-KEM with the trivial extractor H(x,y,z)=x$H(x,y,z)=x$, composed with the group one-time pad: both terms but the DDH one are 0)
  • the CCA break: the one-time pad is malleable: \mathcal A$\mathcal A$ receives \hat c=(c_1,c_2)$\hat c=(c_1,c_2)$, picks any k\ne1$k\ne1$ in \mathbb G$\mathbb G$, asks the decryption oracle for (c_1,c_2\cdot k)$(c_1,c_2\cdot k)$ (a different ciphertext, hence allowed); the answer is m_b\cdot k$m_b\cdot k$; divide by k$k$ and read off b$b$ (adv \tfrac12$\tfrac12$, i.e. it always wins)
  • generic recipe for "sketch a CCA attacker": find a malleability c\mapsto c'$c\mapsto c'$ with a known effect m\mapsto\phi(m)$m\mapsto\phi(m)$, ensure c'\ne\hat c$c'\ne\hat c$, query the oracle, invert \phi$\phi$: works for ElGamal (\cdot k$\cdot k$), CTR/OTP (\oplus\Delta$\oplus\Delta$), textbook RSA (\cdot r^e$\cdot r^e$)
  • the fix: "apply the FO transformation plus a hybrid construction with a CCA-secure symmetric scheme \Pi'$\Pi'$": name the transformation (worth a point) and show the re-encryption check (what kills malleability)
• OW-VA: one-way under validity checking attack
  • formally: like the OWTF game, but \mathcal A$\mathcal A$ may query images y_i$y_i$ and receive [[y_i=F(pk,I(sk,y_i))]]$[[y_i=F(pk,I(sk,y_i))]]$ (the image oracle); \mathsf{IOWadv}[\mathcal A,\mathcal T]:=\Pr[W]$\mathsf{IOWadv}[\mathcal A,\mathcal T]:=\Pr[W]$; negligible for all PPT ⟹ OW-VA
  • the meta-pattern: adding an interface to a game makes the attacker stronger, hence the resulting security property is stronger (OWTF → OW-VA, CPA → CCA, CDH → GDH); whenever a reduction gets stuck because the wrapper cannot answer an oracle query, the standard move is to strengthen the assumption by giving that oracle to the assumption's adversary too
  • why the CPA KEM-from-OWTF is not CCA: if \mathcal A$\mathcal A$ can find c\ne\hat c$c\ne\hat c$ with I(sk,c)=I(sk,\hat c)$I(sk,c)=I(sk,\hat c)$ (flip a bit ignored by I$I$), it decapsulates \hat c$\hat c$'s key through the oracle; the fix re-checks in D$D$ ("if F(pk,x)\ne c$F(pk,x)\ne c$ return \bot$\bot$"), but then answering decapsulation queries needs the validity bit, which the wrapper cannot compute without sk$sk$; that motivates the game
  • theorem (CCA KEM from a OW-VA trapdoor function, in the ROM): \mathsf{KEMCCAroadv}[\mathcal A,\mathcal E,Q]\le\mathsf{IOWadv}[\mathcal B,\mathcal T,Q]$\mathsf{KEMCCAroadv}[\mathcal A,\mathcal E,Q]\le\mathsf{IOWadv}[\mathcal B,\mathcal T,Q]$
  • proof shape (4 games, two of which are pure bookkeeping: a very typical exam shape): re-index the dictionary from preimages to ciphertexts (legal: unique images: gap 0) → decouple the challenge key (Z$Z$ : = "\mathcal A$\mathcal A$ queries \mathcal O(\hat x)$\mathcal O(\hat x)$"; \mathcal B$\mathcal B$ replaces the validity test by a query to its IOW challenger and detects Z$Z$ by computing F(pk,x)\stackrel{?}{=}\hat c$F(pk,x)\stackrel{?}{=}\hat c$ on each RO query) → undo the re-indexing (gap 0)
  • a OWTF is not automatically OW-VA (Bleichenbacher-style: RSA restricted to x\le n/2$x\le n/2$ with a protocol error revealing [[y^d\bmod n\le n/2]]$[[y^d\bmod n\le n/2]]$: since VO(y\cdot r^e)=[[x\cdot r\bmod n\le n/2]]$VO(y\cdot r^e)=[[x\cdot r\bmod n\le n/2]]$, one bit per chosen r$r$, binary-search x$x$); but a OWTP is: the validity oracle just checks y\in\mathcal Y$y\in\mathcal Y$, which the attacker can do itself; hence the CPA construction was already CCA-secure for permutations
• the Fujisaki–Okamoto transformation: make the randomness of the trapdoor function derived from the input via a random oracle, so that any valid ciphertext must have been "assembled" through a RO query: the reduction, which sees all RO queries, knows every valid ciphertext and can answer validity queries by rejecting everything else (no sk$sk$): the public-key analogue of ciphertext integrity
  • \gamma$\gamma$-spread: \forall(sk,pk),x,y:\ \Pr[F(pk,x)=y]\le\gamma$\forall(sk,pk),x,y:\ \Pr[F(pk,x)=y]\le\gamma$ (the randomised OWTF's output is well spread)
  • formally: F_{FO}(pk,x):=F(pk,x;H(x))$F_{FO}(pk,x):=F(pk,x;H(x))$ (probabilistic OWTF, H$H$ a RO); \mathsf{IOWroadv}[\mathcal A,\mathcal T_{FO},Q_v]\le Q_v\cdot\gamma+(Q_{ro}+1)\cdot\mathsf{OWTFadv}[\mathcal B,\mathcal T]$\mathsf{IOWroadv}[\mathcal A,\mathcal T_{FO},Q_v]\le Q_v\cdot\gamma+(Q_{ro}+1)\cdot\mathsf{OWTFadv}[\mathcal B,\mathcal T]$
  • reading the bound: Q_v\gamma$Q_v\gamma$ = an unqueried image passes the validity check by luck (\gamma$\gamma$-spread per query); (Q_{ro}+1)$(Q_{ro}+1)$ = guess which RO query holds the preimage (Pattern G; WLOG \mathcal A$\mathcal A$ queries \mathcal O(x)$\mathcal O(x)$ before outputting x$x$)
  • the simple variant (the one to default to in constructions): for deterministic F$F$, F'(pk,x):=(F(pk,x),r)$F'(pk,x):=(F(pk,x),r)$ with r\xleftarrow{R}\{0,1\}^l$r\xleftarrow{R}\{0,1\}^l$ is a OWTF and 2^{-l}$2^{-l}$-spread; together with a CCA symmetric cipher this gives a CCA PKE from any OWTF and two hashes:
    • E(pk,m)$E(pk,m)$: x\xleftarrow{R}\mathcal X$x\xleftarrow{R}\mathcal X$; c\leftarrow(F(pk,x),H_1(x))$c\leftarrow(F(pk,x),H_1(x))$; k\leftarrow H_2(x)$k\leftarrow H_2(x)$; return (c,E_s(k,m))$(c,E_s(k,m))$; D(sk,((c,r),c'))$D(sk,((c,r),c'))$: x\leftarrow I(sk,c)$x\leftarrow I(sk,c)$; if (F(pk,x),H_1(x))\ne(c,r)$(F(pk,x),H_1(x))\ne(c,r)$ return \bot$\bot$; else return D_s(H_2(x),c')$D_s(H_2(x),c')$
    • bound: \mathsf{PKCCAroadv}^*[\mathcal A,\Pi,Q]\le Q\cdot2^{-l}+\mathsf{OWTFadv}[\mathcal B_{\mathcal T},\mathcal T]+\mathsf{CCAadv}^*[\mathcal B_s,\Pi_s,0,Q]$\mathsf{PKCCAroadv}^*[\mathcal A,\Pi,Q]\le Q\cdot2^{-l}+\mathsf{OWTFadv}[\mathcal B_{\mathcal T},\mathcal T]+\mathsf{CCAadv}^*[\mathcal B_s,\Pi_s,0,Q]$: no Q_{ro}$Q_{ro}$ factor: with the separate component F(pk,x)$F(pk,x)$ the reduction can identify the right preimage by recomputing F$F$ (publicly checkable ⟹ tight); the randomness-reuse version pays (Q_{ro}+1)$(Q_{ro}+1)$ for guessing
  • FO-ElGamal (worth memorising as a ready-made answer): E(pk)$E(pk)$: x\xleftarrow{R}\mathbb G$x\xleftarrow{R}\mathbb G$, \beta\leftarrow H_1(x)$\beta\leftarrow H_1(x)$, B\leftarrow g^\beta$B\leftarrow g^\beta$, \omega\leftarrow pk^\beta$\omega\leftarrow pk^\beta$, y\leftarrow\omega\circ x$y\leftarrow\omega\circ x$; return (H_2(x),(y,B))$(H_2(x),(y,B))$; D(sk,(y,B))$D(sk,(y,B))$: \omega\leftarrow B^\alpha$\omega\leftarrow B^\alpha$, x\leftarrow\omega^{-1}\circ y$x\leftarrow\omega^{-1}\circ y$, \beta\leftarrow H_1(x)$\beta\leftarrow H_1(x)$; if (g^\beta,g^{\alpha\beta})\ne(B,\omega)$(g^\beta,g^{\alpha\beta})\ne(B,\omega)$ return \bot$\bot$; else return H_2(x)$H_2(x)$: justification: ElGamal is 1/q$1/q$-spread, and every IND-CPA PKE is one-way
• Gap Diffie–Hellman: the DH-KEM is CCA-secure under GDH (in the ROM): \mathsf{KEMCCAroadv}[\mathcal A,\mathcal E_{DH}]\le\mathsf{GDHadv}[\mathcal B,\mathbb G]$\mathsf{KEMCCAroadv}[\mathcal A,\mathcal E_{DH}]\le\mathsf{GDHadv}[\mathcal B,\mathbb G]$
  • how the two obstacles are removed: (1) decapsulation without \alpha$\alpha$: in the ROM, decapsulating b\ne B$b\ne B$ may just return a fresh random key per b$b$, staying consistent if \mathcal A$\mathcal A$ later asks H(b^\alpha,A,b)$H(b^\alpha,A,b)$ (bookkeeping game, gap 0); (2) recognising the winning RO query: testing whether a query (w,a,b)$(w,a,b)$ is a real DH triple is exactly a DDH oracle, which the GDH game provides; Z$Z$ : = the query (w,a,b)=(\hat w,A,B)$(w,a,b)=(\hat w,A,B)$ happens; \mathcal B$\mathcal B$ aborts and returns w$w$ ⟹ \mathsf{GDHadv}\ge\Pr[Z]$\mathsf{GDHadv}\ge\Pr[Z]$
  • application: this is how RFC 9180 (HPKE) can use plain DH-KEM where an IND-CCA2 KEM is required
• the public-key map (memorise the arrows: the exam's construction task is always a single arrow, the one-liners always a path):

  DH / EC-isogenies / LWE ─[RO or DDH+extractor]→ CPA-secure KEM
  OWTF (OW-CPA) ─[RO]→ CPA-secure KEM
  OWTP ─ Blum–Micali chain, NO RO → CPA-secure KEM
  OWTF ─ FO transform → OW-VA OWTF ─[RO]→ CCA-secure KEM
  OWTP ─ (trivially OW-VA) ─[RO]→ CCA-secure KEM
  DH ─ [GDH, RO] → CCA-secure KEM
  CPA KEM + sem.-secure cipher ─ hybrid → CPA-secure PKE
  CCA KEM + CCA symmetric cipher ─ hybrid → CCA-secure PKE
  OWTP + RO ─ Full Domain Hash → SUF-CMA signatures
  OWF ─ Lamport → containment-free → hash → tree → (S)UF-CMA signatures

  DH / EC-isogenies / LWE ─[RO or DDH+extractor]→ CPA-secure KEM
  OWTF (OW-CPA) ─[RO]→ CPA-secure KEM
  OWTP ─ Blum–Micali chain, NO RO → CPA-secure KEM
  OWTF ─ FO transform → OW-VA OWTF ─[RO]→ CCA-secure KEM
  OWTP ─ (trivially OW-VA) ─[RO]→ CCA-secure KEM
  DH ─ [GDH, RO] → CCA-secure KEM
  CPA KEM + sem.-secure cipher ─ hybrid → CPA-secure PKE
  CCA KEM + CCA symmetric cipher ─ hybrid → CCA-secure PKE
  OWTP + RO ─ Full Domain Hash → SUF-CMA signatures
  OWF ─ Lamport → containment-free → hash → tree → (S)UF-CMA signatures

Signatures

• setting: against a fully active adversary, PKE alone is hopeless (Mallory replaces pk$pk$); fix: a trusted third party that attests key ownership before Alice and Bob talk: certificates \mathrm{Cert}_{id}=(id,pk,\sigma)$\mathrm{Cert}_{id}=(id,pk,\sigma)$; that attestation is a signature (ids assumed unique)
• signature scheme: \mathcal S=(G,S,V)$\mathcal S=(G,S,V)$ over (\mathcal M,\mathcal T)$(\mathcal M,\mathcal T)$; (sk,pk)\xleftarrow{R}G()$(sk,pk)\xleftarrow{R}G()$; \sigma\xleftarrow{R}S(sk,m)$\sigma\xleftarrow{R}S(sk,m)$, \sigma\in\mathcal T$\sigma\in\mathcal T$; v\leftarrow V(pk,m,\sigma)\in\{\text{accept},\text{reject}\}$v\leftarrow V(pk,m,\sigma)\in\{\text{accept},\text{reject}\}$; correctness: V(pk,m,\sigma)=\text{accept}$V(pk,m,\sigma)=\text{accept}$ for all honestly produced \sigma$\sigma$
  • game: signing queries m_i\mapsto\sigma_i\xleftarrow{R}S(sk,m_i)$m_i\mapsto\sigma_i\xleftarrow{R}S(sk,m_i)$; then a forgery (\hat m,\hat\sigma)$(\hat m,\hat\sigma)$
  • EUF-CMA: wins if accept and \hat m\notin\{m_i\}$\hat m\notin\{m_i\}$: a new message; \mathsf{SIGadv}[\mathcal A,\mathcal S]$\mathsf{SIGadv}[\mathcal A,\mathcal S]$
  • SUF-CMA: wins if accept and (\hat m,\hat\sigma)\notin\{(m_i,\sigma_i)\}$(\hat m,\hat\sigma)\notin\{(m_i,\sigma_i)\}$: a new pair; \mathsf{stSIGadv}[\mathcal A,\mathcal S]$\mathsf{stSIGadv}[\mathcal A,\mathcal S]$
  • note: a deterministic scheme with exactly one valid signature per message makes EUF-CMA ⟺ SUF-CMA (used for FDH)
• why the naive "sign = invert" fails: S(sk,m):=I(sk,m)$S(sk,m):=I(sk,m)$, V(pk,m,\sigma):=[[F(pk,\sigma)=m]]$V(pk,m,\sigma):=[[F(pk,\sigma)=m]]$
  • universal forgery for free: pick any \sigma$\sigma$; it is a valid signature for the message m=F(pk,\sigma)$m=F(pk,\sigma)$
  • multiplicative RSA: if \sigma$\sigma$ signs m$m$, then \sigma r^e$\sigma r^e$ signs m r^e$m r^e$
  • in other words (lesson stated explicitly on the slides): read the security definition: one-wayness only says "hard to invert on a uniformly random image"; force the message to be hashed to a random image
• Full Domain Hash: OWTP \mathcal T=(G,F,I)$\mathcal T=(G,F,I)$ + H$H$ modelled as a random oracle
  • formally: S(sk,m):=I(sk,H(m))$S(sk,m):=I(sk,H(m))$, V(pk,m,\sigma):=[[F(pk,\sigma)=H(m)]]$V(pk,m,\sigma):=[[F(pk,\sigma)=H(m)]]$; correctness: F(pk,I(sk,H(m)))=H(m)$F(pk,I(sk,H(m)))=H(m)$
  • bound: \mathsf{stSIGroadv}[\mathcal A,\mathcal S_{FDH}]\le(Q_{ro}+1)\cdot\mathsf{OWTFadv}[\mathcal B,\mathcal T]$\mathsf{stSIGroadv}[\mathcal A,\mathcal S_{FDH}]\le(Q_{ro}+1)\cdot\mathsf{OWTFadv}[\mathcal B,\mathcal T]$ (SUF-CMA in the ROM)
  • why the hash: with it, "pick \sigma$\sigma$ first" requires a preimage of a random oracle, and "from \sigma$\sigma$ for m$m$ get \sigma r^e$\sigma r^e$ for mr^e$mr^e$" requires H(m)\cdot r^e$H(m)\cdot r^e$ to be H(m')$H(m')$ for a message you can name: the hash forces inversion at a uniformly random point, exactly the precondition of the one-wayness game
  • proof (memorise the simulation subroutine: it is the whole trick):
    1. WLOG \mathcal A$\mathcal A$ makes an RO query on its output message ⟹ at most Q_{ro}+1$Q_{ro}+1$ RO queries; since V$V$ accepts only one signature per message, strong = existential here
    2. G_1$G_1$: sample images together with their preimages (sign without sk$sk$): Sim(): x←R X; y←F(pk,x); I[y]←x; return y; every H[m]$H[m]$ is produced by Sim() and signing returns I[H[m_i]]$I[H[m_i]]$; because F(pk,\cdot)$F(pk,\cdot)$ is a permutation, y$y$ is uniform, so \mathcal A$\mathcal A$'s view is unchanged: \Pr[W_0]=\Pr[W_1]$\Pr[W_0]=\Pr[W_1]$
    3. \mathcal B$\mathcal B$ plants the challenge at a guessed position: \omega\xleftarrow{R}\{0,\dots,Q_{ro}\}$\omega\xleftarrow{R}\{0,\dots,Q_{ro}\}$; answer the \omega$\omega$-th RO query with the challenge image \hat y$\hat y$, all others with Sim(); signing queries answered from I[\cdot]$I[\cdot]$: fails only if \mathcal A$\mathcal A$ asks a signature for the \omega$\omega$-planted message, i.e. only if \omega$\omega$ was not the forgery message; with probability \frac1{Q_{ro}+1}$\frac1{Q_{ro}+1}$ the simulation is perfect and \hat\sigma$\hat\sigma$ is a preimage of \hat y$\hat y$ ⟹ \mathsf{OWTFadv}[\mathcal B]\ge\frac{\Pr[W_1]}{Q_{ro}+1}$\mathsf{OWTFadv}[\mathcal B]\ge\frac{\Pr[W_1]}{Q_{ro}+1}$ ∎
  • two transferable ideas: (1) programming the random oracle: choose x$x$ first and set H(m):=F(pk,x)$H(m):=F(pk,x)$: a valid signature for free; (2) plant the challenge at a random index: the standard way to embed a single hard instance into a game with many opportunities; always costs a factor equal to the number of positions
  • exam: "SUF-CMA signature from a OWTP" = exactly FDH, and you must mark H$H$ as a random oracle; one-liner: "FDH with a OWTP is always SUF-CMA" = true (exactly one valid \sigma$\sigma$ per message: \sigma=I(sk,H(m))$\sigma=I(sk,H(m))$ and F$F$ is a bijection)
• hash-based signatures (no random oracle, only OWFs: arguably a symmetric primitive that happens to be publicly verifiable); the ladder, each rung fixing exactly one deficiency of the rung below:
  1. Lamport (one-time, small message space \mathcal M=\{m_1,\dots,m_{|\mathcal M|}\}$\mathcal M=\{m_1,\dots,m_{|\mathcal M|}\}$): G()$G()$: x_i\xleftarrow{R}\mathcal X$x_i\xleftarrow{R}\mathcal X$, y_i\leftarrow f(x_i)$y_i\leftarrow f(x_i)$ for every i$i$; pk=(y_1,\dots)$pk=(y_1,\dots)$, sk=(x_1,\dots)$sk=(x_1,\dots)$; S(sk,m_i)=x_i$S(sk,m_i)=x_i$ (signing just reveals the matching preimage); V(pk,m_i,\sigma)=[[f(\sigma)=y_i]]$V(pk,m_i,\sigma)=[[f(\sigma)=y_i]]$
     • \mathsf{SIGadv}[\mathcal A,\mathcal S]\le|\mathcal M|\cdot\mathsf{OWFadv}[\mathcal B,f]$\mathsf{SIGadv}[\mathcal A,\mathcal S]\le|\mathcal M|\cdot\mathsf{OWFadv}[\mathcal B,f]$; strong: \mathsf{stSIGadv}\le|\mathcal M|(\mathsf{OWFadv}[\mathcal B,f]+\mathsf{SPRadv}[\mathcal C,f])$\mathsf{stSIGadv}\le|\mathcal M|(\mathsf{OWFadv}[\mathcal B,f]+\mathsf{SPRadv}[\mathcal C,f])$
     • both reductions plant the challenge at a random slot \omega$\omega$: existential: overwrite y_\omega\leftarrow y^*$y_\omega\leftarrow y^*$ from the OWF challenger; if \omega=i^*$\omega=i^*$ (probability \frac1{|\mathcal M|}$\frac1{|\mathcal M|}$) and the forgery is on a new message, \mathcal B$\mathcal B$ never revealed x_\omega$x_\omega$ and outputs the preimage; strong: overwrite x_\omega\leftarrow x^*$x_\omega\leftarrow x^*$ from the SPR challenger and y_\omega\leftarrow f(x^*)$y_\omega\leftarrow f(x^*)$ (a new signature on an already-signed message is a second preimage of y_\omega$y_\omega$)
     • strictly one-time: once x_i$x_i$ is public, anyone can re-sign m_i$m_i$
  2. containment-free encoding: P:\mathcal M\to2^{\mathcal M'}$P:\mathcal M\to2^{\mathcal M'}$ is containment-free if \forall m\ne m': P(m)\not\subseteq P(m')$\forall m\ne m': P(m)\not\subseteq P(m')$; canonical: P(x):=\{2i+x_i : i<n\}$P(x):=\{2i+x_i : i<n\}$: the classic Lamport "two keys per bit" layout
     • in other words: slot 2i$2i$ is used when bit i$i$ is 0, slot 2i+1$2i+1$ when it is 1: every P(x)$P(x)$ holds exactly one of \{2i,2i+1\}$\{2i,2i+1\}$ for each i$i$; two distinct strings differ in some bit, so each set contains a slot the other lacks: no containment in either direction; signing x$x$ reveals exactly the n$n$ secrets of P(x)$P(x)$; any other x'$x'$ needs at least one secret never revealed
     • theorem: one-time scheme S_1$S_1$ signs every element of P(m)$P(m)$: \mathsf{SIGadv}[\mathcal A,\mathcal S_1,1]\le\mathsf{SIGadv}[\mathcal B,\mathcal S]$\mathsf{SIGadv}[\mathcal A,\mathcal S_1,1]\le\mathsf{SIGadv}[\mathcal B,\mathcal S]$ (and likewise strong): no loss factor: any forgery for \mathcal S_1$\mathcal S_1$ contains a forgery for the base scheme (new base-message, or a differing component signature)
  3. hash first (arbitrary-length messages): S_H(sk,m):=S_1(sk,H(m))$S_H(sk,m):=S_1(sk,H(m))$ with H$H$ collision resistant (also from a UOWHF, buildable from any OWF): \mathsf{(st)SIGadv}[\mathcal A,\mathcal S_H,1]\le\mathsf{(st)SIGadv}[\mathcal B,\mathcal S_1,1]+\mathsf{CRadv}[\mathcal C,H]$\mathsf{(st)SIGadv}[\mathcal A,\mathcal S_H,1]\le\mathsf{(st)SIGadv}[\mathcal B,\mathcal S_1,1]+\mathsf{CRadv}[\mathcal C,H]$: same event split as hash-then-MAC
  4. key tree (many messages): depth d$d$, branching b$b$ with b^d$b^d$ super-poly; all key material PRF-derived (G_{sk}(\cdot):=G(;F(sk,\cdot))$G_{sk}(\cdot):=G(;F(sk,\cdot))$); signing picks a random leaf l\xleftarrow{R}\mathbb Z_b^d$l\xleftarrow{R}\mathbb Z_b^d$; each inner node signs the tuple of its children's public keys; the leaf signs m$m$; the signature is the whole path (the indices, the public keys, and every signature along it)
     • theorem: \mathsf{(st)SIGadv}[\mathcal A,\mathcal S^*,Q]\le(Qbd{+}1)\cdot\mathsf{(st)SIGadv}[\mathcal B,\mathcal S]+\mathsf{PRFadv}[\mathcal C,F]+\frac{Q^2}{2b^d}$\mathsf{(st)SIGadv}[\mathcal A,\mathcal S^*,Q]\le(Qbd{+}1)\cdot\mathsf{(st)SIGadv}[\mathcal B,\mathcal S]+\mathsf{PRFadv}[\mathcal C,F]+\frac{Q^2}{2b^d}$
     • one term per simplification: (Qbd+1)$(Qbd+1)$ = guess which of the \le Qbd+1$\le Qbd+1$ generated public keys the forgery attacks (any forgery path must, at some node, contain a signature under a challenger-generated key on something the challenger never signed); \mathsf{PRFadv}$\mathsf{PRFadv}$ = pretend keys are generated by fresh randomness (inputs distinct per node); \frac{Q^2}{2b^d}$\frac{Q^2}{2b^d}$ = pretend leaves are never reused (birthday bound)
     • in other words: the post-quantum-relevant construction: needs only a hash function (optimisations: Merkle trees to compress public keys, Winternitz, HORS/FORS ⟹ SPHINCS+)
• hash-then-sign: S'(sk,m)=S(sk,H(m))$S'(sk,m)=S(sk,H(m))$; \Pr[W_f]=\underbrace{\Pr[W_f\cap W_c]}_{\le\mathsf{CRadv}[\mathcal B,H]}+\underbrace{\Pr[W_f\setminus W_c]}_{\le\mathsf{stSIGadv}[\mathcal C,\mathcal S,Q]}$\Pr[W_f]=\underbrace{\Pr[W_f\cap W_c]}_{\le\mathsf{CRadv}[\mathcal B,H]}+\underbrace{\Pr[W_f\setminus W_c]}_{\le\mathsf{stSIGadv}[\mathcal C,\mathcal S,Q]}$ with W_c$W_c$ : = "some m_i\ne m^*$m_i\ne m^*$ has H(m_i)=H(m^*)$H(m_i)=H(m^*)$"; the game-based variant: a second game whose winning event is W_f\setminus W_c$W_f\setminus W_c$
• compressed public keys: pk'=H(pk)$pk'=H(pk)$ published; the signature carries the real pk$pk$; verification checks H(pk)=pk'$H(pk)=pk'$ first
  • write the challenger explicitly (Setup/Sign/Forgery): explicitly requested, worth points; split on E$E$ : = "pk^*=pk$pk^*=pk$": W\setminus E$W\setminus E$ ⟹ (pk,pk^*)$(pk,pk^*)$ is an H$H$-collision ⟹ \mathsf{CRadv}[\mathcal B,H]\ge\Pr[W\setminus E]$\mathsf{CRadv}[\mathcal B,H]\ge\Pr[W\setminus E]$; W\cap E$W\cap E$ ⟹ (m^*,\sigma^*)$(m^*,\sigma^*)$ is a genuine forgery ⟹ \mathsf{SIGadv}[\mathcal C,\mathcal S']\ge\Pr[W\cap E]$\mathsf{SIGadv}[\mathcal C,\mathcal S']\ge\Pr[W\cap E]$; total \le\mathsf{CRadv}+\mathsf{SIGadv}$\le\mathsf{CRadv}+\mathsf{SIGadv}$ ∎
• multi-key / T-try generalisations: "the real attacker has more chances than the textbook game", all solved by the same two moves:
  • N$N$-key signatures (N$N$ public keys, forge under any): \mathsf{MKSIGadv}\le N\cdot\mathsf{SIGadv}$\mathsf{MKSIGadv}\le N\cdot\mathsf{SIGadv}$: guess \omega\xleftarrow{R}\mathbb Z_N$\omega\xleftarrow{R}\mathbb Z_N$, plant pk^*$pk^*$ at slot \omega$\omega$, generate the other N-1$N-1$ pairs yourself (so you can answer their signing queries); win iff i^*=\omega$i^*=\omega$
  • T$T$-try MAC (attacker outputs T$T$ candidate pairs): \mathsf{TMACadv}\le T\cdot\mathsf{MACadv}$\mathsf{TMACadv}\le T\cdot\mathsf{MACadv}$: guess the \omega$\omega$-th pair; you must guess because MAC validity is not publicly checkable
  • T$T$-try signatures: \mathsf{TSIGadv}\le\mathsf{SIGadv}$\mathsf{TSIGadv}\le\mathsf{SIGadv}$: no factor T$T$: verify locally (pk$pk$ is public; run V$V$ on all T$T$ pairs, submit the first valid one)
  • multi-target OWF: \le N\cdot\mathsf{OWFadv}$\le N\cdot\mathsf{OWFadv}$ (guess the index, plant the challenge image); multi-target discrete log: \le\mathsf{OWFadv}$\le\mathsf{OWFadv}$: no factor N$N$: re-randomise one instance into N$N$ (y_i:=y^{r_i}$y_i:=y^{r_i}$, r_i\xleftarrow{R}[q-1]$r_i\xleftarrow{R}[q-1]$: i.i.d. uniform; if \mathcal A$\mathcal A$ returns x^*$x^*$ with y^{r_i}=g^{x^*}$y^{r_i}=g^{x^*}$, output x^*/r_i$x^*/r_i$; always wins)
  • the decisive question: can the reduction tell which of the several opportunities is the successful one?: yes, the check is public (signature verification, F(pk,x)\stackrel{?}{=}y$F(pk,x)\stackrel{?}{=}y$) ⟹ tight, factor 1; no, the check needs a secret (MAC verification, "which RO query is the CDH answer") ⟹ guess: factor T/N/Q$T/N/Q$; or use algebraic self-reducibility to make all N$N$ targets copies of one ⟹ factor 1

BONUS: Proof techniques

• the master template: the 13–15 point task is always three sub-tasks, written as three clearly separated blocks: (1) challenger pseudocode for each game (Setup(), one block per oracle, Challenge()/Forgery(); later games as diffs); (2) one bullet per gap: a wrapper (who, what it outsources, what it outputs, query count) or a difference-lemma argument (Z$Z$, why the games coincide unless Z$Z$, \Pr[Z]$\Pr[Z]$); (3) bound the last game directly, telescope with the triangle inequality, end with "by our assumptions this value is negligible"
  • the canonical final computation, in the exact form (state which form you use: mixing them silently loses a factor 2):
    • bit-guessing (CPA, CCA, KEM, semantic security): \mathsf{Xadv}^*[\mathcal A,\Pi]:=\big|\Pr[W_0]-\tfrac12\big|=|\Pr[W_0]-\Pr[W_n]|\le\sum_{i=0}^{n-1}|\Pr[W_i]-\Pr[W_{i+1}]|\le\cdots$\mathsf{Xadv}^*[\mathcal A,\Pi]:=\big|\Pr[W_0]-\tfrac12\big|=|\Pr[W_0]-\Pr[W_n]|\le\sum_{i=0}^{n-1}|\Pr[W_i]-\Pr[W_{i+1}]|\le\cdots$
    • winning-event (MAC, signatures, CI, UHF, CR): \mathsf{Xadv}[\mathcal A,\Pi]:=\Pr[W_0]\le\sum_i|\Pr[W_i]-\Pr[W_{i+1}]|+\Pr[W_n]\le\cdots$\mathsf{Xadv}[\mathcal A,\Pi]:=\Pr[W_0]\le\sum_i|\Pr[W_i]-\Pr[W_{i+1}]|+\Pr[W_n]\le\cdots$
    • two-experiment (walk m_0$m_0$ → middle → m_1$m_1$): \mathsf{Xadv}[\mathcal A,\Pi]:=|\Pr[W_0]-\Pr[W_n]|\le\sum_i|\Pr[W_i]-\Pr[W_{i+1}]|\le\cdots$\mathsf{Xadv}[\mathcal A,\Pi]:=|\Pr[W_0]-\Pr[W_n]|\le\sum_i|\Pr[W_i]-\Pr[W_{i+1}]|\le\cdots$
  • switching between the two forms: for every notion in this course \mathsf{Xadv}=2\cdot\mathsf{Xadv}^*$\mathsf{Xadv}=2\cdot\mathsf{Xadv}^*$ (because \Pr[W]=\tfrac12(1-\Pr[W_0]+\Pr[W_1])$\Pr[W]=\tfrac12(1-\Pr[W_0]+\Pr[W_1])$); use bit-guessing if the chain ends "the view is independent of b$b$ ⟹ \Pr[W_n]=\tfrac12$\Pr[W_n]=\tfrac12$"; two-experiment if the chain ends at literally the other experiment (then walk there and back)
• pattern R: the reduction / wrapper (used in ~90% of all steps):
  • when: two consecutive games differ by replacing a primitive with its idealised version (PRF → random function, PRP → random permutation, real key → random key, real ciphertext → encryption of the other message); \mathcal B$\mathcal B$ sits between the worlds: to \mathcal A$\mathcal A$ it looks like one game's challenger, to its own challenger like an ordinary attacker: and \mathcal B$\mathcal B$'s code does not change between the two cases, only which experiment its challenger runs
  • the five things to write: (1) name and target ("\mathcal B$\mathcal B$ is an adversary in Attack Game X against F$F$, runs \mathcal A$\mathcal A$ as a subroutine"); (2) what \mathcal B$\mathcal B$ does itself (including generating the keys it may know); (3) what it outsources; (4) the perfect-simulation claim (Exp. 0 ⟹ exactly Game i$i$, Exp. 1 ⟹ exactly Game i{+}1$i{+}1$); (5) output rule + conclusion + query count
  • the output rule: distinguisher-in/distinguisher-out ⟹ echo \hat b$\hat b$; \mathcal A$\mathcal A$ bit-guessing (\mathcal B$\mathcal B$ chose b$b$), \mathcal B$\mathcal B$ distinguishes ⟹ [[\hat b=b]]$[[\hat b=b]]$; \mathcal A$\mathcal A$ forges, \mathcal B$\mathcal B$ distinguishes ⟹ [[\text{the forgery verifies}]]$[[\text{the forgery verifies}]]$ (one extra query); \mathcal B$\mathcal B$ must forge ⟹ the (transformed) forgery, e.g. (H(\hat m),\hat t)$(H(\hat m),\hat t)$
  • legality checklist: only information \mathcal B$\mathcal B$ legitimately has (never k,sk$k,sk$, never its challenger's experiment); can answer every oracle query (if one is unanswerable, that is the reason a stronger primitive is needed: how CCA-KEM, OW-VA, GDH were invented); PPT; query count stated
  • sub-move: programming the RO: the reduction owns the hash; sample the answer with a witness (pick x$x$, set \mathcal O(m):=F(pk,x)$\mathcal O(m):=F(pk,x)$: still uniform since F$F$ is a permutation, but now you can sign without sk$sk$: the Sim() of FDH); or plant the challenge at one guessed query (you cannot answer a signing query for that message (fine exactly when it is the forgery message))
  • detecting the bad event for free: if the relation is publicly checkable, test every RO query ("if F(pk,x)=c$F(pk,x)=c$ output x$x$ and stop"): why the OWTF-KEM pays no Q_{ro}$Q_{ro}$ factor while the CDH proof does
• pattern H: hybrids (when the gap has n$n$ copies):
  • when: games 0 and n$n$ differ in n$n$ independent places (parallel PRGs, tree nodes, Feistel rounds, N$N$ keys) but a challenger only hands over one value: take n$n$ small steps, each swapping one copy; the walk length is where the factor n$n$ comes from
  • skeleton: (1) Hybrid \gamma$\gamma$: first \gamma$\gamma$ instances ideal, rest real; (2) verify the endpoints (Hybrid 0 = Exp. 0, Hybrid n$n$ = Exp. 1: worth points); (3) \mathcal B_i$\mathcal B_i$: ideal for j<i$j<i$, the challenger's value at position i$i$, real for j>i$j>i$, echo \mathcal A$\mathcal A$; (4) Exp. 0 ⟹ Hybrid i$i$, Exp. 1 ⟹ Hybrid i{+}1$i{+}1$ ⟹ |p_i-p_{i+1}|$|p_i-p_{i+1}|$; (5) telescope \le n\cdot\max_i$\le n\cdot\max_i$
  • signature in a theorem statement: a leading factor n$n$, 4$4$, Ql$Ql$, Qbd{+}1$Qbd{+}1$, …
• pattern D: the difference lemma (statistical steps):
  • formally: if W_0\cap\bar Z$W_0\cap\bar Z$ occurs iff W_1\cap\bar Z$W_1\cap\bar Z$ occurs, then |\Pr[W_0]-\Pr[W_1]|\le\Pr[Z]$|\Pr[W_0]-\Pr[W_1]|\le\Pr[Z]$
  • when: the change is "tweaked the sampling / removed a rare special case": collisions, nonce reuse, guessing a secret, an invalid ciphertext accidentally valid; the games are identical unless an unlucky coincidence occurs; you concede the whole mass of Z$Z$ (a crude union bound is fine)
  • the three sentences to write: (1) "let Z$Z$ be the event that …" (precise); (2) "unless Z$Z$, both challengers behave identically, because …"; (3) "\Pr[Z]\le\dots$\Pr[Z]\le\dots$" (counting)
  • the standard counts (know these cold): fresh value hits one of Q$Q$ fixed values in a space of size N$N$ ⟹ Q/N$Q/N$ (linear); collision among Q$Q$ values ⟹ \binom Q2/N\le\frac{Q^2}{2N}$\binom Q2/N\le\frac{Q^2}{2N}$ (birthday); Q$Q$ counter windows of width l$l$ overlap ⟹ \le\frac{2Ql}{N}$\le\frac{2Ql}{N}$ (rCTR); guessing a secret with Q_{ro}$Q_{ro}$ queries ⟹ Q_{ro}/|\mathcal K|$Q_{ro}/|\mathcal K|$ or Q_{ro}/|\mathcal X|$Q_{ro}/|\mathcal X|$; an invalid image passes a \gamma$\gamma$-spread check ⟹ Q_v\gamma$Q_v\gamma$ (FO); several independent causes ⟹ union bound
  • when a probability term appears at all: exactly when you rewrite the challenger so it stops doing bookkeeping (table lookup) and starts drawing fresh randomness: the real scheme is consistent, the ideal one forgetful; they diverge exactly when an input repeats, and the probability of that repeat is your term; no lookup→fresh-draw change, no term owed
  • the four questions that produce the number: (1) what did I just start sampling freshly? (2) what must coincide: a fresh value hitting one particular stored value (or one of Q$Q$) ⟹ linear in Q$Q$; any two of Q$Q$ values, no pair named ⟹ quadratic (birthday); answer this out loud before writing the fraction (3) how many chances? Q$Q$, \binom Q2$\binom Q2$, or Q(2l-1)$Q(2l-1)$; (4) probability of one chance? almost always 1/N$1/N$, N$N$ = size of the space the value is drawn from; multiply (union bound)
  • the three mistakes: writing Q^2$Q^2$ where the count is \binom Q2$\binom Q2$ (keep the \tfrac12$\tfrac12$); forgetting a collision needs two values per query (Luby–Rackoff: per-query count 2i$2i$, giving Q^2-Q$Q^2-Q$); charging a term for a bookkeeping-only change (gap exactly 0, Pattern B: say so, worth marks)
• pattern G: guess the index (where all the loss factors come from):
  • when: you know some query/key/position is the successful one, but your reduction can only submit one answer and cannot recognise which; pick \omega\xleftarrow{R}\{0..N-1\}$\omega\xleftarrow{R}\{0..N-1\}$ before the game, simulate faithfully, at position \omega$\omega$ submit/plant
  • the conclusion, verbatim: "given Z$Z$, \omega$\omega$ is right with probability 1/N$1/N$, and in that case \mathcal B$\mathcal B$ wins; hence \mathsf{adv}[\mathcal B]\ge\Pr[Z]/N$\mathsf{adv}[\mathcal B]\ge\Pr[Z]/N$, i.e. \Pr[Z]\le N\cdot\mathsf{adv}[\mathcal B]$\Pr[Z]\le N\cdot\mathsf{adv}[\mathcal B]$" (for an unordered pair of indices, two draws hit with probability 2/Q^2$2/Q^2$: the \frac{Q^2}{2}$\frac{Q^2}{2}$ in PRF∘UHF)
  • catalogue: Q_d$Q_d$ = which decryption query is the first forgery (AE ⟹ CCA); Q$Q$ = which RO query contains the CDH secret (DH-KEM under CDH); Q_{ro}+1$Q_{ro}+1$ = at which RO query to plant (FDH, FO); Q^2/2$Q^2/2$ = which pair of queries collides (PRF∘UHF); N$N$/T$T$/|\mathcal M|$|\mathcal M|$/ Qbd{+}1$Qbd{+}1$ = which key / which of T$T$ forgeries / which slot / which tree node
  • always ask first: can I avoid the guess?: publicly checkable candidate ⟹ verify locally, tight factor 1 (signature verification, F(pk,x)\stackrel{?}{=}c$F(pk,x)\stackrel{?}{=}c$, a DDH oracle, re-randomisation); exam tasks asking "\le T\cdot\mathsf{adv}$\le T\cdot\mathsf{adv}$" vs "\le\mathsf{adv}$\le\mathsf{adv}$" test exactly this distinction
• pattern E: event splitting (no games needed):
  • when: one win can arise for two mutually exclusive reasons, each breaking a different primitive; symptom: the bound is a sum of two different advantages, no factor (\mathsf{MACadv}+\mathsf{CRadv}$\mathsf{MACadv}+\mathsf{CRadv}$)
  • skeleton: define the win W$W$ and the case event E$E$ (usually "a collision happened" or "the attacker used the honest pk$pk$"); \Pr[W]=\Pr[W\cap E]+\Pr[W\setminus E]$\Pr[W]=\Pr[W\cap E]+\Pr[W\setminus E]$; one adversary per branch, each wins whenever its branch occurs; add up
  • instances: hash-then-MAC / hash-then-sign (collision vs. genuine forgery); compressed public keys (pk^*=pk$pk^*=pk$ vs. \ne$\ne$); "r^*$r^*$ appeared twice / at most once"
  • equivalent game-based phrasing (also accepted): a second game whose winning event is W\setminus E$W\setminus E$, gap bounded by \Pr[E\cap W]$\Pr[E\cap W]$ via the difference lemma
• pattern B: bookkeeping-only games (free steps, worth points):
  • when: a game changes nothing the adversary could ever observe: only how the challenger keeps its records; the transcripts are identically distributed, so the gap is exactly 0, no assumption invoked
  • write: "this game only changes internal bookkeeping; \mathcal A$\mathcal A$'s view is identically distributed, hence \Pr[W_i]=\Pr[W_{i+1}]$\Pr[W_i]=\Pr[W_{i+1}]$"
  • instances: re-index a dictionary from preimages x$x$ to ciphertexts c$c$ (CCA KEM from OWTF: valid because F(pk,\cdot)$F(pk,\cdot)$ is injective); sample images together with preimages via Sim() (FDH: valid because F$F$ is a permutation, so y$y$ stays uniform); replace "lazy random function" by "fresh randoms, reusing on collision" (Luby–Rackoff G_5$G_5$, PRF∘UHF G_1$G_1$); index the RO by b$b$ only instead of the full triple (GDH proof)
  • why they matter: they usually remove the secret key from the challenger's code: which is what the next step needs (once sk$sk$ no longer appears anywhere, the challenger can be run by a reduction that does not know it); heuristic: your chain is finished when sk$sk$/k$k$ no longer appears anywhere in the challenger
• meta-pattern: when the reduction gets stuck, strengthen the assumption: if your wrapper cannot answer an oracle query, that is not a dead end: it is the method for discovering the right assumption; give the missing capability to the assumption's adversary and re-run the proof:
  • wrapper cannot decide whether a ciphertext is valid (needs sk$sk$) ⟹ OWTF → OW-VA (adds an image oracle): used for the CCA KEM from OWTF
  • wrapper cannot decapsulate c_k\ne\hat c_k$c_k\ne\hat c_k$ ⟹ KEM-CPA → KEM-CCA (adds a decapsulation oracle): CCA hybrid PKE
  • wrapper cannot recognise the real DH triple among RO queries ⟹ CDH → GDH (adds a DDH oracle): CCA DH-KEM
  • wrapper cannot decrypt c_s$c_s$ under the challenge key ⟹ sem.-security → CCA for the symmetric part: CCA hybrid PKE
  • say it out loud in the exam if a construction is not provable as given: "the reduction would need an oracle for X, so either the primitive must satisfy the stronger notion Y, or the construction must be changed (e.g. by adding a re-encryption check)": that is the reasoning the FO transformation is built on
• choosing the games: a decision procedure for a scheme you have never seen (the blank page):
  1. Game 0 = the definition, with the construction inlined into the challenger; note which advantage it equals
  2. list every primitive in the construction: you will need roughly one game per primitive, plus one per rare-event cleanup
  3. idealise in dependency order: the primitive whose output feeds the others goes first (KEM combiner: k_1$k_1$ from \mathcal E_1$\mathcal E_1$ → then the PRF H'$H'$ that eats k_1$k_1$ → then the CRHF H$H$)
  4. after each idealisation ask: "does some other part of the challenger recompute this value?": if yes, patch that branch in the same game (the "if c=c^*$c=c^*$" rule: forgetting it is the most common lost point)
  5. add cleanup games for anything now random-but-possibly-repeating (nonce collisions, hash collisions, counter overlaps ⟹ difference lemma): this is the step that generates the Q/N$Q/N$ and Q^2/2N$Q^2/2N$ terms
  6. stop when the challenge is information-theoretically independent of b$b$ (⟹ \Pr[W_n]=\tfrac12$\Pr[W_n]=\tfrac12$) or when winning requires predicting a fresh random value (⟹ \Pr[W_n]\le\frac1{|\mathcal T|}$\Pr[W_n]\le\frac1{|\mathcal T|}$ or \frac1{|\mathcal X|-q}$\frac1{|\mathcal X|-q}$)
  7. assemble with the triangle inequality and state negligibility
  • in other words: a game chain is nothing more than a list of lies you tell the adversary, each one small enough that it cannot notice, arranged so that after the last lie the challenge carries no information about b$b$ at all
• reading a theorem statement backwards (the shape of the bound tells you the proof; use it when the exam gives you the target bound):
  • \mathsf{PRFadv}[\mathcal B,F,Q{+}1]$\mathsf{PRFadv}[\mathcal B,F,Q{+}1]$ ⟹ a wrapper that idealises F$F$ and spends one extra query to check the forgery
  • n\cdot\mathsf{adv}$n\cdot\mathsf{adv}$, 4\cdot\mathsf{adv}$4\cdot\mathsf{adv}$, Ql\cdot\mathsf{adv}$Ql\cdot\mathsf{adv}$ ⟹ a hybrid over n$n$ instances
  • T\cdot\mathsf{adv}$T\cdot\mathsf{adv}$, Q_d\cdot\mathsf{adv}$Q_d\cdot\mathsf{adv}$, (Q_{ro}{+}1)\cdot\mathsf{adv}$(Q_{ro}{+}1)\cdot\mathsf{adv}$ ⟹ guess-the-index
  • \frac{Q^2}{2N}$\frac{Q^2}{2N}$, \frac{Q}{N}$\frac{Q}{N}$, \frac{2Ql}{|\mathcal X|}$\frac{2Ql}{|\mathcal X|}$, Q_v\gamma$Q_v\gamma$ ⟹ difference lemma + counting
  • \mathsf{adv}_A+\mathsf{adv}_B$\mathsf{adv}_A+\mathsf{adv}_B$ (different primitives, no factors) ⟹ event split, or two consecutive independent game hops
  • \frac1{|\mathcal T|}$\frac1{|\mathcal T|}$, \frac1{|\mathcal X|-q}$\frac1{|\mathcal X|-q}$, \epsilon$\epsilon$ ⟹ the direct bound on the final game (guessing a random value)
  • an equality "=$=$" rather than "\le$\le$" ⟹ a single perfect reduction, no losses (EtM, stream cipher, PRG-from-hc)
• constructing an attacker (the other half of the exam):
  • template for "sketch an adversary with non-negligible advantage": (1) the queries \mathcal A$\mathcal A$ makes, in order, + challenge messages; (2) the output rule as a formula ("output 1 iff f_3=k_1x_3+k_2$f_3=k_1x_3+k_2$"); (3) both probabilities (real world, ideal world); (4) subtract: "hence the advantage is 1-\frac1{|\mathbb F|}$1-\frac1{|\mathbb F|}$, non-negligible" (words alone earn little: algorithm + arithmetic statement)
  • the five attack ideas that cover every exercise: algebraic solve-and-predict (use the first queries to solve for the key, predict the next output: linear PRF); malleability (maul c\mapsto c'$c\mapsto c'$ with a known effect on m$m$, query the decryption oracle: ElGamal, CTR-as-MAC); key-independent collision (exploit commutativity/linearity to collide for all keys: XOR-UHF); reorder / truncate / mix blocks (whenever the tag input lacks index, length or nonce); detect determinism / structure (a constant component, repeated ciphertext for a repeated message, parity leak)
• two-minute self-check before handing in:
  • every game has an explicit challenger (Setup + each oracle + challenge/forgery)
  • game 0's win probability is identified with the advantage being bounded, in words
  • every gap has either a named wrapper or a named event Z$Z$: never a bare "clearly"
  • every wrapper: what it simulates, what it outsources, what it outputs, how many queries
  • the last game is bounded directly
  • the final chain uses the triangle inequality and ends "…is negligible by assumption"
  • no wrapper reads a secret or branches on its challenger's experiment

BONUS: Constructions catalogue

• what counts as a complete construction (the usual failure is not a wrong construction but an incomplete description):
  • give all algorithms of the primitive (cipher: E$E$ and D$D$; KEM: G,E,D$G,E,D$; signature: G,S,V$G,S,V$; MAC: S$S$ and V$V$)
  • mark random oracles explicitly ("let H:\mathcal M\to\mathcal X$H:\mathcal M\to\mathcal X$ be a random oracle"): the task statement demands it and it is worth a point
  • make it correct: decryption/verification must invert/accept: check it mentally once
  • make it randomised where required (any IND-CPA cipher: a deterministic one is instantly wrong)
  • domain-separate whenever one key serves two purposes: F(k,(0,\cdot))$F(k,(0,\cdot))$ vs F(k,(1,\cdot))$F(k,(1,\cdot))$, or derive subkeys F(k,0),F(k,1)$F(k,0),F(k,1)$
  • you may chain known constructions: say which ones ("this is Encrypt-then-MAC with rCTR and a PRF-MAC")
• the two maps (draw these from memory):
  • secret key: OWF ← (implied by everything below) ← OWP+hc [G(x)=(hc(x),f(x)): 1-bit; Blum–Micali/parallel: n-bit] → PRG → PRF [G(k)=F(k,0)‖F(k,1)‖…] → {stream cipher (sem.-secure, |K|<|M|), IND-CPA ciphers (rCTR/OFB), (S)UF-CMA MACs} → Encrypt-then-MAC → AE → IND-CCA ciphers, with back-edges PRP ⇄ PRF (Luby–Rackoff; switching lemma cost Q^2/2|\mathcal X|$Q^2/2|\mathcal X|$; P(k_1,m)\oplus P(k_2,m)$P(k_1,m)\oplus P(k_2,m)$), PRP → PRG: P(s,[0])‖P(s,[1])‖P(s,[2]), strong PRP → IND-CCA cipher: P(k,(m,r)), tweakable E(k,s,m)=P(F(k,s),m); and OWF → PRG ⟹ P≠NP
• symmetric recipes (given X, build Y):
  • PRG from PRP/PRF: G(s):=P(s,[0])\,\|\,P(s,[1])\,\|\,P(s,[2])$G(s):=P(s,[0])\,\|\,P(s,[1])\,\|\,P(s,[2])$ (seed = key, fixed distinct points)
  • stream cipher (sem.-secure, single message): E(k,m)=G(k)\oplus m$E(k,m)=G(k)\oplus m$, D(k,c)=G(k)\oplus c$D(k,c)=G(k)\oplus c$ (truncate; one message per key: reuse gives c_1\oplus c_2=m_1\oplus m_2$c_1\oplus c_2=m_1\oplus m_2$)
  • PRF from PRP: P$P$ itself (cost \frac{Q^2}{2|\mathcal X|}$\frac{Q^2}{2|\mathcal X|}$: switching lemma) or better F((k_1,k_2),m):=P(k_1,m)\oplus P(k_2,m)$F((k_1,k_2),m):=P(k_1,m)\oplus P(k_2,m)$ (avoids the "outputs never repeat" weakness)
  • 1-bit PRG from OWP: G(x):=(hc(x),f(x))$G(x):=(hc(x),f(x))$; then Blum–Micali for length
  • PRF from PRG (1-bit domain): (y_0,y_1)\leftarrow G(k)$(y_0,y_1)\leftarrow G(k)$, return y_x$y_x$; extend the domain with the tree construction F^*$F^*$ (prefix-free inputs: enforce via length prefix or an appended independent key)
  • arbitrary-length PRF, efficiently: NMAC F'((k_0,k_1),x):=F(k_0,H(k_1,x))$F'((k_0,k_1),x):=F(k_0,H(k_1,x))$ with a UHF H$H$; HMAC = NMAC with ipad/opad$ipad/opad$ standing in for independent keys
  • UHF: H(k,x):=k^l+x_0k^{l-1}+\dots+x_{l-1}$H(k,x):=k^l+x_0k^{l-1}+\dots+x_{l-1}$ (\mathsf{UHFadv}\le l/|\mathbb F|$\mathsf{UHFadv}\le l/|\mathbb F|$, unconditional); never XOR-checksums
  • IND-CPA from a PRF: rCTR (iv\xleftarrow{R}\mathcal X$iv\xleftarrow{R}\mathcal X$; c[i]=m[i]\oplus F(k,iv+i)$c[i]=m[i]\oplus F(k,iv+i)$; send (iv,c)$(iv,c)$) or OFB (IV_0\xleftarrow{R}\{0,1\}^n$IV_0\xleftarrow{R}\{0,1\}^n$; IV_i=F(k,IV_{i-1})$IV_i=F(k,IV_{i-1})$; c_i=m_i\oplus IV_i$c_i=m_i\oplus IV_i$; send (IV_0,c)$(IV_0,c)$); from a PRG \{0,1\}^n\to\{0,1\}^{2n}$\{0,1\}^n\to\{0,1\}^{2n}$: the GGM path (random bits as nonce, walk, final k\oplus m$k\oplus m$)
  • PRP from PRF: 4-round Feistel (Luby–Rackoff), 4 independent keys
  • IND-CCA from a strong PRP: E(k,m)$E(k,m)$: r\xleftarrow{R}\mathcal R$r\xleftarrow{R}\mathcal R$, return P(k,(m,r))$P(k,(m,r))$; D$D$: invert, drop r$r$; full-disk variant \mathcal R=\{\varepsilon\}$\mathcal R=\{\varepsilon\}$ (deterministic, length-preserving: secure if a message is never encrypted twice); tweakable (per-sector FDE): E(k,s,m):=P(F(k,s),m)$E(k,s,m):=P(F(k,s),m)$
  • MAC from a PRF: S(k,m)=F(k,m)$S(k,m)=F(k,m)$, V(k,m,t)=[[F(k,m)=t]]$V(k,m,t)=[[F(k,m)=t]]$ (needs super-poly |\mathcal T|$|\mathcal T|$)
  • MAC for long/structured messages: F^*$F^*$ at fixed length (S(k,(m_0,m_1,m_2))=F(F(F(k,m_0),m_1),m_2)$S(k,(m_0,m_1,m_2))=F(F(F(k,m_0),m_1),m_2)$); hash-then-MAC S(k,H(m))$S(k,H(m))$; Carter–Wegman H(k,m)\oplus F(k',r)$H(k,m)\oplus F(k',r)$
  • AE: the default answer: Encrypt-then-MAC with independent keys (c\leftarrow E(k_e,m)$c\leftarrow E(k_e,m)$; t\leftarrow S(k_m,c)$t\leftarrow S(k_m,c)$; verify before decrypt, else \bot$\bot$); with AD: tag (c,d)$(c,d)$; from a single PRF: keystream under subkey F(k,0)$F(k,0)$, tag F(k,(1,iv,c))$F(k,(1,iv,c))$: the leading 0/1$0/1$ domain separation is the one trick to remember
• public-key recipes:
  • CPA KEM from a OWTF (ROM): E(pk)$E(pk)$: x\xleftarrow{R}\mathcal X$x\xleftarrow{R}\mathcal X$, c\leftarrow F(pk,x)$c\leftarrow F(pk,x)$, return (c,H(x))$(c,H(x))$; D(sk,c)$D(sk,c)$: H(I(sk,c))$H(I(sk,c))$: the key is the hash of x$x$, never x$x$ itself (one-wayness permits leaking half the preimage; sending x$x$ is the classic wrong answer)
  • CPA KEM from a OWTP, no RO: Blum–Micali (chain forwards with pk$pk$, receiver walks back with I$I$; needs a permutation; costs n$n$ evaluations)
  • CCA KEM from a OWTF (ROM): three interchangeable answers: (a) FO with explicit rejection: r\leftarrow H_1(x)$r\leftarrow H_1(x)$ as redundancy, key H_2(x)$H_2(x)$, re-encryption check in D$D$; (b) FO with implicit rejection: secret seed s$s$, invalid ciphertexts return H(s,c)$H(s,c)$ instead of \bot$\bot$ (looks uniform to anyone without s$s$; the \frac{Q_{ro}}{|\mathcal X|}$\frac{Q_{ro}}{|\mathcal X|}$ term is its price); (c) if the OWTF is a permutation (RSA), the validity check is vacuous: simplify to E$E$: c\leftarrow m^e$c\leftarrow m^e$, return (c,H(m))$(c,H(m))$
  • the FO transformation itself: F_{FO}(pk,x):=F(pk,x;H(x))$F_{FO}(pk,x):=F(pk,x;H(x))$: OWTF ⟹ OW-VA OWTF; the variant F'(pk,x):=(F(pk,x),H(x))$F'(pk,x):=(F(pk,x),H(x))$: the guess disappears (publicly checkable ⟹ tight)
  • CCA KEM from a CCA PKE: E_{kem}(pk)$E_{kem}(pk)$: m\xleftarrow{R}\mathcal M$m\xleftarrow{R}\mathcal M$, c\leftarrow E(pk,m)$c\leftarrow E(pk,m)$, return (c,m)$(c,m)$; D_{kem}(sk,c)$D_{kem}(sk,c)$: D(sk,c)$D(sk,c)$
  • hybrid PKE: (k,c_k)\xleftarrow{R}E_k(pk)$(k,c_k)\xleftarrow{R}E_k(pk)$, c_s\leftarrow E_s(k,m)$c_s\leftarrow E_s(k,m)$, output (c_k,c_s)$(c_k,c_s)$; CCA needs both halves CCA-secure
  • DH KEM: H$H$ = extractor under DDH, random oracle under CDH/GDH; AD-KEM: CCA KEM + PRF over d$d$
  • ElGamal (DH-KEM + trivial extractor + group OTP; IND-CPA under DDH, not CCA: malleable) and FO-ElGamal (the re-encryption check is what kills the malleability: the ready-made answer)
  • signatures: FDH from a OWTP + RO (S=I\circ H$S=I\circ H$, V$V$ checks F(\sigma)\stackrel{?}{=}H(m)$F(\sigma)\stackrel{?}{=}H(m)$): the default answer for "given a trapdoor permutation", mark H$H$ as a random oracle; the Lamport ladder from any OWF (naming the four steps in order is usually most of the marks)
• hash-function recipes:
  • CR hash for long inputs: Merkle–Damgård (injective padding with the length; \mathsf{CRadv}[H_{MD}]=\mathsf{CRadv}[h]$\mathsf{CRadv}[H_{MD}]=\mathsf{CRadv}[h]$)
  • compression: Davies–Meyer h(x,k)=E(k,x)\oplus x$h(x,k)=E(k,x)\oplus x$ from a PRP (heuristic; the feed-forward \oplus x$\oplus x$ is essential), or DL-based h(x,y)=a^xb^y\bmod p$h(x,y)=a^xb^y\bmod p$ (provable)
  • many-item integrity: Merkle tree (a proof is the d$d$ sibling hashes; forging one implies a collision in h$h$)
  • keyed hashing / PRF from a hash: HMAC H(k\oplus opad\,\|\,H(k\oplus ipad\,\|\,m))$H(k\oplus opad\,\|\,H(k\oplus ipad\,\|\,m))$; never H_{MD}(k\|m)$H_{MD}(k\|m)$ (length extension)
  • key derivation: existing key ⟹ PRF; computational secret ⟹ RO/hard-core; high-entropy non-uniform ⟹ strong extractor; low-entropy ⟹ as above but deliberately slow; HKDF = extract-then-expand (HMAC extract, then HMAC-CTR expand)
• design rules for constructions you have to invent:
  1. match the interface first: write the signature of every algorithm with its types; the types usually force the construction (e.g. "tags in \{0,1\}^n$\{0,1\}^n$, messages in \{0,1\}^{3n}$\{0,1\}^{3n}$, PRF on n$n$ bits" ⟹ iterate the PRF three times)
  2. randomise/nonce everything that must hide repetitions (fresh iv$iv$/r$r$ per encryption, sent in the clear)
  3. bind everything the receiver relies on into the authentication tag: nonce, ciphertext, length, associated data, index (each omission has a known forgery: the drop-one-field catalogue)
  4. separate keys/domains: one key per purpose, or one master key plus F(k,\text{tag})$F(k,\text{tag})$
  5. never expose a raw trapdoor/one-way image as a key: always hash it (k\leftarrow H(x)$k\leftarrow H(x)$), because one-wayness allows leaking half the preimage
  6. for CCA, make ciphertexts non-malleable and unique: MAC them (symmetric) or add a re-encryption/validity check (FO, public key)
  7. prefix-freeness/injective encodings whenever you iterate a function over blocks (length prefix, padding with the length)
  8. sanity-attack your own answer: can I swap two blocks? truncate? reuse a nonce? re-sign with a different key? If yes, fix it
• existence one-liners: rather than memorising the table, memorise the spine and read each claim as "can I walk from A to B along it?": OWF → PRG → PRF → {MAC, IND-CPA} → AE → IND-CCA
  • PRFs ⟹ PRGs: G(k)=F(k,0)\|F(k,1)\|\dots$G(k)=F(k,0)\|F(k,1)\|\dots$; PRGs ⟹ PRFs: 1-bit PRF + tree construction; PRPs ⟹ AE: PRP gives a CPA cipher and (via switching lemma / sum construction) a PRF, hence a MAC, hence EtM; CPA-secure ciphers ⟹ CCA-secure ciphers: CPA ⟹ OWF ⟹ PRG ⟹ PRF ⟹ MAC ⟹ EtM ⟹ AE ⟹ CCA; OWFs ⟹ signatures: hash-based/Lamport (no RO, no trapdoor needed); sem-secure cipher with negligible |\mathcal K|/|\mathcal M|$|\mathcal K|/|\mathcal M|$ ⟹ MACs: via OWF; RSA assumption ⟹ secure MACs without ROs: RSA ⟹ OWTF ⟹ OWF ⟹ …; OWFs ⟹ collision-resistant functions: heuristically yes: build a block cipher and use Davies–Meyer (the model answer; a fully generic black-box construction is not known: give the model answer, know the subtlety); "semantically secure schemes exist" = true (the OTP)

BONUS: Exam patterns and one-liners

• a bank of true/false claims, grouped by the reasoning each one needs:
  • pattern A: "chain through OWF" (⟹ usually TRUE, name the chain): PRFs exist ⟹ PRGs exist; CPA-secure schemes exist ⟹ CCA-secure schemes exist (CPA ⟹ OWF ⟹ … ⟹ MAC ⟹ EtM ⟹ AE ⟹ CCA); PRPs exist ⟹ AE schemes exist; sem.-secure with negligible |\mathcal K|/|\mathcal M|$|\mathcal K|/|\mathcal M|$ ⟹ MACs exist; OWFs exist ⟹ signature schemes exist (Lamport); RSA assumption ⟹ secure MACs without ROs; OWFs exist ⟹ collision-resistant functions exist (model answer: block cipher + Davies–Meyer); semantically secure schemes exist (the OTP)
  • pattern B: "definitions do not transfer" (⟹ usually FALSE; the fastest refutation is a specific counterexample: the same half-dozen objects refute almost everything in this family):
    • every collision-resistant function is one-way: false: the identity function (no collisions at all, trivially invertible)
    • an IND-CPA scheme can be used as a MAC via S(k,m)=E(k,m)$S(k,m)=E(k,m)$: false: malleability (rCTR ciphertexts can be modified into valid "tags" for other messages)
    • in the ROM, F(k,m):=H(m)$F(k,m):=H(m)$ is a PRF: false: H$H$ is public, the adversary computes it without any F$F$-query
    • textbook RSA is IND-CPA iff the RSA assumption holds: false: the RSA assumption gives a OWTF; deterministic ⟹ never IND-CPA
    • ROM schemes stay secure if H$H$ is replaced by a CRHF that is also a PRF: false: there exist ROM-secure schemes no PPT function can instantiate
    • integrity for a single message requires OWFs: false: polynomial one-time MACs are unconditionally secure
    • a signed PKES ciphertext must have been created by the signer: false: Alice can sign a ciphertext produced by Eve
    • signcryption prevents replay: false: it guarantees authenticity, not liveness/freshness
    • static AKE security lets you reuse keys after a server (HSM) compromise: false: that needs HSM security, a different model
  • pattern C: "read the definition literally" (mixed; the only skill is quoting the definition rather than your intuition): a perfectly secure scheme is also semantically secure: true (every adversary has advantage exactly 0, which is negligible); under perfect security, brute force lets you deduce the message: false (you obtain every message of that length equally often); the OTP has the optimal |\mathcal K|/|\mathcal M|$|\mathcal K|/|\mathcal M|$ ratio: true (Shannon's theorem forbids |\mathcal K|<|\mathcal M|$|\mathcal K|<|\mathcal M|$); FDH with a OWTP is always SUF-CMA: true (exactly one valid signature per message)
  • how to attack an unseen one-liner in 40 seconds: (1) existence/implication claim? try to chain through OWF: usually true, name the chain; (2) one notion implies another? look for the standard counterexamples: identity (CR≠OW), deterministic scheme (¬CPA), malleable scheme (¬MAC, ¬CCA), public function (¬PRF), constant component (¬PRF but still a MAC), H_{MD}(k\|m)$H_{MD}(k\|m)$ (length extension); (3) mentions the ROM? rigorous but not instantiable in general; a public hash is never a PRF by itself; (4) claims a scheme achieves more than its definition (authorship of the content? freshness? many-message security?): usually false; (5) write one concrete sentence, naming the scheme, theorem or attack
• reference table of the security bounds (not asked from memory, but the shape of a bound reveals which technique produced it):
  • forms: \mathsf{Xadv}=2\cdot\mathsf{Xadv}^*$\mathsf{Xadv}=2\cdot\mathsf{Xadv}^*$
  • stream cipher: \mathsf{PRGadv}[\mathcal B,G]=\mathsf{SCadv}^*[\mathcal A,\Pi]$\mathsf{PRGadv}[\mathcal B,G]=\mathsf{SCadv}^*[\mathcal A,\Pi]$; PRG compositions (parallel/BM): \le n\cdot\mathsf{PRGadv}$\le n\cdot\mathsf{PRGadv}$; PRG from OWP+hc: =\mathsf{HCadv}$=\mathsf{HCadv}$
  • rCTR: \le\mathsf{PRFadv}[\mathcal B,F,(Q{+}1)l]+\frac{2Ql}{|\mathcal X|}$\le\mathsf{PRFadv}[\mathcal B,F,(Q{+}1)l]+\frac{2Ql}{|\mathcal X|}$; tree PRF F^*$F^*$: \le n\cdot\mathsf{PRFadv}$\le n\cdot\mathsf{PRFadv}$ (prefix-free), \le Ql\cdot\mathsf{PRFadv}$\le Ql\cdot\mathsf{PRFadv}$ (fixed length)
  • PRP-cipher (CCA): \le\mathsf{PRPadv}[\mathcal B,P,Q_e{+}1,Q_d]+\frac{Q_e+Q_d}{|\mathcal M||\mathcal R|}+\frac{Q_e+Q_d}{|\mathcal R|}$\le\mathsf{PRPadv}[\mathcal B,P,Q_e{+}1,Q_d]+\frac{Q_e+Q_d}{|\mathcal M||\mathcal R|}+\frac{Q_e+Q_d}{|\mathcal R|}$; Luby–Rackoff: \le4\,\mathsf{PRFadv}[\mathcal B,F,Q_f{+}Q_b]+\frac{Q^2}{|\mathcal X|}$\le4\,\mathsf{PRFadv}[\mathcal B,F,Q_f{+}Q_b]+\frac{Q^2}{|\mathcal X|}$; switching lemma: \le\frac{Q^2}{2|\mathcal X|}$\le\frac{Q^2}{2|\mathcal X|}$
  • AE ⟹ CCA: \le Q_d\cdot\mathsf{CIadv}[\mathcal B_{CI},\Pi,Q_e{+}1]+\mathsf{CPAadv}^*[\mathcal B_{CPA},\Pi,Q_e]$\le Q_d\cdot\mathsf{CIadv}[\mathcal B_{CI},\Pi,Q_e{+}1]+\mathsf{CPAadv}^*[\mathcal B_{CPA},\Pi,Q_e]$; PRF ⟹ MAC: \le\mathsf{PRFadv}[\mathcal B,F,Q{+}1]+\frac1{|\mathcal T|}$\le\mathsf{PRFadv}[\mathcal B,F,Q{+}1]+\frac1{|\mathcal T|}$
  • polynomial UHF: \le\frac{l}{|\mathbb F|}$\le\frac{l}{|\mathbb F|}$ (one-time MAC: \le\epsilon$\le\epsilon$); PRF∘UHF: \le\mathsf{PRFadv}[\mathcal B_F,F,Q]+\frac{Q^2}{2}\mathsf{UHFadv}[\mathcal B_H,H]$\le\mathsf{PRFadv}[\mathcal B_F,F,Q]+\frac{Q^2}{2}\mathsf{UHFadv}[\mathcal B_H,H]$
  • hash-then-MAC / hash-then-sign: \le\mathsf{MACadv}+\mathsf{CRadv}$\le\mathsf{MACadv}+\mathsf{CRadv}$ / \le\mathsf{SIGadv}+\mathsf{CRadv}$\le\mathsf{SIGadv}+\mathsf{CRadv}$; Merkle–Damgård: =$=$; Encrypt-then-MAC: =$=$ (equalities, both)
  • \mathcal O(k\|x)$\mathcal O(k\|x)$ is a PRF: \le\frac{Q_{ro}}{|\mathcal K|}$\le\frac{Q_{ro}}{|\mathcal K|}$; KEM from OWTF (CPA, ROM): \le\mathsf{OWTFadv}$\le\mathsf{OWTFadv}$; KEM from OWTF (CCA, ROM): \le\mathsf{IOWadv}[\mathcal B,\mathcal T,Q]$\le\mathsf{IOWadv}[\mathcal B,\mathcal T,Q]$
  • DH-KEM: \le Q\cdot\mathsf{CDHadv}$\le Q\cdot\mathsf{CDHadv}$ (ROM) / \le\mathsf{DDHadv}+\mathsf{EXTadv}$\le\mathsf{DDHadv}+\mathsf{EXTadv}$ / \le\mathsf{GDHadv}$\le\mathsf{GDHadv}$ (CCA, ROM)
  • hybrid PKE: CPA: \le\mathsf{KEMCPAadv}+\mathsf{SCadv}^*$\le\mathsf{KEMCPAadv}+\mathsf{SCadv}^*$; CCA: \le\mathsf{KEMCCAadv}+\mathsf{CCAadv}^*[\cdot,\Pi_s,0,Q]$\le\mathsf{KEMCCAadv}+\mathsf{CCAadv}^*[\cdot,\Pi_s,0,Q]$
  • FO transformation: \mathsf{IOWroadv}\le Q_v\gamma+(Q_{ro}{+}1)\mathsf{OWTFadv}$\mathsf{IOWroadv}\le Q_v\gamma+(Q_{ro}{+}1)\mathsf{OWTFadv}$; Full Domain Hash: \mathsf{stSIGroadv}\le(Q_{ro}{+}1)\mathsf{OWTFadv}$\mathsf{stSIGroadv}\le(Q_{ro}{+}1)\mathsf{OWTFadv}$
  • Lamport: \le|\mathcal M|\,\mathsf{OWFadv}$\le|\mathcal M|\,\mathsf{OWFadv}$ (strong: \le|\mathcal M|(\mathsf{OWFadv}+\mathsf{SPRadv})$\le|\mathcal M|(\mathsf{OWFadv}+\mathsf{SPRadv})$); tree signatures: \le(Qbd{+}1)\mathsf{SIGadv}+\mathsf{PRFadv}+\frac{Q^2}{2b^d}$\le(Qbd{+}1)\mathsf{SIGadv}+\mathsf{PRFadv}+\frac{Q^2}{2b^d}$
• exam phrasing:
  • "Skizzieren Sie die einzelnen Angriffsspiele, indem Sie jeweils das Verhalten des Challengers angeben." ⟹ pseudocode of each challenger: Setup(), oracles, challenge/forgery; later games as diffs
  • "Finden Sie vernachlässigbare obere Schranken für |\Pr[W_i]-\Pr[W_{i+1}]|$|\Pr[W_i]-\Pr[W_{i+1}]|$ und beweisen Sie deren Richtigkeit." ⟹ one bullet per gap: wrapper (who/what/output) or difference lemma (event Z$Z$ + probability)
  • "Begrenzen Sie die Advantage eines PPT-Angreifers durch einen vernachlässigbaren Wert." ⟹ triangle inequality + "negligible by assumption"
  • "Konstruieren Sie … auf korrekte und sichere Weise." ⟹ all algorithms, correct, randomised; no proof required
  • "Wenn Sie Zufallsorakel verwenden, markieren Sie diese als solche." ⟹ write "let H$H$ be a random oracle"
  • "Skizzieren Sie einen Angreifer mit nicht vernachlässigbarer Advantage." ⟹ queries, output rule, both probabilities, the difference
  • "Gegeben einen Angreifer \mathcal A$\mathcal A$, konstruieren Sie einen Angreifer \mathcal B$\mathcal B$ mit …" ⟹ pseudocode for \mathcal B$\mathcal B$ using \mathcal A$\mathcal A$'s oracle names, plus the success-probability relation, rearranged into the stated inequality
  • "Zeigen Sie, dass … nicht perfectly secure ist." ⟹ Shannon (|\mathcal K|<|\mathcal M|$|\mathcal K|<|\mathcal M|$) or an explicit (m_0,m_1,c)$(m_0,m_1,c)$ with N_{m_0,c}\ne N_{m_1,c}$N_{m_0,c}\ne N_{m_1,c}$
  • "Zeigen Sie die Korrektheit." ⟹ D(k,E(k,m))=m$D(k,E(k,m))=m$ by algebra, for all k,m$k,m$
  • "Erklären Sie, wann … die Sicherheit beeinträchtigt." ⟹ name the event (nonce reuse, key reuse, collision), what leaks, and which property survives