NTRU格的基矩阵

Question

在NTRUEncrypt中，我们选择多项式\mathbf f,\mathbf g (具有适当的小系数)，使得\mathbf f允许逆\mathbf f_p, \mathbf f_q关于模p,q。使用公共\mathbf h=\mathbf f_q\mathbf g\text{ mod q}和私钥(\mathbf f, \mathbf f_p)之间的关系来定义一个格。

\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}

从\mathbf h\equiv \mathbf{f}_q\mathbf g\text{ mod } q中可以看出\mathbf f\mathbf h\equiv \mathbf g\text{ mod } q，因此是(\mathbf{f},\mathbf g)\in \mathcal L。相同的表达式可以编写为

\begin{equation} \mathbf{fh-u}q=\mathbf g, \quad \mathbf u \in \mathbf T, \end{equation}

以矩阵形式出现

\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}

并使用多项式的坐标

\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*}

为什么在这个展开式中需要\mathbf h所有循环移位的循环矩阵？

Answer 1

i第四列(i的循环移位)表示多项式x^ih(x)\mod{x^n-1}的系数。圆移位是因为环被定义为模多项式x^n-1。

如果我们只使用一列，这将意味着使用一个单项f(x)，例如，如果我们只使用第二列，它将给出方程(f_2x^2)h(x)-\mathbf u q=g(x)。