1
$\begingroup$

I'm trying to recreate the wiki's example procedure, available here:

https://en.wikipedia.org/wiki/NTRUEncrypt

I've run into an issue while attempting to invert the polynomials.

The SAGE code below seems to be working fine for the given p=3, which is a prime number.

However, the representation of the polynomial in the field generated by q=32 ends up wrong, because it behaves as if the modulus was 2.

Here's the code in play:

F = PolynomialRing(GF(32),'a')
a = F.gen()
Ring = F.quotient(a^11 - 1, 'x')
x = Ring.gen()
pollist = [-1, 1, 1, 0, -1, 0, 1, 0, 0, 1, -1]

fq = Ring(pollist)
print(fq)
print(fq^(-1))

The Ring is described as follows:

Univariate Quotient Polynomial Ring in x over Finite Field in z5 of size 2^5 with modulus a^11 + 1

And the result:

x^10 + x^9 + x^6 + x^4 + x^2 + x + 1
x^5 + x + 1

I've tried to replace the Finite Field with IntegerModRing(32), but the inversion ends up demanding a field, as implied by the message:

NotImplementedError: The base ring (=Ring of integers modulo 32) is not a field

The desired result:

$fq(x) = 5+9X+6X^2+16X^3+4X^4+15X^5+16X^6+22X^7+20X^8+18X^9+30X^{10} (mod32)$

Any suggestions as to how I could obtain the correct inverse of f (mod q) would be greatly appreciated.

$\endgroup$
2
$\begingroup$

NTRU definitely does its arithmetic inside a ring like $\Bbb{Z}_q[X]/(X^N-1)$, so using the field $\Bbb{F}_q$ in place of $\Bbb{Z}_q$ is not right.

I am willing to take the error message at face value. The people behind Sage simply haven't implemented the calculation of inverses in rings like $R_m:=\Bbb{Z}_{2^m}[X]/(X^N-1)$ (IIRC in NTRU $q$ is always a power of two).

Here's how I would do it. First a general explanation, then your example:

Begin by calculating the inverse of $f$ in $R_1$, i.e. the inverse modulo $2$ and $X^N-1$. We need to view the coefficients of that inverse as integers rather than as elements of $\Bbb{Z}_2$. I don't know how to do that in Sage, but looks like the tricks you did with pollist is all you need to go back and forth.

At this point we have a polynomial $g_1(x)\in\Bbb{Z}[x]$ such that $$f(x)g_1(x)=1+2r_1(X)+(X^N-1)h_1(X)$$ for some polynomials $r_1(X),h_1(X)\in\Bbb{Z}[x]$. For what follows it is cleaner to write this as $$f(x)g_1(x)=1+2r_1(x)\in \Bbb{Z}[X]/(X^N-1).\qquad(*)$$

We next "lift" $g_1$ to an inverse of $f$ modulo $4$ as follows. Multiplying both sides of $(*)$ by $1-2r_1(x)$ gives $$f(x)g_1(x)(1-2r_1(x))=1-4r_1(x)^2.$$ The right hand side differs from $1$ by a multiple of four, so if we set $g_2(x)=g_1(x)(1-2r_1(x))$ (do the calculation in the ring $\Bbb{Z}[X]/(X^N-1)$), then $$ f(x)g_2(x)=1+4r_2(x)\in\Bbb{Z}[X]/(X^N-1).\qquad(**) $$ In other words, $g_2(x)$ works as an inverse of $f$ in the ring $R_2$ Furthermore, because $1-2r_1(x)\equiv1\pmod 2$ we get that $g_2\equiv g_1\pmod 2$ (that's why we call $g_2$ a lifting of $g_1$.

Next we multiply both sides of $(**)$ by $1-4r_2(X)$. Repeating the dose, I declare $g_3(x)=g_2(x)(1-4r_2(x))$ and as $$(1-4r_2(x))(1+4r_2(x))=1-16r_2(x)^2\equiv1\pmod{16}$$ we see that $g_3(x)$ is an inverse of $f$ modulo sixteen or, more precisely, in the ring $R_4$. Also $g_3\equiv g_2\pmod4$, so we are still lifting.

Next you get a polynomial $g_4$ that is congruent to $g_3$ modulo $16$, and an inverse of $f$ modulo $16^2$. In your example case $q$ was $32$ so you can stop here and reduce the coefficients of $g_4$ modulo $32$. If $q$ is a higher power of two you rinse and repeat as the necessity arises.


In a lifting process we first figure out the least significant bits of all the coefficients of the inverse (i.e. modulo $2$), then in the subsequent rounds of iteration we figure out the next (or a few next) bits, but the process must not disturb the already "frozen" less significant bits. This is a common technique in all $p$-adic algebra. We work modulo an increasing sequence of powers of a fixed prime $p$. The technique is actually related to several approximation techniques from the real side. That's because in the $p$-adic world the least significant (=units) bit is actually the boss term, and the rest of them are more or less just supporting cast of decreasing importance as the exponent goes up.


I show the above steps for your example (aided by Mathematica in those steps that you can hopefully do using Sage instead).

So $N=11$, $q=32$ and $f=-x^{10}+x^9+x^6-x^4+x^2+x-1$. First we calculate the inverse modulo $2$. I used Mathematica's command PolynomialExtendedGCD and got the same result you did, namely $$ g_1=1+x+x^5. $$ Then I calculate the product (pretending that the coefficients are usual integers) $$ fg_1=-1 + 2 x^2 + x^3 - x^4 - 2 x^5 + 2 x^6 + 2 x^7 + x^{14} - x^{15}. $$ We need to reduce that modulo $x^{11}-1$. Doing that gives $$ \begin{aligned} fg_1&\equiv-1 + 2 x^2 + 2 x^3 - 2 x^4 - 2 x^5 + 2 x^6 + 2 x^7\\ &=1+2(-1+x^2+x^3-x^4-x^5+x^6+x^7), \end{aligned} $$ so $$ r_1(x)=-1 + x^2 + x^3 - x^4 - x^5 + x^6 + x^7. $$ Therefore we can calculate $g_2=g_1(1-2r_1)$ first as a polynomial, then reduced modulo $x^{11}-1$: $$ \begin{aligned} g_2&=3 + 3 x - 2 x^2 - 4 x^3 + 7 x^5 - 6 x^7 - 4 x^8 + 2 x^9 + 2 x^{10} - 2 x^{11} - 2 x^{12}\\ &\equiv 1 + x - 2 x^2 - 4 x^3 + 7 x^5 - 6 x^7 - 4 x^8 + 2 x^9 + 2 x^{10}. \end{aligned} $$ As I promised, $g_2$ differs from $g_1$ only by a multiple of two. Next we need to calculate $fg_2$. Again first as polynomial and then modulo $x^{11}-1$ (you can probably combine these steps easily): $$ fg_2 \equiv 13 + 4 x + 4 x^3 - 12 x^4 - 16 x^5 + 12 x^6 + 24 x^7 - 4 x^8 - 24 x^9 - 4 x^{10}. $$ As promised, $g_2$ works as an inverse of $f$ modulo four because this product differs from $1$ by multiples of four only. We also read that $fg_2=1+4r_2$, where $$ r_2=3 + x + x^3 - 3 x^4 - 4 x^5 + 3 x^6 + 6 x^7 - x^8 - 6 x^9 - x^{10}. $$ Next we need to compute $g_3=g_2(1-4r_2)$ modulo $x^{11}-1$: $$ g_3\equiv -219 - 439 x + 54 x^2 + 464 x^3 + 132 x^4 - 273 x^5 - 192 x^6 - 10 x^7 + 36 x^8 + 210 x^9 + 222 x^{10}. $$ At this point we see that modulo $x^{11}-1$ we have $$ fg_3\equiv881 + 624 x - 1264 x^2 - 1440 x^3 + 896 x^4 + 1712 x^5 - 176 x^6 - 1184 x^7 - 304 x^8 + 112 x^9 + 128 x^{10}. $$ As promised the product is $\equiv1\pmod{16}$, but not yet modulo $q=32$. However, the numbers are becoming progressively kludgier (my own fault because I chose to work in $\Bbb{Z}[x]/(x^{11}-1)$ instead of modulo $32$). Anyway, you see that my $g_3$ differs from your target answer by multiples of sixteen only, so the next round will take you there. Leaving that to you!

$\endgroup$
  • $\begingroup$ It looks like you should actually be able to do all this in $\Bbb{Z}_q[X]/(X^n-1)$. You do need the ability to reinterpret a sequence of coeffcients from $\Bbb{Z}_{2^k}$ as elements of $\Bbb{Z}_{2^\ell}$ where $\ell>k$. At the level of coefficients such lifting is not unique, but we need it to calculate the error of our current "approximate inverse" $g_1,g_2,...$ The point is that the sequence $(g_k)$ will stabilize modulo $q$, and then you can stop. $\endgroup$ – Jyrki Lahtonen Feb 14 '18 at 18:24
  • $\begingroup$ I hope its clear that if $f$ has no inverse modulo $2$, then it won't have an inverse modulo a power of two either. $\endgroup$ – Jyrki Lahtonen Feb 15 '18 at 18:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.