Key Generation

Module-LWE hands us a trapdoor almost directly, and key generation is mostly that observation plus engineering.

Pick a uniform matrix $A \in R_q^{k \times k}$ and a short secret vector $\mathbf{s} \in R_q^k$. Compute

$$\mathbf{t} \;=\; A\mathbf{s} + \mathbf{e}$$

with a short error $\mathbf{e}$. The Module-LWE assumption from Chapter 4 says the pair $(A, \mathbf{t})$ is indistinguishable from uniform to any polynomial-time attacker, classical or quantum. So $(A, \mathbf{t})$ is a public key, and $\mathbf{s}$ is the trapdoor.

Everything below is the practical version of that.

01.The steps

K1. Derive two seeds. Start from 32 random bytes $d$ and hash:

$$(\rho, \sigma) \;=\; G(d),$$

where $G$ is SHA3-512, whose 64 output bytes split into two 32-byte halves. The first seed $\rho$ will produce the matrix, the second $\sigma$ will produce the secret and error.

K2. Expand $\rho$ into $A$. Feed $\rho$ into SHAKE128, an extendable output function that produces an arbitrarily long pseudorandom byte stream, and rejection-sample that stream into elements of $\mathbb{Z}_q$. The result is a matrix $A$ whose $k^2$ ring elements are uniform over $R_q$.

Rejection sampling is needed because the stream produces 12-bit values in $[0, 4095]$ and only those below $q = 3329$ are usable. Values at or above $q$ are discarded rather than reduced, because reducing would make small residues more likely than large ones and the matrix would not be uniform. The cost is that roughly one in five candidates is thrown away.

The important property is that this is deterministic. Anybody holding $\rho$ reconstructs exactly the same $A$.

That is worth a moment, because it is the first of several "regenerate rather than transmit" decisions. Storing $A$ outright would cost $k^2 \cdot n \cdot 12 / 8$ bytes, which at $k = 3$ is $3456$ bytes. Storing $\rho$ costs $32$. The matrix travels as a seed and is rebuilt at both ends.

K3. Sample $\mathbf{s}$ and $\mathbf{e}$. From $\sigma$, draw every coefficient of both vectors from the centred binomial distribution $\text{CBD}_{\eta_1}$ described in Chapter 3. For $\eta_1 = 2$ each coefficient is

$$a_1 + a_2 - b_1 - b_2$$

with the four values independent uniform bits, giving a small symmetric distribution on $\{-2, -1, 0, 1, 2\}$ peaked at zero.

Both vectors are short. That is what makes $\mathbf{s}$ usable as a trapdoor, and it is why the scheme is a lattice scheme rather than linear algebra.

K4. Compute $\mathbf{t} = A\mathbf{s} + \mathbf{e}$. This is $k^2$ ring multiplications, and they are done in the NTT domain using Chapter 4's transform. Both $A$ and $\mathbf{t}$ are kept in NTT domain afterwards.

K5. Serialise.

$$pk \;=\; (\rho,\; \hat{\mathbf{t}}), \qquad sk \;=\; \hat{\mathbf{s}},$$

where the hat marks NTT representation.

For $k = 3$ that gives a public key of $32 + 3 \cdot 384 = 1184$ bytes, and a secret key of $1152$ bytes for the encryption layer, which the wrapper in The Fujisaki-Okamoto Wrapper later extends.

02.Why the public key is stored transformed

Step K4 said $A$ and $\mathbf{t}$ stay in the NTT domain, and FIPS 203 specifies the public key that way on the wire. That is not an implementation detail, it is part of the standard.

The reason is that the public key is used repeatedly. Every client that ever connects to Bob runs encryption against the same $pk$, and encryption needs $A$ and $\mathbf{t}$ in transformed form. If the key were stored in coefficient form, every client would begin by performing $k^2 + k$ forward transforms that produce the same result every time.

Storing it transformed removes all of them. It is the pattern flagged in Chapter 4: keep data in the NTT domain as long as possible, and let the transform boundaries fall where data genuinely enters or leaves.

There is a small cost. The transformed representation is not compressible in the way the coefficient form would be, which is part of why public keys are not compressed while ciphertexts are. Compression and Ciphertext Size returns to that.

03.Where the security sits

Restating what an attacker faces after key generation.

They see $\rho$, from which they can reconstruct $A$ exactly. They see $\hat{\mathbf{t}}$. They want $\mathbf{s}$.

That is precisely a Module-LWE instance: recover the short secret from $(A, A\mathbf{s} + \mathbf{e})$. By the assumption, and via Regev's reduction behind it, doing so is at least as hard as approximating the shortest vector in a lattice of dimension $k \cdot 256$.

Nothing about publishing $\rho$ helps them, because $A$ was never secret. The secret is $\mathbf{s}$, and it is hidden by $\mathbf{e}$.