Score:1

Basis matrix of NTRU lattice

jp flag

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

\begin{equation} \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}. \end{equation}

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 \begin{equation} \mathbf{fh-u}q=\mathbf g, \quad \mathbf u \in \mathbf T, \end{equation}

which becomes in matrix form \begin{equation} \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} \end{equation} 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$?

Score:2
ru flag

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)$.

I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.