# How is MLWE used for key generation in Kyber?

I've been reading about Crystal kyber, and i read that the in the key generation process, the public key pk is computed using secret key s in such a way that the error e is added to inner product of random matrix A & secret key s.

It is said that an attacker trying to crack secret key from public key needs to solve Module-LWE problem to do so, which is computationally hard.

My question is how is MLWE used in generating public-key & what makes it so hard so that an attacker cant brute force to crack the secret key s

In Kyber the matrix $$A$$ has special structure. Specifically, in Kyber512 it is of the form $$\begin{pmatrix}N_{1,1}&N_{1,2}\\ N_{2,1}&N_{2,2}\end{pmatrix}$$ in Kyber768 it is of the form $$\begin{pmatrix}N_{1,1}&N_{1,2}&N_{1,3}\\ N_{2,1}&N_{2,2}&N_{2,3}\\ N_{3,1}&N_{3,2}&N_{3,3}\end{pmatrix}$$ and in Kyber1024 it is of the form $$\begin{pmatrix}N_{1,1}&N_{1,2}&N_{1,3}&N_{1,4}\\ N_{2,1}&N_{2,2}&N_{2,3}&N_{2,4}\\ N_{3,1}&N_{3,2}&N_{3,3}&N_{3,4}\\ N_{4,1}&N_{4,2}&N_{4,3}&N_{4,4}\end{pmatrix}$$ where each $$N_{i,j}$$ is a negacirculant matrix of the form $$\begin{pmatrix} c_0 & c_1 & c_2&\ldots & c_{511}\\ -c_{511} & c_0 & c_1 &\ldots & c_{510}\\ -c_{510} & -c_{511} & c_0 &\ldots & c_{509}\\ \vdots & & &\ddots &\vdots\\ -c_1 &-c_2&-c_3&\ldots& c_0\end{pmatrix}.$$ The special form of this matrix means that the matrix multiplication $$\begin{pmatrix} c_0 & c_1 & c_2&\ldots & c_{255}\\ -c_{255} & c_0 & c_1 &\ldots & c_{254}\\ -c_{254} & -c_{255} & c_0 &\ldots & c_{253}\\ \vdots & & &\ddots &\vdots\\ -c_1 &-c_2&-c_3&\ldots& c_0\end{pmatrix}\begin{pmatrix} \ell_{255}\\ \ell_{254}\\ \vdots\\ \ell_0\end{pmatrix}=\begin{pmatrix} r_{255}\\ r_{254}\\ \vdots\\ r_0\end{pmatrix}.$$ Is consistent with the multiplication $$(c_0+c_1X+\cdots c_{255}X^{255})(\ell_0+\ell_1X+\cdots+\ell_{255}X^{255})=r_0+r_1X+\cdots+r_{255}X^{255}$$ when the multiplication is performed modulo $$X^{256}+1$$.
This means that in Kyber512, the expression $$A\mathbf s+\mathbf e$$ can equally be thought to represent the following matrix equation over the ring $$\mathbb Z[X]/\langle q, X^{256}+1\rangle$$ $$\begin{pmatrix} n_{1,1}(X) & n_{1,2}(X)\\ n_{2,1}(X) & n_{2,2}(X)\end{pmatrix}\begin{pmatrix}s_1(X)\\ s_2(X)\end{pmatrix}+\begin{pmatrix}e_1(X)\\ e_2(X)\end{pmatrix}$$ (with similar expressions for Kyber768 and Kyber1024). This is a module learning with errors problem with 2 samples (respectively 3 and 4 in the cases of Kyber768 and Kyber1024). We believe that the components of the answer vector are statistically indistinguishable from uniform elements of our ring.
To "brute force" a solution one would try all possible values of $$s_1(X)$$ and $$s_2(X)$$ to see if when multiplied by $$A$$ they producer an answer close to the public key. In Kyber512 the coefficients of the $$s_i(X)$$ are all from the range $$-3,-2,-1,0,1,2,3$$ which gives $$7^{512}$$ possibilities for the private key. Breaking Kyber512 is "only" meant to be as hard as brute-forcing a 128-bit key for which there are $$2^{128}$$ possibilities. Even if we are intelligent about our exhaust, the key space is much larger than that permitted by the security requirements.
• @SujanSM The error is sampled from a centred binomial distribution with $p=0.5$ and four coin tosses. This is part of the specification. Again this leads to $5^{512}$ possible errors in Kyber512, which is significantly more work than permitted by security requirements. Commented Feb 27, 2023 at 12:41