PQC · Lecture 1 · Florida Atlantic University · Fall 2026

Lecture 1: Why PQC, polynomial rings and MLWE

RSA, Diffie-Hellman and elliptic curves all fall to Shor's algorithm. This lecture shows why, then builds the replacement: polynomials mod q with xⁿ = −1, and the MLWE problem behind ML-KEM and ML-DSA. Every step uses one small example (q = 17, n = 4) that you can check by hand.

3problems Shor breaks: factoring, DLP, ECDLP

65,536products in one schoolbook multiplication at n = 256

2¹⁷⁸³guesses to brute-force an ML-KEM-768 secret

2024FIPS 203 and 204 published

What happens to RSA and elliptic curves when a large quantum computer exists?

The public-key crypto we use today

Public-key schemes you already know

Scheme	Used for	Hard problem	Where you saw it
Diffie-Hellman	key exchange	discrete log mod $p$	Assignment 4
RSA	encryption, signatures	factoring $N = p \cdot q$	Assignment 4
ECDH	key exchange	elliptic-curve discrete log	Assignment 5
ECDSA, EdDSA	signatures	elliptic-curve discrete log	Ed25519 example

TLS, SSH, VPNs and software updates all start with one of these.
AES and SHA-2 do not rely on a number-theory problem. AES gets its security from the key length, SHA-2 from the output length.

Recap: Diffie-Hellman with numbers

Public

p = 23

g = 5

Alice

secret

\Sec{a = 6}

sends

A = 5^{6} \bmod 23 = \Pub{8}

Bob

secret

\Sec{b = 15}

sends

B = 5^{15} \bmod 23 = \Pub{19}

Shared key

Alice:

19^{6} \bmod 23 = \Out{2}

Bob:

\;\;8^{15} \bmod 23 = \Out{2}

An attacker sees $5$ , $8$ , $19$ and must find $6$ or $15$ : the discrete log problem.
With a 3072-bit $p$ , no classical computer can do this. Keep this picture: in Lecture 3, ML-KEM does the same job with polynomials.

The quantum threat

Quantum computers in one slide

A quantum bit (qubit) can hold a mix of 0 and 1 at the same time. A group of qubits can hold a mix of many values.
It speeds up only problems with a special structure.
Factoring and discrete logs have exactly that structure: a hidden period.
The largest machines today have on the order of a thousand noisy qubits. A 2025 estimate (Gidney) says RSA-2048 falls to fewer than one million noisy qubits in under a week.
Optional: a good video introduction to quantum computers.

Shor and Grover

Algorithm	What it does	Affects	Fix
Shor	factoring and discrete log, fast	RSA, DH, ECDH, ECDSA	replace them
Grover	search $2^{k}$ keys in $\approx 2^{k/2}$ steps	AES, SHA-2	double key or hash size

Grover on AES

AES-128:

2^{128} \rightarrow 2^{64}

steps, too weak.
AES-256:

2^{256} \rightarrow 2^{128}

steps, still safe.

Shor on RSA

Work grows roughly with (key bits)

^3

.
RSA-15360 instead of RSA-2048 costs about

7.5^3 \approx 420

times more work, which is still easy for Shor.

Harvest now, decrypt later

The attack starts before the quantum computer exists, so the migration has to start years earlier.

The new NIST standards

Competition from 2016 to 2022. FIPS 203, 204 and 205 published in August 2024.
This course covers the two green ones. Both are built on one problem: MLWE.

When to switch: the CNSA 2.0 timeline

The NSA requires US national security systems to switch. Most deadlines fall between 2025 and 2033.

Polynomials as data

A polynomial is a list of numbers

In this lecture we never plug a value into $x$ . The polynomial is only a container for its coefficients.
In code, a polynomial is an array: a[0], a[1], ..., a[n-1].

Coefficients live mod $q$

Every coefficient is reduced mod $q$ , the same modular arithmetic as in the finite-field lectures.
Our toy modulus for the whole lecture: $q = 17$ .

Secrets and noise in PQC are small: coefficients between $-2$ and $2$ .
A small $-1$ is stored as $16$ , and $-2$ as $15$ . Think of $16$ as "just below zero".

The ring $\Rq = \mathbb{Z}_q[x]/(x^n+1)$

Two rules

$\mathbb{Z}_q$ : every coefficient is reduced mod $q$ .
$x^n + 1$ : we set $x^n = -1$ , so a polynomial never has more than $n$ coefficients.

Toy ring,

q = 17

n = 4

x^4 = -1

x^5 = x \cdot x^4 = -x

x^6 = x^2 \cdot x^4 = -x^2

Real rings

ML-KEM:

q = 3329

n = 256

ML-DSA:

q = 8380417

n = 256

Both use

x^{256} = -1

Addition in $\Rq$

Our running example in $\mathbb{Z}_{17}[x]/(x^4+1)$ , used again in Lecture 2: $a = 1 + 2x + 3x^2 + 4x^3, \qquad b = 5 + 6x + 7x^2 + 8x^3$
Add coefficient by coefficient, then reduce mod 17:

	$x^0$	$x^1$	$x^2$	$x^3$
$a$	1	2	3	4
$b$	5	6	7	8
$a + b$	6	8	10	12

Nothing reached 17 here. Subtraction works the same way: $a - b = (-4, -4, -4, -4) = (13, 13, 13, 13)$ .
Cost: $n$ additions, which is cheap.

Multiplication, step 1: every pair

Multiply every coefficient of $a$ by every coefficient of $b$ , like long multiplication.

$\times$	$5$	$6x$	$7x^2$	$8x^3$
$1$	$5$	$6x$	$7x^2$	$8x^3$
$2x$	$10x$	$12x^2$	$14x^3$	$16x^4$
$3x^2$	$15x^2$	$18x^3$	$21x^4$	$24x^5$
$4x^3$	$20x^3$	$24x^4$	$28x^5$	$32x^6$

$4 \times 4 = 16$ products. The red ones have a power of $x$ that is too high: $x^4$ , $x^5$ , $x^6$ .

Multiplication, step 2: collect by power

Add the products that share a power of $x$ (the diagonals of the table):

\begin{aligned} x^0&: \; 5 = 5 & x^4&: \; \Bad{16 + 21 + 24 = 61}\\ x^1&: \; 6 + 10 = 16 & x^5&: \; \Bad{24 + 28 = 52}\\ x^2&: \; 7 + 12 + 15 = 34 & x^6&: \; \Bad{32}\\ x^3&: \; 8 + 14 + 18 + 20 = 60 & & \end{aligned}

So far: $a \cdot b = 5 + 16x + 34x^2 + 60x^3 + \Bad{61x^4 + 52x^5 + 32x^6}$ .
This is ordinary polynomial multiplication. The ring rules come next.

Multiplication, step 3: fold back and reduce

$x^4 = -1$ moves the high part back to the start, with a minus sign.

Result: $a \cdot b = \Out{12 + 15x + 2x^2 + 9x^3}$ in $\mathbb{Z}_{17}[x]/(x^4+1)$ .

Try it

Multiplication in R_q, step by step

Step through the four stages with the running example, or type your own coefficients (four numbers mod 17).

The rule in one line

Multiplication in

\Rq

(negacyclic)

c_k \;=\; \sum_{i + j = k} a_i b_j \;-\; \sum_{i + j = k + n} a_i b_j \pmod q

Products that land past

x^{n-1}

wrap around to

x^{k}

and change sign.

Check one coefficient

c_0 = a_0 b_0 - (a_1 b_3 + a_2 b_2 + a_3 b_1) = 5 - (16 + 21 + 24) = -56 \equiv 12 \pmod{17}

c_3 = a_0 b_3 + a_1 b_2 + a_2 b_1 + a_3 b_0 = 8 + 14 + 18 + 20 = 60 \equiv 9 \pmod{17}

Your turn

Compute in $\mathbb{Z}_{17}[x]/(x^4+1)$ :

Exercise 1

(1 + x) \cdot x^3

Answer

x^3 + x^4 = x^3 - 1

= 16 + x^3

Exercise 2

(2 + x^2) \cdot 3x^2

Answer

6x^2 + 3x^4 = 6x^2 - 3

= 14 + 6x^2

What multiplication costs

Step 1 does all the work: one multiplication per pair, so $n \cdot n = n^2$ .
Steps 2 and 3 are only additions and subtractions.

Ring	$n$	Multiplications
Our toy	4	16
ML-KEM, ML-DSA	256	65,536

ML-KEM-768 key generation alone needs 9 of these products.

Vectors and matrices of polynomials

Same idea as vectors and matrices of numbers, but every entry is a polynomial in $\Rq$ .

\Pub{\mathbf{A}} = \begin{bmatrix} \Pub{A_{00}} & \Pub{A_{01}} \\ \Pub{A_{10}} & \Pub{A_{11}} \end{bmatrix} \in \Rq^{2 \times 2}, \qquad \Sec{\mathbf{s}} = \begin{bmatrix} \Sec{s_0} \\ \Sec{s_1} \end{bmatrix} \in \Rq^{2}

The size $k$ (here $k = 2$ ) is the security knob: larger $k$ , stronger scheme.
Count the numbers inside:
- Toy ( $k = 2$ , $n = 4$ ): $\mathbf{s}$ holds 8 numbers, $\mathbf{A}$ holds 16.
- ML-KEM-768 ( $k = 3$ , $n = 256$ ): $\mathbf{s}$ holds 768 numbers, $\mathbf{A}$ holds 2,304.

Matrix times vector

The usual row-times-column rule: $\Pub{\mathbf{A}} \cdot \Sec{\mathbf{s}} = \begin{bmatrix} \Pub{A_{00}} \cdot \Sec{s_0} + \Pub{A_{01}} \cdot \Sec{s_1} \\[0.5ex] \Pub{A_{10}} \cdot \Sec{s_0} + \Pub{A_{11}} \cdot \Sec{s_1} \end{bmatrix}$
Each " $\cdot$ " is a full ring multiplication from the last section. Each " $+$ " is a coefficient-wise addition.
Cost: $k^2$ ring multiplications, each costing $n^2$ .

ML-KEM-768

k^2 \cdot n^2 = 9 \cdot 65{,}536 = 589{,}824

multiplications for one

\mathbf{A} \cdot \mathbf{s}

One product, worked out

From the toy example on the next slides: $\Pub{A_{00}} = 3 + 10x + 7x^3$ and $\Sec{s_0} = 1 - x^2 + 2x^3$ .

	$x^0$	$x^1$	$x^2$	$x^3$	$x^4$	$x^5$	$x^6$
collect by power	3	10	$-3$	3	20	$-7$	14
fold ( $x^4 = -1$ )	$3 - 20$	$10 + 7$	$-3 - 14$	3
	$= -17$	$= 17$	$= -17$	$= 3$
mod 17	0	0	0	3

So $\Pub{A_{00}} \cdot \Sec{s_0} = 3x^3$ . Three coefficients happened to be multiples of 17.
In the same way, $\Pub{A_{01}} \cdot \Sec{s_1} = 12 + 13x + x^2 + 3x^3$ . Try it at home.

Module Learning With Errors (MLWE)

Warm-up: equations without noise

Plain numbers mod 17. Secret: $\Sec{x = 2}$ , $\Sec{y = -1}$ . Public:

\begin{aligned} x + \phantom{5}y &= \Pub{1} \\ x + 5y &= \Pub{14} \end{aligned} \pmod{17}

Subtract the first from the second: $4y = 13$ .
Multiply by $4^{-1} = 13$ (since $4 \cdot 13 = 52 = 3 \cdot 17 + 1$ ): $y = 13 \cdot 13 = 169 \equiv 16 = -1$ .
Then $x = 1 - y = 2$ .

Gaussian elimination finds the secret. The same works for

\Pub{\mathbf{t}} = \Pub{\mathbf{A}} \cdot \Sec{\mathbf{s}}

with polynomials.

Now add a little noise

Same secret, but each equation gets a small error: $\Noi{e = (+1, -1)}$ .

\begin{aligned} x + \phantom{5}y &= 1 \Noi{+ 1} = \Pub{2} \\ x + 5y &= 14 \Noi{- 1} = \Pub{13} \end{aligned} \pmod{17}

Same steps: $4y = 11$ , so $y = 11 \cdot 13 = 143 \equiv 7$ , and $x = 2 - 7 \equiv 12$ .
The answer $(12, 7)$ satisfies both equations exactly, yet the secret was $(2, -1)$ .
Why: elimination multiplied the noise by 13. An error of size 1 became an error of size 8.

With noise, elimination returns garbage. The attacker has to search for the secret instead.

Try it

Noise against elimination

Pick the two errors. With both at 0, elimination finds the secret. Any other choice gives a wrong answer.

The MLWE problem

MLWE

Given

\Pub{\mathbf{A}}

and

\Pub{\mathbf{t}} = \Pub{\mathbf{A}} \cdot \Sec{\mathbf{s}} + \Noi{\mathbf{e}}

, find

\Sec{\mathbf{s}}

.
No known algorithm solves this fast, on a classical or a quantum computer.

$\Pub{\mathbf{t}}$ looks like random numbers. Without $\Noi{\mathbf{e}}$ , it would give $\Sec{\mathbf{s}}$ away.

A toy MLWE instance

$q = 17$ , $n = 4$ , $k = 2$ . Each box is one polynomial, written as its 4 coefficients.

Check the first row: $\Pub{A_{00}} \Sec{s_0} + \Pub{A_{01}} \Sec{s_1} + \Noi{e_0} = (0,0,0,3) + (12,13,1,3) + (1,-1,0,0) = \Pub{(13, 12, 1, 6)}$ .
An attacker gets only the blue boxes and must recover the lavender ones.

Why not just try every secret?

Every coefficient of $\Sec{\mathbf{s}}$ is one of 5 values: $-2, -1, 0, 1, 2$ .

	Coefficients in $\mathbf{s}$	Guesses
Toy ( $k = 2$ , $n = 4$ )	8	$5^{8} = 390{,}625$	a laptop: instant
ML-KEM-768 ( $k = 3$ , $n = 256$ )	768	$5^{768} \approx 2^{1783}$	impossible

Smarter attacks exist and do much better than guessing.
Against ML-KEM-768, the best known ones still cost more than breaking AES-192.

Try it

How many secrets are there?

Change the matrix size k, the polynomial length n and the range of the small coefficients.

Real parameters

Scheme	$n$	$q$	Matrix	Small range	Security
ML-KEM-512	256	3329	$2 \times 2$	$\pm 3$	128-bit
ML-KEM-768	256	3329	$3 \times 3$	$\pm 2$	192-bit
ML-KEM-1024	256	3329	$4 \times 4$	$\pm 2$	256-bit
ML-DSA-44	256	8380417	$4 \times 4$	$\pm 2$	128-bit
ML-DSA-65	256	8380417	$6 \times 5$	$\pm 4$	192-bit
ML-DSA-87	256	8380417	$8 \times 7$	$\pm 2$	256-bit

Same $n = 256$ everywhere, so the same polynomial code serves all six.

Why polynomials and not plain numbers?

The same 768 secret numbers with a matrix of plain numbers would need a $768 \times 768$ matrix.

Matrix	Numbers stored	Size (12 bits each)
plain numbers, $768 \times 768$	589,824	about 885 KB
polynomials, $3 \times 3$ of $n = 256$	2,304	about 3.5 KB

A polynomial packs 256 numbers that are tied together by the ring rules.
In Lecture 3 the matrix shrinks again, to a 32-byte seed that both sides expand.

Where we go next

Summary

What we have

Shor breaks RSA, DH and ECC. Grover only forces AES-256.
Data lives in polynomials with coefficients mod $q$ and the rule $x^n = -1$ .
MLWE: from $\Pub{\mathbf{A}}$ and $\Pub{\mathbf{t}} = \Pub{\mathbf{A}}\Sec{\mathbf{s}} + \Noi{\mathbf{e}}$ , nobody can recover the small secret $\Sec{\mathbf{s}}$ .
ML-KEM and ML-DSA are built on MLWE.

The bottleneck

One polynomial product costs

n^2 = 65{,}536

multiplications, and one

\mathbf{A} \cdot \mathbf{s}

needs

k^2

of them.

Can we multiply two polynomials with far fewer than

n^2

multiplications?

The public-key crypto we use today

Public-key schemes you already know

Recap: Diffie-Hellman with numbers

The quantum threat

Quantum computers in one slide

Shor and Grover

Harvest now, decrypt later

The new NIST standards

When to switch: the CNSA 2.0 timeline

Polynomials as data

A polynomial is a list of numbers

Coefficients live mod qq

The ring Rq=Zq[x]/(xn+1)\Rq = \mathbb{Z}_q[x]/(x^n+1)

Addition in Rq\Rq

Multiplication, step 1: every pair

Multiplication, step 2: collect by power

Multiplication, step 3: fold back and reduce

Multiplication in Rq, step by step

The rule in one line

Your turn

What multiplication costs

Vectors and matrices of polynomials

Vectors and matrices of polynomials

Matrix times vector

One product, worked out

Module Learning With Errors (MLWE)

Warm-up: equations without noise

Now add a little noise

Noise against elimination

The MLWE problem

A toy MLWE instance

Why not just try every secret?

How many secrets are there?

Real parameters

Why polynomials and not plain numbers?

Where we go next

Summary

Coefficients live mod $q$

The ring $\Rq = \mathbb{Z}_q[x]/(x^n+1)$

Addition in $\Rq$

Multiplication in R_q, step by step