# Why was A doubled in size

Why was the dimension of A doubled in kyber?

LWE encryption uses a public matrix A of dimension K but kyber uses a double matrix A resulting in $$A ^{ k * k * n }$$

When deriving the results of the definition of gen, enc en dec this results in:

$$RA_0 S + RA_1 S + RE + E_3 + \frac{q}{2}m - RA_0 S + RA_1 S + ES \\$$

Which reduces into: $$RE + E_3 + \frac{q}{2}m - ES$$

Which is equivalent to the $$A^k$$ scheme. Why was the size of A increased by $$k$$?

• For some module dimension $k$ (a security parameter), $A\in R_q^{k\times k}$, a $k\times k$ matrix with entries in $R_q=\mathbb{Z}[x]/(q,x^{256}+1)$ with $q=3329$. In the specification, it is actually $\hat{A}$, the number theoretic transform of $A$ that is expanded from seed (or its transpose). For practical purposes, $A$ or $\hat{A}$ is a $k\times k$ matrix with entries that are 256-dimensional vectors over $\mathbb{Z}/q\mathbb{Z}$, or more simply a $k\times k \times256$ array with integer entries (say in the range $[0,q)$).
– yoyo
Mar 22 at 20:44
• @yoyo exactly, but the theory already works for a $k \times 256$ array, so why was it made to be $k \times k \times 256$? Mar 22 at 21:23
• You may want to compare different learning with errors key exchanges: LWE (like FRODO), RLWE (like NewHope), and MLWE (like Kyber). They're all very similar, but use algebraic structures of increasing complexity.
– yoyo
Mar 22 at 21:40