2
$\begingroup$

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$?

$\endgroup$

1 Answer 1

2
$\begingroup$

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

$\endgroup$

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.