Cryptography is About Definitions, Not Secrets

Throughline

Security is not “the plaintext looks scrambled.” It is a quantified claim about an attacker, its resources, and what counts as winning.

1. Define the object before securing it

• A symmetric-key encryption scheme is $\Pi=(\mathsf{Gen},\mathsf{Enc},\mathsf{Dec})$:

$$k\leftarrow\mathsf{Gen}(1^\lambda),\qquad c\leftarrow\mathsf{Enc}_k(m),\qquad m':=\mathsf{Dec}_k(c)$$

• Explain the notation:
  • $\leftarrow$ allows randomized output.
  • $:=$ denotes deterministic assignment.
  • $\lambda$ indexes a family of schemes; for now, treat it as the security knob.
• Define correctness first:

$$\Pr[\mathsf{Dec}_k(\mathsf{Enc}_k(m))=m]=1$$

• Note that some schemes, especially lattice-based ones, permit negligible decryption failure; return to that in Part 6.
• Introduce Kerckhoffs's principle: algorithms are public, while generated secret values remain secret.
• Use a substitution cipher to separate “large key space” from “secure.”

Reference: Katz–Lindell §2.1

2. First attempt: reveal absolutely nothing

• Work one one-time-pad example:

$$\mathsf{Enc}(k,m)=m\oplus k,\qquad \mathsf{Dec}(k,c)=c\oplus k$$

• Define perfect secrecy through identical ciphertext distributions:

$$\mathsf{Enc}_k(m_0)\equiv\mathsf{Enc}_k(m_1)$$

• Give the equivalent posterior view:

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

• Explain why a uniform one-time-pad key achieves it.
• Show key reuse leaking the XOR of both messages:

$$c_1\oplus c_2=m_1\oplus m_2$$

• Use Shannon's theorem as the limit:

$$|\mathcal K|\ge|\mathcal M|$$

• Land the problem: perfect secrecy works, but securely distributing a message-sized one-use key is the problem encryption was meant to solve.

Reference: Katz–Lindell ch. 2; Shannon (1949)

3. The escape: computational security

• Weaken “identical distributions” to “no efficient algorithm can distinguish them.”
• Return to $\lambda$ and define:
  • adversary runtime: $\mathsf{poly}(\lambda)$
  • advantage: a function of $\lambda$
  • acceptable advantage: negligible in $\lambda$

$$\forall c>0,\ \exists N,\ \forall\lambda>N: \quad \nu(\lambda)<\frac1{\lambda^c}$$

• Use examples to separate asymptotic and concrete claims:

• Distinguish three quantities often collapsed into “security parameter”:
  • theoretical parameter $\lambda$
  • concrete parameter sizes, such as an RSA modulus or AES key
  • estimated security level, such as 128 bits of work
• Use the $2^{128}$ arithmetic as intuition only; not every scheme with $\lambda=128$ costs $2^{128}$ to break.

Reference: Katz–Lindell §3.1

4. The intuitive goal: semantic security

• State semantic security in the chosen-plaintext setting:

  Given a ciphertext and allowed side information, an efficient attacker should learn no efficiently computable property of the plaintext that it could not predict without the ciphertext.

• Use a concrete example: encrypting a salary should hide not only the amount but also predicates such as “is it above $100,000?”

• Explain why “the attacker cannot recover the entire plaintext” is too weak.

• Include equality and repeated-message leakage as useful counterexamples.

• Explain why the semantic definition matches the real goal but is cumbersome to prove directly.

Reference: Goldwasser–Micali (1982); Katz–Lindell ch. 3

5. The equivalent game: IND-CPA

• State the bridge explicitly: semantic security under chosen-plaintext attack is equivalent to IND-CPA.
• Define the experiment:
  1. $k\leftarrow\mathsf{Gen}(1^\lambda)$.
  2. The adversary queries an encryption oracle.
  3. It submits equal-length $m_0,m_1$.
  4. The challenger samples $b\leftarrow\{0,1\}$ and returns $c^*\leftarrow\mathsf{Enc}_k(m_b)$.
  5. The adversary may continue querying, then outputs $b'$.

$$\mathsf{Adv}^{\mathsf{ind\text{-}cpa}}_\Pi(A,\lambda) =\left|\Pr[b'=b]-\tfrac12\right|$$

• Require negligible advantage for every PPT adversary.
• Explain each design choice:
  • equal lengths remove trivial length leakage
  • oracle access models attacker-controlled plaintexts; for public-key encryption, anyone can encrypt already
  • randomized encryption prevents direct comparison
• Give the equivalence intuition:
  • learning a predicate distinguishes messages chosen to differ on that predicate
  • distinguishing messages reveals a predicate of the hidden message
• Show deterministic encryption losing immediately.
• Use ECB as the visual example: AES remains sound, but deterministic composition leaks structure.
• Keep the proof boundary clear:
  • a winning adversary disproves security
  • failing to find one does not prove security
  • a reduction proves that a winner would break an assumed-hard primitive

Reference: Katz–Lindell ch. 3

6. From definition to construction

• Show the smallest PRF-based randomized scheme:

$$r\leftarrow\{0,1\}^\lambda,\qquad c=(r,\ F_k(r)\oplus m)$$

• State the requirements:
  • $F_k(r)$ is at least as long as $m$
  • $F$ is a secure PRF
  • $r$ is fresh; collisions among polynomially many encryptions are negligible
• Sketch the hybrid proof:
  1. Replace $F_k$ with a truly random function using PRF security.
  2. Condition on a fresh $r$.
  3. The challenge mask is uniform, so the hidden bit is independent of the ciphertext.
• Record the concrete bound:

$$\mathsf{Adv}^{\mathsf{ind\text{-}cpa}} \le \mathsf{Adv}^{\mathsf{prf}} + O(q^2/2^\lambda)$$

• State what IND-CPA does not provide: ciphertext integrity or resistance to active tampering. That is the opening problem for Part 2.

Assumptions introduced

• One-way functions exist.
• PRFs can be constructed from one-way functions.
• Practical block ciphers such as AES are modeled as secure PRPs.

Go deeper

• Katz–Lindell ch. 2–3
• Boneh–Shoup ch. 2–5
• Goldwasser–Micali, Probabilistic Encryption (1982)
• Shannon, Communication Theory of Secrecy Systems (1949)
• Scribed applied cryptography notes, §2.1