Chapter 8 - Post-Quantum Cryptography (PQC)

Standardizing Security for the Quantum Era

Classical Cryptography Foundation

The Two Types of Classical Crypto

Symmetric-Key Cryptography

• Alice and Bob share a secret key beforehand
• Example: AES, Chacha20

Public-Key Cryptography

• Alice can send a secure message without ever meeting Bob
• Example: RSA, ECC

Key Insight: Classical crypto security relies on math problems that are too hard for modern computers to solve quickly.

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

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

The Quantum Threat

What Makes Quantum Computers Different?

Classical Bit vs Qubit

• Classical bit: either 0 OR 1
• Qubit: can be 0 AND 1 at the same time (superposition)
  • Mathematically: $|\psi\rangle = \alpha|0\rangle + \beta|1\rangle$

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

Why this matters: Quantum computers can explore many possibilities simultaneously, giving them exponential speedups on certain problems.

Quantum Algorithms That Break Crypto

Shor's Algorithm (1994)

• A polynomial-time quantum algorithm
• Solves integer factorization and discrete logarithm exponentially faster than classical computers
• Result: RSA, ECC, and Diffie-Hellman are all fundamentally vulnerable
• อาจารย์บอกว่า AES is still secure เลยนะ!!
  • → Longer key size, more secure

Grover's Algorithm

• Gives a quadratic speedup in unstructured search
• Classical: $O(N)$ → Quantum: $O(\sqrt{N})$
• Weakens symmetric crypto (but doesn't break it outright)

Analogy for Shor's: Imagine a huge combination lock with a billion combinations. Classically, you try them one by one. Shor's algorithm is like being able to try all combinations simultaneously and instantly identify the right one.

Quantum Computer Progress Timeline

• Still a long way to full fault-tolerant quantum computation
• Challenges: measurement collapses state, quantum states are fragile, need extreme isolation

Impact on Current Algorithms

Vulnerable (Broken by Large-Scale Quantum)

• RSA (e.g., RSA-2048 broken by Shor's)
• ECDSA / Elliptic Curve Cryptography
• DSA / Finite Field Cryptography
• Diffie-Hellman Key Exchange

Impact: PKI ecosystem invalid, TLS/VPN compromised.

Adaptable (Usable with Adjustments)

• AES → Requires longer keys (use AES-256)
• Triple DES → Requires longer keys
• SHA-2 / SHA-3 → Use longer output

Why is AES okay? Grover's only gives a square-root speedup. AES-128 effectively becomes ~64-bit against quantum — not great. AES-256 becomes ~128-bit — still secure enough.

⚠️ The "Harvest Now, Decrypt Later" Attack

Adversaries can:

1. Record encrypted traffic today
2. Decrypt it later once quantum computers exist

This means data encrypted right now could be vulnerable in the future — including state secrets, medical records, financial data.

แม้ว่าตอนนี้ Attacker ได้ Ciphertext ไปก็ยังเอาไปทำอะไรไม่ได้ เพราะว่า Technology capabilities ยังไม่ถึง

• NIST (USA) เป็นคน regulate เรื่องพวกนี้

Mosca's Theorem — When Do We Need to Worry?

Let:

• $x$ = how long the encrypted data needs to stay secure
• $y$ = how long it takes to migrate infrastructure 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: If your house needs to stay standing for 20 more years ($x=20$), and it takes 5 years to rebuild ($y=5$), but an earthquake is coming in 15 years ($z=15$) — you're already too late to start building.

Post-Quantum Cryptography (PQC)

What is PQC?

$\boxed{\text{PQC} = \text{Classical algorithms that are secure against quantum attacks}}$

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

Why PQC Takes Time

• Efficiency: New algorithms must be fast enough for real-world use
• Confidence: Needs years of cryptanalysis to trust
• Standardization: NIST has been running a competition since 2016
• Interoperability: Must work with TLS, IKE, VPNs, etc.

Families of Post-Quantum Cryptography

NIST Standardization Progress

พวก Mathematicians อยากจะส่ง Algorithm เข้า NIST กันมาก คงเพราะอยากได้เงินเนี่ยแหละ5555

• 3rd Round → Selected for standardization:
  • Public-key encryption: Kyber (Lattice-based)
  • Signatures: Dilithium, FALCON (Lattice), SPHINCS+ (Hash-based)
• 4th Round → Selected 2025:
  • Public-key encryption: HQC (Code-based)

Lattice-Based Cryptography — The Most Promising Family

What is a Lattice?

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

Formally, a lattice is all integer combinations of some basis vectors:
$\boxed{\Lambda = \left\{ \sum_{i=1}^{n} a_i b_i \;\Big|\; a_i \in \mathbb{Z} \right\}}$
Where $b_1, b_2, \ldots, b_n \in \mathbb{R}^n$ are linearly independent basis vectors.

Properties:

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

Simple Example

Let $b_1 = (2, 0)$ and $b_2 = (0, 3)$

$\text{Lattice} = \{ab_1 + cb_2 \mid a, c \in \mathbb{Z}\}$

Some lattice points:

• $(0, 0)$ — $a=0, c=0$
• $(2, 0)$ — $a=1, c=0$
• $(4, 0)$ — $a=2, c=0$
• $(2, 3)$ — $a=1, c=1$
• $(6, 9)$ — $a=3, c=3$
• $(-2, -3)$ — $a=-1, c=-1$

General form: $(2a, 3c)$ for any integers $a, c$.

Is $(12, 0)$ in the lattice?

• $12 = 2a \Rightarrow a = 6$ ✅ (integer)
• $0 = 3c \Rightarrow c = 0$ ✅ (integer)
• Yes! $(12, 0) = 6b_1 + 0b_2$ ✅

Is $(5, 1)$ in the lattice?

• $5 = 2a \Rightarrow a = 2.5$ ❌ (not integer)
• $(5, 1)$ is NOT in the lattice ❌

Why Lattices Are Hard in High Dimensions

In Kyber (real PQC), the dimension is $n = 512$ or $768$.

We ask: can a target vector be written as

$a_1 b_1 + a_2 b_2 + \cdots + a_{768} b_{768}$

• We have
  • 768 basis vectors ($b_i$ → directions - basis vectors)
  • 768 integer multipliers ($a_i$ → integer multiples (how many steps))
  • Points in 768-dimensional space ($n$ → number of directions = dimension)

This becomes extremely difficult when:

• $n = 512$ or $768$ dimensions
• Basis vectors are large and skewed
• Noise is added

Analogy: In 2D, finding the nearest point on a grid is easy — you can just look. In 768 dimensions, there is no "looking." Every direction looks almost the same distance away, and the number of nearby points grows exponentially.

The number of basis vectors ($n$) = the dimension of the lattice.

อย่าลืม Add section In Praise of LWE
→ No algorithm can break LWE right now!

Hard Lattice Problems

Shortest Vector Problem (SVP)

Definition: Given a lattice $\Lambda$ with basis $B = \{b_1, \ldots, b_n\}$, find the shortest non-zero lattice vector:

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

Intuition: "What is the shortest arrow you can make from the origin using the grid's directions?"

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

Closest Vector Problem (CVP)

Definition: Given a lattice $\Lambda$ and a target point $t \in \mathbb{R}^n$, find the lattice vector closest to $t$:

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

Intuition: "Find the nearest grid point to a given off-grid point."

Why CVP is hard:

• Easy in 2D (you can visually see the nearest point)
• Extremely hard in $n = 512+$ because:
  • Can't "see" the structure
  • Number of nearby points explodes
  • Distances behave counter-intuitively
  • Everything looks almost equally far away
  • Best known attacks are exponential-time

SVP vs CVP vs LWE Summary

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

This shared hardness is why lattice-based crypto is post-quantum secure.

Learning With Errors (LWE)

The Core Idea

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

Where:

• $A \in \mathbb{Z}_q^{m \times n}$ → public matrix (known to everyone)
• $s \in \mathbb{Z}_q^n$ → secret vector (what we want to hide)
• $e \in \mathbb{Z}_q^m$ → small noise (random small error)
• $b \in \mathbb{Z}_q^m$ → public output
• $q$ → modulus

Given: $A$ and $b$
Goal: Recover secret $s$ — this is computationally hard!

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

Why LWE is Hard — Two Cases

Case 1: No Noise ($e = 0$)

$b = As$

• This is just a linear system
• Solvable using Gaussian elimination
• Easy → polynomial time ✅

Case 2: With Noise ($e \neq 0$)

$b = As + e$

• $e$ is small but unknown
• Now $b - As = e$, and there is no exact linear solution
• ===Must find $s$ such that $\|b - As\|$ is small===
• This becomes a Closest Vector Problem (CVP) in high dimension
• Exponentially hard → no efficient classical or quantum algorithm ✅

Why LWE is Secure

LWE = Hardness of SVP + CVP

LWE security is mathematically reduced to the worst-case hardness of SVP and CVP. This means:

• Breaking LWE = Breaking SVP/CVP
• Breaking SVP/CVP = exponential time
• Therefore LWE is exponentially hard to break

LWE won the Gödel Prize 2018 for revolutionizing cryptography in both theory and practice. It serves as the foundation for "nearly every kind of cryptographic object."

Module-LWE (MLWE)

พูดง่าย ๆ ก็คือ MLWE = LWE in Polynomial Form

LWE but over polynomial rings (structured generalization):

Instead of vectors of integers, we work with:

• Vectors of polynomials
• Over ring $R_q = \mathbb{Z}_q[x]/(x^n + 1)$

The equation remains the same form:

$\mathbf{b} = \mathbf{A}\mathbf{s} + \mathbf{e}$

But now $\mathbf{A}$ is a matrix of polynomials, $\mathbf{s}$ and $\mathbf{e}$ are vectors of polynomials.

Why Module over Polynomial Ring?

• Highly structured → faster computation
• Uses NTT (Number Theoretic Transform) for fast polynomial multiplication modulo a prime
• Smaller keys than plain LWE
• Preserves lattice hardness

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

NIST Standardized MLWE Algorithms

• CRYSTALS-Kyber → Key Encapsulation (MLWE)
• CRYSTALS-Dilithium → Digital Signature (MLWE)

CRYSTALS-Kyber (Key Encapsulation)

What is Kyber?

• Based on MLWE
• Designed for Key Encapsulation Mechanism (KEM)
• Used in: TLS/SSL, VPN, Secure messaging

Analogy for KEM: Think of a KEM like a special lockbox. Bob puts a padlock on an empty box and sends it to Alice (public key). Alice puts a secret note inside, snaps the lock, and sends it back (encapsulation). Only Bob has the key to open it (decapsulation). They now both "know" the same secret note.

Step 1: KeyGen (Receiver — Bob)

Input: Security parameters
Output: Public key $pk$, Secret key $sk$

1. Generate public polynomial matrix: $\mathbf{A} \in R_q^{k \times k}$
2. Sample small secret vector: $\mathbf{s} \leftarrow \text{small in } R_q^k$
3. Sample small error vector: $\mathbf{e} \leftarrow \text{small in } R_q^k$
4. Compute public vector: $\mathbf{t} = \mathbf{As} + \mathbf{e}$
5. Output:

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

Bob sends $pk$ to Alice (the encryptor).

จะไม่เหมือน RSA นะที่ คน GenKey จะต้อง เป็นคนที่จะเริ่มสื่อสาร (Sender)
อันนี้ Receiver ต้องเป็นคน GenKey

Step 2: Encaps (Sender — Alice)

Input: Public key $pk = (\mathbf{A}, \mathbf{t})$
Output: Ciphertext $c$, Shared secret $K$

1. Choose random message/seed $m$
2. Derive shared secret: $K = H(m)$ (Hash)
3. Sample small random values: $\mathbf{r}, \mathbf{e_1}, e_2 \leftarrow \text{small}$
4. Compute ciphertext part 1: $\mathbf{u} = \mathbf{A}^T \mathbf{r} + \mathbf{e_1}$
5. Compute ciphertext part 2: $v = \mathbf{t}^T \mathbf{r} + e_2 + m$
6. Output:

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

แล้วก็ส่ง $c$ ไปให้ Bob, not $K$

Where:

• $t$ = public key vector
• $r$ = random vector chosen by sender
• $e_2$ = small noise
• $m$ = random message bits (used to derive key)

Encryption formula (detail):

$u = A^T r + e_1$
$v = t^T r + e_2 + \lfloor q/2 \rfloor m$

Step 3: Decaps (Receiver — Bob)

Input: Ciphertext $c = (\mathbf{u}, v)$, Secret key $sk = \mathbf{s}$
Output: Shared secret $K$

1. Compute estimate of message: $m' = v - \mathbf{u}^T \mathbf{s}$
2. Derive shared key: $K = H(m')$
3. Output $K$

Why does $v - \mathbf{u}^T \mathbf{s}$ recover $m$?

$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 out (since $t = As + e$), leaving approximately $\lfloor q/2 \rfloor m$ — and the small noise terms are small enough to round away.

Kyber

• ❌ Data Enc
• ✅ Secure Communication (based on Symmetric Encyption → เพราะว่า AES พวกนี้ ยังปลอดภัยสำหรับ Post Quantum Attack)

Full Kyber KEM Protocol (Alice–Bob)

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))

KEM Step 3: Turn Encryption into Key Exchange

Kyber does not encrypt data directly. Instead it encrypts a random value to establish a shared key.

Alice:

1. Generate random message $m$
2. Encrypt it: $c = Enc(pk, m)$ ↔ $c = (u, v)$
3. Derive shared key: $K = KDF(K' \| H(c))$

Final result:

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

This shared key $K$ is then used for symmetric encryption:

$C = \text{AES-GCM}(K, M)$

Full Hash Chain in Kyber

① Hash public key:

$H(pk) = \text{SHA3-256}(pk)$

② Hash expansion:

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

③ Final key derivation:

$\boxed{K = \text{SHAKE256}(K' \| H(c))}$

อย่าลืมใส่ตรงนี้ missing heading

Why Kyber is Quantum-Secure

• Security based on MLWE hardness
• High-dimensional lattice problems
• No efficient quantum attack is known
• If Kyber is secure → attacker cannot compute $K$, even with a quantum computer

AES and Quantum

Grover's algorithm gives only a quadratic speedup on symmetric crypto:

→ Symmetric crypto is still usable — just use longer keys.

CRYSTALS-Dilithium (Digital Signatures)

What is Dilithium?

• A Post-Quantum Digital Signature scheme
• Based on MLWE and structured lattice problems
• Designed to replace RSA and ECDSA
• All operations over polynomial ring: $R_q = \mathbb{Z}_q[x]/(x^n + 1)$

Analogy: A digital signature is like a handwritten signature, but mathematical. Anyone can verify it was you who signed a document, but no one can forge your signature. Dilithium makes this quantum-resistant.

Dilithium KeyGen

1. Generate matrix: $\mathbf{A} \in R_q^{k \times l}$ (using a seed for compact storage)
2. Sample small polynomials: $\mathbf{s_1} \in R_q^l, \quad \mathbf{s_2} \in R_q^k$
3. Compute public vector: $\mathbf{t} = \mathbf{A}\mathbf{s_1} + \mathbf{s_2}$
4. Split $\mathbf{t}$ into high bits $\mathbf{t_1}$ and low bits $\mathbf{t_0}$ (reduces signature size)

Output:

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

Dilithium Sign(sk, m)

Dilithium Verify(pk, m, σ)

Post-Quantum Access Control: Lattice CP-ABE

Pairing ก็ vulnerable ต่อ Post quantum attack อยู่ดี

What is Attribute-Based Encryption (ABE)?

Analogy: Imagine a hospital where a file is encrypted so that 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.

Core Idea: Data is encrypted under an access policy. Users can only decrypt if their attributes logically satisfy the policy constraints.

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

The Outcome: Fine-grained access control embedded at the data level, not relying on perimeter security.

The Four Entities

The Cryptographic Lifecycle

1. Setup → 2. Key Generation → 3. Encryption → 4. Decryption

1. Setup: Authority generates master keys and public parameters
2. Key Generation: User receives secret keys based on their attributes
3. Encryption: Data owner encrypts the message, embedding the access policy
4. Decryption: User decrypts only if their attributes satisfy the embedded policy

Phase 1: Setup

Generate random matrix using Trapdoor Generation:

$A \in \mathbb{Z}_q^{n \times m}$

$(A, T_A) \leftarrow TrapGen(n, m, q)$

Output:

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

• $PK$ = Public Key (the matrix $A$, known to everyone)
• $MK$ = Master Key (the trapdoor $T_A$, kept secret by Authority)

What is a trapdoor? A mathematical backdoor. Without $T_A$, it's computationally infeasible to invert $A$. With $T_A$, it's easy. Like a one-way door — easy to go through one way, impossible the other way, unless you know the secret.

Phase 2: Key Generation

For user with attribute set $S = \{\text{attr}_1, \text{attr}_2, \ldots\}$:

Authority uses lattice trapdoor sampling:

$x \leftarrow SampleD(A, T_A, u)$

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

The vector $x$ is sampled from a discrete Gaussian distribution.

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

Phase 3: Encryption

Data owner picks policy, creates a Linear Secret Sharing Scheme (LSSS):

An LSSS is defined as $(M, \rho)$ where:

• $M \in \mathbb{Z}_q^{l \times n}$ = sharing matrix
• $\rho(i)$ = maps row $i$ to an attribute

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

The secret is shared across attributes using the LSSS matrix:

$\lambda_i = M_i \cdot s$

Where $\lambda_i$ is the share assigned to attribute $\rho(i)$.

Ciphertext components:

Choose random $\mathbf{s} \in \mathbb{Z}_q^n$, then:

$\boxed{C_0 = A^T\mathbf{s} + \mathbf{e}}$
$\boxed{C_1 = M + \left\lfloor\frac{q}{2}\right\rfloor}$

For each attribute row $i$:

$C_i = A_{\rho(i)}^T s + e_i + \lambda_i$

• $C_0$ contains the global secret vector $s$
• Each $C_i$ hides the LSSS share $\lambda_i$ inside an LWE ciphertext
• Noise vectors $e, e_i$ ensure LWE hardness

"LSSS embeds the access policy into encryption by splitting the encryption secret into linear shares associated with attributes; only attribute sets satisfying the policy can linearly reconstruct the secret and decrypt."

Phase 4: Decryption

If user's attributes satisfy the policy:

User combines their attribute keys:
$\sum_i \lambda_i SK_i$
To recover:
$\boxed{M = C_1 - s^T A}$
Why this works:
$\left(M + \left\lfloor\frac{q}{2}\right\rfloor\right) - (A^T s + \cancel{e})$
Because the noise $e$ is intentionally small, the errors gracefully cancel out during subtraction, revealing the pristine message $M$.

Advantages vs Challenges

Exercise - Manual Kyber Computation

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$

Compute:

1. Public key $t = As + e \pmod{17}$
2. Ciphertext $u = A^T r + e_1 \pmod{17}$ and $v = t^T r + e_2 + \lfloor q/2 \rfloor \cdot m \pmod{17}$
3. Bob computes $v - s^T u \pmod{17}$
4. Recover $m$
5. Compute shared key $K = H(m)$

Summary

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 size)
Access Control     ──►   All pubkey broken    ──►    Lattice CP-ABE

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

All classical public-key security assumptions (factoring, discrete log) are broken by Shor's. The quantum-safe replacements (LWE/MLWE) rely on high-dimensional lattice problems that no known quantum algorithm can solve efficiently.