6
$\begingroup$

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?

$\endgroup$

1 Answer 1

7
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Thanks for the incredibly clear explanation! $\endgroup$
    – Ymi
    Nov 21, 2023 at 9:10
  • $\begingroup$ Quick followup: Why is it that this process does not work when we replace $X^i$ with some other arbitrary polynomial, e.g. $X^2 + 1$? Based on the last line of the decryption equation, the left expression is removed via modulo p but the right expression becomes something like $(X^2 +1)f(X)m(X)$, but multiplying it with the inverse of $(X^2 +1)f(X)$ doesn't seem to work. What gives? $\endgroup$
    – Ymi
    Nov 23, 2023 at 0:00
  • $\begingroup$ Multiplying by $X^2+1$ and other non-monomials is likely to increase the size of the coefficients of the products $r(X)g(X)$ and $f(X)m(X)$ and hence induce decryption failure rates when the coefficients wrap around the ends of the lifting interval. Decryption will still work in some cases (particularly if your small polynomial coefficients vary in sign), but the denser your arbitrary polynomial is and the larger its coefficients, the greater the chance of failure. $\endgroup$
    – Daniel S
    Nov 25, 2023 at 10:09

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.