# Basis matrix of NTRU lattice

In NTRUEncrypt, we choose polynomials $$\mathbf f,\mathbf g$$ (with suitably small coefficients) such that $$\mathbf f$$ admits inverses $$\mathbf f_p, \mathbf f_q$$ with respect to the moduli $$p,q$$. The relationship between the public $$\mathbf h=\mathbf f_q\mathbf g\text{ mod q}$$ and the private key $$(\mathbf f, \mathbf f_p)$$ is used to define a lattice

$$$$\mathcal L=\{(\mathbf u,\mathbf v)\in \mathbf T\times \mathbf T\text{ t.c. } \mathbf u\mathbf h\equiv \mathbf v\mod q\}\subset \mathbb Z^{2N}.$$$$

From $$\mathbf h\equiv \mathbf{f}_q\mathbf g\text{ mod } q$$ it follows that $$\mathbf f\mathbf h\equiv \mathbf g\text{ mod } q$$, therefore $$(\mathbf{f},\mathbf g)\in \mathcal L$$. The same expression can be written as $$$$\mathbf{fh-u}q=\mathbf g, \quad \mathbf u \in \mathbf T,$$$$

which becomes in matrix form $$$$\begin{pmatrix} \mathbf f \\ \mathbf g \end{pmatrix}=\begin{pmatrix} 1 & 0 \\ \mathbf h & q \end{pmatrix}\begin{pmatrix} \mathbf f \\ - \mathbf u \end{pmatrix}$$$$ and using the coordinates of the polynomials $$\begin{equation*}\scriptsize{ \begin{pmatrix} f_0 \\ f_1 \\ \vdots \\ f_{N-1} \\ g_0 \\ g_1 \\ \vdots \\ g_{N-1} \end{pmatrix} = \left(\begin{array}{@{}cccc|cccc@{}} 1 & 0 & \cdots & 0 & 0 & 0 & \cdots & 0 \\ 0 & 1 & \cdots & 0 & 0 & 0 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 1 & 0 & 0 & \cdots & 0 \\ \hline h_0 & h_1 & \cdots & h_{N-1} & q & 0 & \cdots & 0 \\ h_{N-1} & h_0 & \cdots & h_{N-2} & 0 & q & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \ddots & \vdots \\ h_1 & h_2 &\cdots & h_0 & 0 & 0 & \cdots & q \end{array}\right) \begin{pmatrix} f_0 \\ f_1 \\ \vdots \\ f_{N-1} \\ -u_1 \\ -u_2 \\ \vdots \\ -u_{N-1} \end{pmatrix}. } \end{equation*}$$ Why do we need in this expansion the circulant matrix of all cyclic shifts of $$\mathbf h$$?

The $$i$$th column (which is a circular shift by $$i$$) represents the coefficients of the polynomial $$x^ih(x)\mod{x^n-1}$$. The circular shifts are because the ring is defined modulo the polynomial $$x^n-1$$.
If we only used one column, this would mean using a monomial $$f(x)$$ e.g. if we only used the second column this would give the equation $$(f_2x^2)h(x)-\mathbf u q=g(x)$$.