⚛️ Chapter 8 — Post-Quantum Cryptography (PQC) Cheat Sheet

🗺️ Big Picture

Classical Crypto          Quantum Threat              PQC Solution
──────────────────────────────────────────────────────────────────
RSA (factoring)    ──►   Shor's Algorithm     ──►    Kyber (MLWE)
ECDSA (DL problem) ──►   Shor's Algorithm     ──►    Dilithium (MLWE)
AES (brute force)  ──►   Grover's Algorithm   ──►    AES-256 (double key)
Access Control     ──►   All pubkey broken    ──►    Lattice CP-ABE

$\boxed{\text{The hard problems of the quantum era: LWE, MLWE, SVP, CVP}}$

1. Classical Cryptography — Foundation

Two Types of Classical Crypto

$\boxed{\text{RSA} \leftarrow \text{Integer Factorization} \qquad \text{ECC / DH} \leftarrow \text{Discrete Logarithm}}$

🔢 Analogy: Factoring is like being given a 300-digit number and asked "which two primes multiply to give this?" — classical computers would take longer than the age of the universe.

2. The Quantum Threat

Classical Bit vs. Qubit

🪙 Analogy: A classical coin is either Heads or Tails. A quantum coin while spinning is both at once — it only picks a side the moment you look at it (measurement collapses superposition).

Quantum Computer Progress

Challenges: fragile quantum states, measurement collapses state, needs extreme isolation — still a long way to full fault-tolerant quantum computation.

Two Algorithms That Break Crypto

Shor's Algorithm (1994)

• Solves integer factorization AND discrete logarithm in polynomial time
• Breaks: RSA, ECDSA, DSA, Diffie-Hellman — exponentially faster than classical
• Result: Entire PKI ecosystem invalid. TLS/VPN compromised.

🔐 Analogy: A combination lock with a billion combinations. Classically, you try one-by-one. Shor's tries all combinations simultaneously and instantly identifies the right one.

Grover's Algorithm

• Gives a quadratic speedup in unstructured search
• Classical: $O(N)$ → Quantum: $O(\sqrt{N})$
• Weakens symmetric crypto — does NOT break it outright
• Fix: just use longer keys

🏫 Lecturer note: AES is still secure — just use AES-256!

Impact Summary

⚠️ The "Harvest Now, Decrypt Later" Attack

Today:     Attacker records encrypted traffic ────► stores ciphertext
Future:    Quantum computer exists ────────────────► decrypts stored data!

• State secrets, medical records, financial data encrypted today could be decrypted in the future
• NIST (USA) regulates and standardizes the response
• Even if attacker has ciphertext now → technology not yet capable → but they're waiting

Mosca's Theorem — When Must We Act?

Let:

• $x$ = how long the data needs to stay secure
• $y$ = how long it takes to migrate to quantum-safe solutions
• $z$ = how long until a large-scale quantum computer exists

$\boxed{\text{If } x + y > z, \text{ then worry NOW}}$

🏠 Analogy: Your house needs to stand 20 more years ($x=20$). Rebuilding takes 5 years ($y=5$). Earthquake coming in 15 years ($z=15$). Since $20 + 5 = 25 > 15$ — you're already too late to start.

3. Post-Quantum Cryptography (PQC)

$\boxed{\text{PQC} = \text{Classical algorithms secure against BOTH classical AND quantum attacks}}$

• Runs on normal (classical) computers — no quantum hardware needed
• Can be deployed as a software upgrade
• Secure against both classical and quantum adversaries

Why PQC Takes Time to Deploy

PQC Families

NIST Standardization Results

4. Lattice-Based Cryptography — The Most Promising Family

What Is a Lattice?

🏠 Analogy: Think of floor tiles. The corners of all the tiles form a regular grid of points. That grid is a lattice.

Formally — all integer combinations of basis vectors:

\boxed{\Lambda = \left{ \sum_{i=1}^{n} a_i b_i ;\Big|; a_i \in \mathbb{Z} \right}}

Key properties:

• Only integer coefficients (no fractions!)
• Infinite number of lattice points
• Regular repeating structure

Simple 2D example: $b_1 = (2,0),\ b_2 = (0,3)$ → Lattice = ${(2a,\ 3c)\ |\ a,c \in \mathbb{Z}}$

• Is $(12, 0)$ in the lattice? → $a=6$, $c=0$ → ✅ Yes
• Is $(5, 1)$ in the lattice? → $a=2.5$ → ❌ No (not integer)

In Kyber: dimension is $n = 512$ or $768$ — exponentially harder than 2D!

🧊 High-dimension analogy: In 2D, you can visually see the nearest grid point. In 768 dimensions, there is no "looking" — every direction looks equally far away, and the number of nearby points grows exponentially.

Hard Lattice Problems

Shortest Vector Problem (SVP)

Find the shortest non-zero vector in the lattice.

$\boxed{\lambda_1(\Lambda) = \min_{v \in \Lambda \setminus {0}} |v|}$

• Easy in 2D/3D
• Exponentially hard in $n = 512+$ dimensions
• No efficient quantum algorithm known

Closest Vector Problem (CVP)

Given a target point off the grid, find the nearest lattice point.

$\boxed{v \in \Lambda \text{ such that } |t - v| \text{ is minimized}}$

• Easy in 2D (you can see it)
• Exponentially hard in $n = 512+$: can't "see" structure, distances behave counter-intuitively, best known attacks are exponential-time

SVP vs CVP vs LWE Summary

$\boxed{\text{All three become exponentially hard as dimension grows}}$

5. Learning With Errors (LWE)

Core Equation

$\boxed{b = As + e \pmod{q}}$

Given: $A$ and $b$ → Goal: Recover $s$ — computationally hard!

📊 Analogy: 1000 equations like $3x + 5y + 7z \approx 42$, but each has a tiny random rounding error added. Without knowing the errors, you cannot solve for $x, y, z$ — even with a quantum computer!

Why the Noise Makes It Hard

With noise → must find $s$ such that $|b - As|$ is small → Closest Vector Problem → exponential time.

Why LWE Is Quantum-Safe

$\text{Breaking LWE} \equiv \text{Breaking SVP/CVP} \equiv \text{Exponential Time}$

LWE won the Gödel Prize 2018 — foundation for "nearly every kind of cryptographic object."

6. Module-LWE (MLWE)

$\boxed{\text{MLWE = LWE in Polynomial Form}}$

Instead of integer vectors, work over polynomial rings:

• Ring: $R_q = \mathbb{Z}_q[x]/(x^n + 1)$
• $\mathbf{A}$ = matrix of polynomials; $\mathbf{s}, \mathbf{e}$ = vectors of polynomials
• Same equation: $\mathbf{b} = \mathbf{A}\mathbf{s} + \mathbf{e}$ — but polynomials

Advantages over plain LWE:

• Uses NTT (Number Theoretic Transform) for fast polynomial multiplication
• Smaller key sizes than plain LWE
• Faster computation
• Preserves lattice hardness

"MLWE is just LWE, but smarter and faster."

NIST MLWE Algorithms

7. CRYSTALS-Kyber (Key Encapsulation Mechanism)

Based on MLWE. Used in TLS/SSL, VPN, secure messaging.

🔒 KEM Analogy: Bob puts a padlock on an empty box and sends it to Alice (public key). Alice puts a secret note inside, snaps the lock, sends it back (encapsulation). Only Bob has the key to open it (decapsulation). Now both know the same secret.

⚠️ Unlike RSA: In Kyber, the Receiver (Bob) generates the key, not the sender.

Kyber Step 1: KeyGen — Bob (Receiver)

$\boxed{pk = (\mathbf{A},\ \mathbf{t}), \quad sk = \mathbf{s}}$

Bob sends $pk$ to Alice.

Kyber Step 2: Encaps — Alice (Sender)

$\boxed{c = (\mathbf{u},\ v), \quad K}$

Alice sends ciphertext $c$ to Bob — NOT $K$.

Kyber Step 3: Decaps — Bob (Receiver)

$\boxed{K_{Alice} = K_{Bob}}\ ✅$

Why does decryption work? $v - \mathbf{u}^T \mathbf{s} = (t^T r + e_2 + \lfloor q/2 \rfloor m) - (A^T r + e_1)^T s$

The lattice components cancel (since $t = As + e$), leaving $\approx \lfloor q/2 \rfloor m$ — small noise rounds away cleanly.

Full Kyber KEM Protocol

Bob (KeyGen)              Alice (Encapsulate)              Bob (Decapsulate)
─────────────────────────────────────────────────────────────────────────────
(pk, sk) ──pk──►         m ← random                       m' = Dec(sk, c)
                          (K', r) = G(m ∥ H(pk))           (K'', r') = G(m' ∥ H(pk))
                          c = Enc(pk, m; r)                 if Enc(pk, m'; r') = c:
                          K = KDF(K' ∥ H(c))  ◄──c──        K = KDF(K'' ∥ H(c))
                                                            else:
                                                             K = KDF(z ∥ H(c))

Kyber Hash Chain

$H(pk) = \text{SHA3-256}(pk)$ $(K', r) = \text{SHA3-512}(m | H(pk))$ $\boxed{K = \text{SHAKE256}(K' | H(c))}$

Kyber's Role

• ❌ Does NOT encrypt data directly
• ✅ Establishes a shared symmetric key $K$
• Then: $C = \text{AES-GCM}(K, M)$ — symmetric encryption takes over

This is why AES is still relevant post-quantum — Kyber securely negotiates the AES key!

⭐ Exam: Why Is Kyber Still Safe If Attacker Has the Public Key?

Because the attacker does not have $sk = \mathbf{s}$. The secret key is never shared. Breaking $\mathbf{t} = \mathbf{As} + \mathbf{e}$ to recover $\mathbf{s}$ is the MLWE problem — exponentially hard even for quantum computers.

8. CRYSTALS-Dilithium (Digital Signature)

Replaces RSA and ECDSA. Based on MLWE. Operations over $R_q = \mathbb{Z}_q[x]/(x^n+1)$.

✍️ Analogy: A digital signature is a mathematical handwritten signature — anyone can verify it was you, but no one can forge it. Dilithium makes this quantum-resistant.

Dilithium KeyGen

$\boxed{pk = (\mathbf{A},\ \mathbf{t_1}), \quad sk = (\mathbf{s_1},\ \mathbf{s_2},\ \mathbf{t_0})}$

Dilithium Sign(sk, m)

$\boxed{\sigma = (c,\ \mathbf{z})}$

Dilithium Verify(pk, m, σ)

$\boxed{\text{Accept if } c' = c, \text{ otherwise Reject}}$

9. Manual Kyber Exercise (Small Example)

Given: $q = 17$, $A = \begin{bmatrix} 3 & 5 \\ 7 & 2 \end{bmatrix}$, $s = [2, 1]$, $e = [1, 1]$, $r = [1, 2]$, $m = 1$, $e_1 = [1, 0]$, $e_2 = 1$

Step 1: Public Key $t = As + e \pmod{17}$ $As = \begin{bmatrix}3&5\\7&2\end{bmatrix}\begin{bmatrix}2\\1\end{bmatrix} = \begin{bmatrix}11\\16\end{bmatrix}, \quad t = \begin{bmatrix}11+1\\16+1\end{bmatrix} = \begin{bmatrix}12\\0\end{bmatrix} \pmod{17}$

Step 2: Ciphertext $u = A^T r + e_1 \pmod{17}, \quad v = t^T r + e_2 + \lfloor 17/2 \rfloor \cdot m \pmod{17}$ $\lfloor 17/2 \rfloor = 8, \quad m=1 \Rightarrow v = t^T r + 1 + 8 \pmod{17}$

Step 3: Decrypt $v - s^T u \pmod{17}$ → result should be close to $8$ (since $\lfloor q/2 \rfloor = 8$)

Step 4: Recover $m$ → if result $\approx 8$ → $m = 1$; if $\approx 0$ → $m = 0$

Step 5: Shared Key $K = H(m)$ — relationship: $K$ is the hash of $m$

10. Lattice CP-ABE (Post-Quantum Access Control)

What Is Attribute-Based Encryption (ABE)?

🏥 Analogy: A hospital file encrypted so only someone who is both a Doctor AND from Hospital-A (or an Emergency worker) can decrypt it. The access rule is baked into the encryption itself — not enforced by a server.

$\boxed{\text{Policy example: (Doctor AND Hospital-A) OR Emergency}}$

Core idea: Data encrypted under an access policy. Users can only decrypt if their attributes satisfy the policy.

Result: Fine-grained access control embedded at the data level.

Four Entities

Cryptographic Lifecycle

Setup → Key Generation → Encryption → Decryption

Phase 1: Setup — Trapdoor Generation

$\boxed{PK = A, \quad MK = T_A}$

$(A, T_A) \leftarrow TrapGen(n, m, q)$ — random matrix with trapdoor

• $A$ = public matrix (everyone knows it)
• $T_A$ = trapdoor (secret master key for Authority only)

🚪 Trapdoor = a mathematical backdoor. Without $T_A$, impossible to invert $A$. With $T_A$, easy. One-way unless you know the secret.

Phase 2: Key Generation — Trapdoor Sampling

$\boxed{Ax = u \pmod{q} \quad \text{and} \quad |x| \text{ is small}}$

$x \leftarrow SampleD(A, T_A, u)$ — sampled from a discrete Gaussian distribution

Output: Secret Key $SK_S$ tied exclusively to the user's attributes.

Phase 3: Encryption — LSSS Policy

Policy encoded as Linear Secret Sharing Scheme (LSSS): $(M, \rho)$ where $M$ = sharing matrix, $\rho(i)$ = attribute for row $i$.

Example — policy (Doctor AND Hospital-A) OR Emergency:

$\boxed{C_0 = A^T\mathbf{s} + \mathbf{e}, \quad C_i = A_{\rho(i)}^T s + e_i + \lambda_i}$

• $C_0$ = global secret vector
• Each $C_i$ = LSSS share for attribute $i$ hidden inside LWE ciphertext
• Noise $e, e_i$ ensures LWE hardness

"LSSS splits the encryption secret into linear shares associated with attributes; only attribute sets satisfying the policy can reconstruct the secret and decrypt."

Phase 4: Decryption

If user's attributes satisfy the policy → combine attribute keys: $\sum_i \lambda_i SK_i$

To recover: $\boxed{M = C_1 - s^T A}$

Noise gracefully cancels out during subtraction → reveals message $M$.

ABE Advantages vs. Challenges

⚡ Key Facts to Remember