Glance Cards: Primitives and Security Notions
| Term | Meaning |
|---|---|
| \(\lambda\) | Security parameter: key/seed length in bits (e.g., 128 or 256) |
| Negligible | \(f(\lambda)\) is negligible if it vanishes faster than any inverse polynomial: \(f(\lambda) < 1/\lambda^c\) for all \(c\), for large enough \(\lambda\) |
| PPT | Probabilistic polynomial time: runs in at most \(\text{poly}(\lambda)\) steps |
| Secure | For all PPT adversaries \(\mathcal{A}\), the relevant advantage is negligible in \(\lambda\) |
| Primitive | Notion | Advantage | Oracle |
|---|---|---|---|
| PRG \(G\) | Output indistinguishable from uniform random | \(\text{PRG}_\text{adv}[\mathcal{A}, G]\) | None |
| Stream cipher \(\mathcal{E}\) | Semantic security, one-time key | \(\text{SS}_\text{adv}[\mathcal{A}, \mathcal{E}]\) | None |
| PRF \(F\) | Indistinguishable from random function | \(\text{PRF}_\text{adv}[\mathcal{A}, F]\) | \(F(k, \cdot)\) |
| Block cipher \(\mathcal{E}\) | Indistinguishable from random permutation | \(\text{BC}_\text{adv}[\mathcal{A}, \mathcal{E}]\) | \(E(k, \cdot)\) |
| CPA encryption \(\mathcal{E}\) | Semantic security, multi-message | \(\text{CPA}_\text{adv}[\mathcal{A}, \mathcal{E}]\) | \(E(k, \cdot)\) |
| MAC \(\mathcal{I}\) | Existential unforgeability under CMA | \(\text{MAC}_\text{adv}[\mathcal{A}, \mathcal{I}]\) | \(S(k, \cdot)\) |
| UHF \(h\) | Collision probability \(\leq \epsilon\) (statistical) | \(\epsilon\)-UHF | None |
| CR hash \(H\) | Computationally collision resistant | \(\text{CR}_\text{adv}[\mathcal{A}, H]\) | None |
| AEAD \(\mathcal{E}\) | Confidentiality and ciphertext integrity | \(\text{CCA}_\text{adv}[\mathcal{A}, \mathcal{E}]\) | \(E(k, \cdot)\), \(D(k, \cdot)\) |
| Primitive | Notion | Advantage | Oracle |
|---|---|---|---|
| Trapdoor function \(\mathcal{T}\) | Hard to invert without \(sk\) (one-wayness) | \(\text{OW}_\text{adv}[\mathcal{A}, \mathcal{T}]\) | None |
| PK encryption, SS-CPA \(\mathcal{E}\) | Semantically secure under CPA | \(\text{SS}_\text{adv}[\mathcal{A}, \mathcal{E}]\) | \(pk\) public |
| PK encryption, SS-CCA \(\mathcal{E}\) | Semantically secure under CCA | \(\text{CCA}_\text{adv}[\mathcal{A}, \mathcal{E}]\) | \(D(sk, \cdot)\) |
| Digital signature \(\mathcal{S}\) | Existential unforgeability under CMA | \(\text{SIG}_\text{adv}[\mathcal{A}, \mathcal{S}]\) | \(S(sk, \cdot)\) |
| Key exchange \(P\) | Shared key hard to recover from transcript | \(\text{AnonKE}_\text{adv}[\mathcal{A}, P]\) | Transcript |
| Primitive | \(G: \{0,1\}^\lambda \to \{0,1\}^n\), \(n \gg \lambda\) |
| Example | RC4 (broken; seed = key) |
| Game | PRG |
| Notion | Output indistinguishable from uniform random |
| Advantage | \(\text{PRG}_\text{adv}[\mathcal{A}, G] = \lvert\Pr[W_0] - \Pr[W_1]\rvert\) |
| Oracle | None: \(\mathcal{A}\) receives a single sample, no queries |
| Secure if | \(\text{PRG}_\text{adv}[\mathcal{A}, G]\) is negligible in \(\lambda\) for all PPT \(\mathcal{A}\) |
| Key reduction | \(\text{SS}_\text{adv}[\mathcal{A}, \mathcal{E}] \leq \text{PRG}_\text{adv}[\mathcal{B}, G]\) |
| Primitive | \(\mathcal{E} = (E, D)\), \(E(k, m) = G(k) \oplus m\), \(k \xleftarrow{R} \mathcal{K}\) |
| Example | ChaCha20 stream cipher |
| Game | SS (semantic security) |
| Notion | Ciphertext indistinguishable under one-time key |
| Advantage | \(\text{SS}_\text{adv}[\mathcal{A}, \mathcal{E}] = \lvert\Pr[W_0] - \Pr[W_1]\rvert\) |
| Oracle | None: single key, single challenge ciphertext |
| Secure if | \(\text{SS}_\text{adv}[\mathcal{A}, \mathcal{E}]\) is negligible in \(\lambda\) for all PPT \(\mathcal{A}\) |
| Warning | Key reuse is catastrophic: \(c_0 \oplus c_1 = m_0 \oplus m_1\) |
| Primitive | \(F: \mathcal{K} \times \mathcal{X} \to \mathcal{Y}\) |
| Example | ChaCha20 (\(k\) = key, input = nonce), AES (keyed), HMAC-SHA256 |
| Game | PRF |
| Notion | Indistinguishable from a truly random function \(f \xleftarrow{R} \text{Funcs}[\mathcal{X}, \mathcal{Y}]\) |
| Advantage | \(\text{PRF}_\text{adv}[\mathcal{A}, F] = \lvert\Pr[W_0] - \Pr[W_1]\rvert\) |
| Oracle | Adaptive query oracle \(F(k, \cdot)\); \(\mathcal{A}\) never sees \(k\) |
| Secure if | \(\text{PRF}_\text{adv}[\mathcal{A}, F]\) is negligible in \(\lambda\) for all PPT \(\mathcal{A}\) |
| Key reduction | \(\text{MAC}_\text{adv}[\mathcal{A}, \mathcal{I}] \leq \text{PRF}_\text{adv}[\mathcal{B}, F] + 1/\lvert\mathcal{T}\rvert\) |
| Primitive | \(E: \mathcal{K} \times \mathcal{X} \to \mathcal{X}\), bijection for each \(k\) |
| Example | AES-128, AES-256 |
| Game | BC (block cipher security) |
| Notion | Indistinguishable from a truly random permutation \(\pi \xleftarrow{R} \text{Perms}[\mathcal{X}]\) |
| Advantage | \(\text{BC}_\text{adv}[\mathcal{A}, \mathcal{E}] = \lvert\Pr[W_0] - \Pr[W_1]\rvert\) |
| Oracle | Forward oracle \(E(k, \cdot)\) only |
| Secure if | \(\text{BC}_\text{adv}[\mathcal{A}, \mathcal{E}]\) is negligible in \(\lambda\) for all PPT \(\mathcal{A}\) |
| Strong PRP | Adds inverse oracle \(E^{-1}(k, \cdot)\): strictly harder to satisfy |
| PRP switching lemma | \(\text{PRF}_\text{adv}[\mathcal{A}, E] \leq \text{BC}_\text{adv}[\mathcal{B}, E] + Q^2 / 2\lvert\mathcal{X}\rvert\) |
| Primitive | \(\mathcal{E} = (E, D)\), symmetric, randomised |
| Example | AES-CTR with random nonce, AES-CBC with random IV |
| Game | IND-CPA (semantic security under CPA) |
| Notion | Ciphertext indistinguishable under adaptive chosen plaintext attack |
| Advantage | \(\text{CPA}_\text{adv}[\mathcal{A}, \mathcal{E}] = \lvert\Pr[W_0] - \Pr[W_1]\rvert\) |
| Oracle | Adaptive encryption oracle \(E(k, \cdot)\) before and after challenge |
| Secure if | \(\text{CPA}_\text{adv}[\mathcal{A}, \mathcal{E}]\) is negligible in \(\lambda\) for all PPT \(\mathcal{A}\) |
| Requires | Randomised or stateful encryption: deterministic encryption fails CPA trivially |
| Primitive | \(\mathcal{I} = (S, V)\), \(S: \mathcal{K} \times \mathcal{M} \to \mathcal{T}\) |
| Example | HMAC-SHA256, CMAC-AES |
| Game | MAC (existential unforgeability under CMA) |
| Notion | Adversary cannot forge a valid tag for any fresh message |
| Advantage | \(\text{MAC}_\text{adv}[\mathcal{A}, \mathcal{I}] = \Pr[V(k, m^*, t^*) = \texttt{accept},\ m^* \text{ fresh}]\) |
| Oracle | Adaptive signing oracle \(S(k, \cdot)\); \(\mathcal{A}\) must output \((m^*, t^*)\) for unseen \(m^*\) |
| Secure if | \(\text{MAC}_\text{adv}[\mathcal{A}, \mathcal{I}]\) is negligible in \(\lambda\) for all PPT \(\mathcal{A}\) |
| Key reduction | \(\text{MAC}_\text{adv}[\mathcal{A}, \mathcal{I}] \leq \text{PRF}_\text{adv}[\mathcal{B}, F] + 1/\lvert\mathcal{T}\rvert\) |
| Primitive | \(h: \mathcal{K} \times \mathcal{M} \to \mathcal{T}\), keyed |
| Example | Poly1305, GHASH (GCM’s authenticator) |
| Security | \(\epsilon\)-UHF: statistical, not computational |
| Notion | Collision probability at most \(\epsilon\) for any fixed \(m_0 \neq m_1\) over random \(k\) |
| Bound | \(\Pr_{k \xleftarrow{R} \mathcal{K}}[h(k, m_0) = h(k, m_1)] \leq \epsilon\) for all \(m_0 \neq m_1\) |
| Oracle | None: security is information-theoretic over key randomness |
| Note | UHF alone is not a MAC: one output leaks key structure to an adversary |
| Used in | Carter-Wegman MAC: \(\text{tag} = h(k_h, m) \oplus \text{PRF}(k_p, \text{nonce})\) |
| Primitive | \(H: \mathcal{M} \to \mathcal{T}\), unkeyed, public |
| Example | SHA-256, SHA-3 (Keccak) |
| Game | CR (collision resistance) |
| Notion | Computationally infeasible to find \(m_0 \neq m_1\) with \(H(m_0) = H(m_1)\) |
| Advantage | \(\text{CR}_\text{adv}[\mathcal{A}, H] = \Pr[H(m_0) = H(m_1),\ m_0 \neq m_1]\) |
| Oracle | None: \(H\) is public; \(\mathcal{A}\) outputs a collision pair \((m_0, m_1)\) |
| Secure if | \(\text{CR}_\text{adv}[\mathcal{A}, H]\) is negligible in \(\lambda\) for all PPT \(\mathcal{A}\) |
| Hierarchy | CR \(\Rightarrow\) 2nd-preimage resistance \(\Rightarrow\) preimage resistance |
| Primitive | \(\mathcal{E} = (E, D)\) with associated data, nonce-based |
| Example | AES-GCM, ChaCha20-Poly1305 |
| Game | CCA (IND-CCA2 with ciphertext integrity) |
| Notion | Confidentiality and ciphertext integrity: decryption oracle gives no advantage |
| Advantage | \(\text{CCA}_\text{adv}[\mathcal{A}, \mathcal{E}] = \lvert\Pr[W_0] - \Pr[W_1]\rvert\) |
| Oracle | Encryption \(E(k, \cdot)\) and decryption \(D(k, \cdot)\) (excluding challenge ciphertext) |
| Secure if | \(\text{CCA}_\text{adv}[\mathcal{A}, \mathcal{E}]\) is negligible in \(\lambda\) for all PPT \(\mathcal{A}\) |
| Composition | Encrypt-then-MAC: \(\text{CCA}_\text{adv} \leq \text{CPA}_\text{adv}[\mathcal{B}, \mathcal{E}] + \text{MAC}_\text{adv}[\mathcal{C}, \mathcal{I}]\) |
| Primitive | \(\mathcal{T} = (G, F, I)\): \(G\) generates \((pk, sk)\); \(F(pk, \cdot)\) applies; \(I(sk, \cdot)\) inverts |
| Example | RSA: \(F(pk, x) = x^e \bmod n\) |
| Game | OW (one-wayness) |
| Notion | Given \(pk\) and \(y = F(pk, x)\), hard to recover \(x\) without \(sk\) |
| Advantage | \(\text{OW}_\text{adv}[\mathcal{A}, \mathcal{T}] = \Pr[\hat{x} = x]\) |
| Oracle | None: \(\mathcal{A}\) receives \((pk, y)\) and must invert |
| Secure if | \(\text{OW}_\text{adv}[\mathcal{A}, \mathcal{T}]\) is negligible in \(\lambda\) for all PPT \(\mathcal{A}\) |
| Warning | One-wayness does not imply CPA security: textbook RSA encryption is broken |
| Primitive | \(\mathcal{E} = (G, E, D)\): probabilistic public-key encryption |
| Example | ElGamal, RSA-OAEP |
| Game | SS-CPA (public-key semantic security) |
| Notion | Ciphertext indistinguishable: adversary holds \(pk\) and can encrypt freely |
| Advantage | \(\text{SS}_\text{adv}[\mathcal{A}, \mathcal{E}] = \lvert\Pr[\hat{b} = b] - 1/2\rvert\) |
| Oracle | None beyond \(pk\): adversary can self-encrypt, so no separate oracle is needed |
| Secure if | \(\text{SS}_\text{adv}[\mathcal{A}, \mathcal{E}]\) is negligible in \(\lambda\) for all PPT \(\mathcal{A}\) |
| Requires | Randomised encryption: deterministic PK encryption is trivially broken under CPA |
| Primitive | \(\mathcal{E} = (G, E, D)\), same scheme, stronger attacker |
| Example | RSA-OAEP (CCA-secure in ROM) |
| Game | SS-CCA (IND-CCA2) |
| Notion | Semantic security even with adaptive decryption oracle access |
| Advantage | \(\text{CCA}_\text{adv}[\mathcal{A}, \mathcal{E}] = \lvert\Pr[W_0] - \Pr[W_1]\rvert\) |
| Oracle | Decryption oracle \(D(sk, \cdot)\) before and after challenge (excluding challenge ciphertext) |
| Secure if | \(\text{CCA}_\text{adv}[\mathcal{A}, \mathcal{E}]\) is negligible in \(\lambda\) for all PPT \(\mathcal{A}\) |
| Stronger than | SS-CPA: active adversaries can submit ciphertexts for decryption in practice |
| Primitive | \(\mathcal{S} = (G, S, V)\): \(G\) generates \((pk, sk)\); \(S(sk, m) \to \sigma\); \(V(pk, m, \sigma) \to \{0,1\}\) |
| Example | RSA-PSS, ECDSA, Ed25519 |
| Game | EUF-CMA (existential unforgeability under CMA) |
| Notion | Adversary with signing oracle cannot forge on any fresh message |
| Advantage | \(\text{SIG}_\text{adv}[\mathcal{A}, \mathcal{S}] = \Pr[\text{valid } (m^*, \sigma^*),\ m^* \text{ fresh}]\) |
| Oracle | Adaptive signing oracle \(S(sk, \cdot)\); \(\mathcal{A}\) also holds \(pk\) |
| Secure if | \(\text{SIG}_\text{adv}[\mathcal{A}, \mathcal{S}]\) is negligible in \(\lambda\) for all PPT \(\mathcal{A}\) |
| Key reduction | Hash-then-sign: \(\text{SIG}_\text{adv}[\mathcal{A}, \mathcal{S}'] \leq \text{SIG}_\text{adv}[\mathcal{B}, \mathcal{S}] + \text{CR}_\text{adv}[\mathcal{C}, H]\) |
| Primitive | Two-party protocol \(P\); both parties output shared key \(k \in \mathcal{K}\) |
| Example | Diffie-Hellman (DH), ECDH |
| Game | AnonKE (anonymous key exchange) |
| Notion | Shared key computationally hard to recover from the protocol transcript |
| Advantage | \(\text{AnonKE}_\text{adv}[\mathcal{A}, P] = \Pr[\hat{k} = k]\) |
| Oracle | Passive only: \(\mathcal{A}\) sees the full transcript but cannot tamper |
| Secure if | \(\text{AnonKE}_\text{adv}[\mathcal{A}, P]\) is negligible in \(\lambda\) for all PPT \(\mathcal{A}\) |
| Limitation | No authentication: vulnerable to active man-in-the-middle. Use authenticated KE in practice. |