Cryptography — Foundations¶
Job: Define asymptotic security for encryption and signatures; ground classical public-key schemes in number-theoretic hardness; state reduction-based security goals and information-theoretic baselines.
Core¶
Syntax and correctness¶
Public-key encryption: keygen \(\to(pk,sk)\); \(\mathrm{Enc}_{pk}(m)\to c\); \(\mathrm{Dec}_{sk}(c)\to m\). Correctness: \(\mathrm{Dec}_{sk}(\mathrm{Enc}_{pk}(m))=m\) except negligible error.
Signatures: keygen \(\to(vk,sk)\); \(\mathrm{Sign}_{sk}(m)\to\sigma\); \(\mathrm{Verify}_{vk}(m,\sigma)\to\{0,1\}\). Correctness on honestly signed messages.
Symmetric / AEAD (pointer): shared-key encryption and authenticated encryption (AES-GCM) handle bulk data; public-key often only wraps keys (hybrid).
Asymptotic security model¶
Security parameter \(\lambda\in\mathbb{N}\). Adversaries are PPT algorithms. \(\varepsilon(\lambda)\) is negligible if \(\forall c\,\exists\lambda_0\,\forall\lambda\ge\lambda_0:\ \varepsilon(\lambda)<\lambda^{-c}\). Advantage of an adversary in a game must be negligible for the scheme to be secure.
| Notion | Informal meaning |
|---|---|
| OW | hard to invert a random image of \(f\) |
| IND-CPA | ciphertexts indistinguishable under chosen-plaintext attacks |
| IND-CCA | same under adaptive chosen-ciphertext attacks |
| EUF-CMA | existential unforgeability under chosen-message attacks |
| PRP / PRF | block ciphers / keyed functions \(\approx\) random (symmetric) |
Semantic security \(\Leftrightarrow\) IND-CPA (Goldwasser–Micali) for public-key encryption in the asymptotic PPT model. Random oracle model: hash functions idealized as random functions — heuristics, not standard model.
Hardness assumptions (classical)¶
| Assumption | Statement (schematic) |
|---|---|
| Factoring | given \(N=pq\), recover \(p,q\) |
| RSA | invert \(x\mapsto x^e\bmod N\) without \(d\) |
| DL | given \(g,g^x\) in group, recover \(x\) |
| CDH | given \(g^a,g^b\), compute \(g^{ab}\) |
| DDH | distinguish \((g^a,g^b,g^{ab})\) from \((g^a,g^b,g^c)\) |
DDH can be easy where CDH is hard (e.g. \(\mathbb{F}_p^\times\) with pairing-friendly structure care). Elliptic curve groups: smaller keys for conjectured DL hardness.
Classical schemes¶
RSA (textbook vs secure). Textbook \(c=m^e\bmod N\) is deterministic \(\Rightarrow\) not IND-CPA. OAEP + random-oracle heuristics yield IND-CCA in idealized models; standard-model RSA-based PKE needs richer assumptions.
Diffie–Hellman key exchange: Alice \(g^a\), Bob \(g^b\), shared \(g^{ab}\). Passive security \(\leftarrow\) CDH; authenticated channels needed against MITM. ElGamal: CPA-secure under DDH (in groups where DDH holds).
Hybrid encryption: KEM/DEM — encapsulate a symmetric key under PKE/KEM; encrypt bulk under AEAD. Composition theorems: IND-CCA KEM + secure DEM \(\Rightarrow\) IND-CCA PKE under standard conditions.
Digital signatures: RSA-FDH / PSS (ROM); Schnorr / ECDSA (DL-based); hash-then-sign paradigm requires collision resistance of the hash.
Information-theoretic baseline¶
One-time pad: \(C=M\oplus K\), \(K\) uniform independent, \(|K|\ge|M|\) \(\Rightarrow\) \(I(M;C)=0\) (perfect secrecy). Shannon: perfect secrecy requires \(H(K)\ge H(M)\). Modern crypto: computational bounded adversaries; insecurity negligible rather than zero.
Secure multiparty computation / secret sharing (pointer): Shamir sharing over fields; information-theoretic thresholds vs computational MPC.
Reductions and post-quantum¶
Security proofs: PPT break of scheme \(\Rightarrow\) PPT algorithm for RSA/DDH/LWE/… — reductions, not unconditional hardness. Tightness of reductions matters for parameter selection.
Post-quantum: Shor breaks factoring/DL on a large quantum computer. NIST-track: lattices (Kyber/Dilithium — MLWE/MSIS), codes, hash-based signatures (SPHINCS+), isogenies (history: SIKE broken). Quantum security models (QROM) are subtle.
Complexity map (one-liners)¶
| Primitive | Relies on (classically) |
|---|---|
| RSA-OAEP | RSA + ROM heuristics |
| DH / ElGamal | CDH / DDH in group |
| AES-GCM | PRF/PRP assumptions + nonces |
| Hybrid TLS-style | KEM + AEAD + signatures + PKI |
See it¶
Reduction sketch. Scheme security proofs show: adversary \(\mathcal{A}\) breaking IND-CPA with advantage \(\varepsilon\) yields algorithm \(\mathcal{B}\) solving DDH (say) with advantage \(\approx\varepsilon\). Parameters chosen so that best known attacks on DDH cost \(\ge 2^{128}\) operations — not a proof that \(P\neq NP\).
Why randomness is mandatory. Deterministic PKE: adversary encrypts \(m_0,m_1\) itself and compares to challenge ciphertext — IND-CPA advantage \(1\).
Check¶
Why is deterministic public-key encryption never IND-CPA?
Adversary sends \(m_0\neq m_1\), receives \(c=\mathrm{Enc}(m_b)\), re-encrypts both and compares. Indistinguishability fails with advantage \(1\). Randomness in \(\mathrm{Enc}\) is mandatory.
State perfect secrecy and Shannon's bound.
\(I(M;C)=0\) (equivalently \(\mathbb{P}(M=m\mid C=c)=\mathbb{P}(M=m)\)). For perfect secrecy with uniform \(M\) of length \(n\) bits, key entropy \(\ge n\).
What does IND-CCA add beyond IND-CPA?
Adversary may query decryption on chosen ciphertexts (except the challenge). Prevents malleability attacks (e.g. textbook RSA / plain ElGamal homomorphisms).
Pitfalls¶
- “RSA is secure” without padding/game-based definitions is meaningless.
- Hardness is conjectural; reductions relate schemes to problems.
- Side channels, bad RNG, padding oracles, and nonce reuse dominate real breaks.
- ROM proofs can fail when hash is instantiated (ROM uninstantiability results).
- Quantum: “double the bits” is not a universal rule; use scheme-specific estimates.
Refs¶
Katz–Lindell, Introduction to Modern Cryptography; Goldreich I–II; Boneh–Shoup (online); HAC (Menezes et al.); NIST PQC documentation.
Next¶
Number theory foundations · Modular arithmetic · Information theory · Abstract algebra