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


1 Answer 1


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.

  • $\begingroup$ Thanks for answering, Also I read that the error is chosen from a uniform probability distribution (Gaussian Distribution) and the parameter deciding the width of the Gaussian curve is its standard-deviation. This parameter is apparently decided upon while handshaking between A & B. Is this correct ? If so can you explain how this process occurs & why can't the error be guessed, if the attacker also knows standard-deviation of the distribution. $\endgroup$
    – Sujan SM
    Commented Feb 27, 2023 at 11:33
  • 1
    $\begingroup$ @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. $\endgroup$
    – Daniel S
    Commented Feb 27, 2023 at 12:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.