NTRU Cryptosystem: Why "rotated" coefficients of key f work the same as f

Question

In the NTRU cryptosystem, we can use a randomly generated polynomial f that is inversible under modulo p and q to encrypt and decrypt our plaintext. While studying this system, I attempted to bruteforce the value of f given a fixed g and a known plaintext for small parameters, and found that N total values of f were obtained that were able to decrypt correctly. They are also able to decrypt other plaintexts that were encrypted by the original f as well.

A closer inspection into these N different f's obtained showed that their coefficients were the same as the original f, but rotated. For example:

Coefficients of original f: [1, 1, 0, 1] -> x^3 + x^2 + 1
Rotated coefficients (values of f found by bruteforce):
[1, 1, 1, 0] -> x^3 + x^2 + x
[0, 1, 1, 1] -> x^2 + x + 1
[1, 0, 1, 1] -> x^3 + x + 1

Why do these other values of f also work when performing decryption and encryption?

Answer 1

In NTRUEncrypt we work with in the ring $\mathbb Z[X]/(X^N-1)$. it looks like for your example you have taken $N=4$.

In this ring, multiplying $X$ is equivalent to rotating the coefficients so that in your example \begin{align} f(X)&=X^3+X^2+1\\ Xf(X)&=X^4+X^3+X\equiv X^3+X+1 &\pmod{X^4-1}\\ X^2f(X)&=X^5+X^4+X^2\equiv X^2+X+1 &\pmod{X^4-1}\\ X^3f(X)&=X^6+X^5+X^3\equiv X^3+X^2+X &\pmod{X^4-1} \end{align} Lets write $f^{(i)}(X)=X^if(X)\mod{X^N-1}$ for your alternative private keys.

Now note that our public key $h(X)$ is chosen so that $$f(X)h(X)\equiv pg(X)\pmod{\langle X^N-1,q\rangle}$$ which in turn implies that $h(X)$ also satisfies $$f^{(i)}(X)h(X)\equiv pX^ig(X)\pmod{\langle X^N-1,q\rangle}$$ again we can write $g^{(i)}(X)=X^ig(X)\mod{X^N-1}$ for a corresponding set of polynomials whose coefficients are rotations of the coefficients of $g(X)$ and hence are also small.

Now let's see what happens when we run our decryption process using $f^{(i)}(X)$ over a ciphertext generated using $h(X)$. Our ciphertext $e(X)$ was generated as $r(X)h(X)+m(X)$ where $r(X)$ is a blinding polynomial with small coefficients. Multiplying it by $f^{(i)}(X)$ mod $\langle X^N-1,q\rangle$ then gives \begin{align}f^{(i)}(X)e(X)&=X^if(X)e(X)&\pmod{\langle X^N-1,q\rangle}\\ &=pX^ir(X)g(X)+X^if(X)m(X) &\pmod{\langle X^N-1,q\rangle}\\ &=pr(X)g^{(i)}(X)+f^{(i)}(X)m(X)&\pmod{\langle X^N-1,q\rangle} \end{align}

Now $r(X)g^{(i)}(X)$ (ditto $f^{(i)}(X)m(X)$) is the product of two polynomials with small coefficients and so the product itself is expected to have smallish coefficients. The usual NTRU argument says that the coefficients of the product are unlikely to wrap past the endpoints of the interval $[-q/2,q/2]$ so that with high probability we can directly lift $f^{(i)}(X)e(X)$ to a polynomial $a(X)$ in $\mathbb Z[X]/(X^N-1)$ and coefficients in that interval. Reducing this $a(X)\mod p$ is then with the same high probability simply $f^{(i)}(X)m(x)\mod p$ and multiplying by the inverse of $f^{(i)}(X)$ allows us to recover $m(X)$ just as in the intended decryption process.

If we work with variant rings ("NTRU NTT") of the form $\mathbb Z[X]/(X^N+1)$ there are still families of equivalent private keys produced by multiplying by $X$, but now the effect is a nega-cyclic rotation on the coefficients. The effect is less pronounced in NTRU prime where reduction mod $X^p-X-1$ means that multiplying by $X$ can increase coefficient size, although there is still some bounding effect.