How to find the inverse of a polynomial in NTRU-PKCS

Question

I am coding a java based implementation of the NTRU public-key cryptosystem. I can comprehend the majority of the algorithms involved in the encryption and decryption process well enough, but the key generation process is giving me serious trouble.

I'll briefly go over some basics of the cryptosystem for those that are unfamiliar, otherwise, skip ahead to the paragraph titled The Problem.

We'll be working with polynomials with degree $<n$. Adding and subtracting these polynomials functions normally, however multiplying these polynomials works different¹². Given two polynomial $A$ and $B$ of degree $<n$, their product is $$A \cdot B = c_0\,x^0 + c_1\,x^1 + \ldots + c_{n-1}\,x^{n-1} = C$$ where each coefficient $c_k$ is calculated by³: $$c_k=\sum_{0\le i<n}a_i\,b_{(k-i\bmod n)}$$ ^{multiplying each coefficient of $a$ with the same from $b$ in reverse order (if $b_k$ is the first coefficient in $b$ then $b_{k-1}$ loops around to the last coefficient in $b$ and so on) ensure the degree of the resulting polynomial remains $<n$.}

The key $F$ is a polynomial with coefficients in $\{-1,0,1\}$. An example (where $n=7$) is: $$1\,x^0 + 0\,x^1 + 0\,x^2 + 1\,x^3 + -1\,x^4 + -1\,x^5 + 0\,x^6$$ or more plainly: $$1 + x^3 - x^4 - x^5$$

$F$ functions as the private key but must be verified to have inverse polynomials $F_q$ and $F_p$, which are polynomials of degree $<n$ with integer coefficients $q_i$ with $0 \leq q_i < q$, and $p_i$ with $0 \leq p_i < p$, where $q$ and $p$ are predefined integers ($q$ is coprime with prime $p$).

$F$ must satisfy that $F_q$ and $F_p$ exist given:

$$F \cdot F_q \equiv 1 \pmod q \quad\text{and}\quad F \cdot F_p \equiv 1 \pmod p$$ that is, if we define $C=F \cdot F_q$, its coefficients $c_k$ must verify $$c_k\bmod q=\begin{cases}1&\text{if }k=0\\0&\text{otherwise}\end{cases}$$ and same for $F \cdot F_p \equiv 1 \pmod p$.

With all that being said…

The Problem

I am still struggling to grasp the algorithm used to calculate the polynomial inverses of the private polynomial key $F$, $F_p$, and $F_q$ for $$F\cdot F_q \equiv 1 \pmod q$$ and for $p$ etc.

Or to even verify if $F$ is invertible. I've seen different pseudocodes explaining the algorithm but all I've seen are poorly elaborated. Other explanations of the algorithm amount to "You can calculate the inverse using the extended euclidean algorithm" with no example, and looking at the eea myself I'm still none the wiser on how it's applied. I'd greatly appreciate a concise explanation in relation to the polynomial $F$ integer $p/q$ and polynomial degree $n$.

Let me know if there seems to be any key concepts I'm missing or critical variables I've omitted.

---

^{Notes of the editors:}
¹ ^{In this modified polynomial multiplication, $x^n$ is assumed to be $1$ in coefficients of degree $\ge n$.}
² ^{Equivalently, this is polynomial multiplication modulo $x^n-1$.}
³ ^{$u \bmod n$ is defined as the integer $v$ with $0\le v<n$ and $u−v$ a multiple of $n$.}

Answer 1

Disclaimer: I'm not familiar with NTRU, and not in my comfort zon. Hence the many edits.

The problem asked can be summarized as: given $n$, $q$ coprime to prime $p$, and for $0\le i<n$ the coefficients $f_i\in\{-1,0,1\}$ of $F=\displaystyle\sum_{0\le i<n}f_i$, find the $n$ coefficients $q_i$ of $F_q$ and $p_i$ of $F_p$ such that, with polynomial multiplication performed modulo $x^n-1$, $F\cdot F_q\equiv1\pmod q$ and $F\cdot F_p\equiv1\pmod p$, or determine that's impossible.

We can treat the problem for $F_q$. The same method will apply for $F_p$. Alternatively, since $q$ and $p$ are coprime, we can find $H$ with $F\cdot H\equiv1\pmod{(p\,q)}$ and if it exists reduce its coefficient modulo $q$ and $p$ to find the $q_i$ and $p_i$ (but if there's no $H$, we could only conclude that at least one of $F_q$ or $F_p$ does not exist).

---

One conceptually simple method is to see the problem as a system of $n$ linear equations in $\Bbb Z_q$, with $n$ unknowns $q_i$, obtained by using the question's definition for the equivalent equation $F_q\cdot F\equiv1\pmod q$: $$\forall k\in[0,n-1),\quad \sum_{0\le i<n}q_i\,f_{(k-i\bmod n)}\equiv\begin{cases}1&\text{if }k=0\\0&\text{otherwise}\end{cases}\pmod q$$ and use Gaussian elimination. If we use the question's $F=1+x^3-x^4-x^5$ for $n=7$, that linear system goes$$ q_0-q_2-q_3+q_4\equiv1\pmod q\\ q_1-q_3-q_4+q_5\equiv0\pmod q\\ q_2-q_4-q_5+q_6\equiv0\pmod q\\ q_3-q_5-q_6+q_0\equiv0\pmod q\\ q_4-q_6-q_0+q_1\equiv0\pmod q\\ q_5-q_0-q_1+q_2\equiv0\pmod q\\ q_6-q_1-q_2+q_3\equiv0\pmod q$$ that is, by realigning$$\begin{matrix} +q_0& &-q_2&-q_3&+q_4& & &\equiv1\pmod q\\ &+q_1& &-q_3&-q_4&+q_5& &\equiv0\pmod q\\ & &+q_2& &-q_4&-q_5&+q_6&\equiv0\pmod q\\ +q_0& & &+q_3& &-q_5&-q_6&\equiv0\pmod q\\ -q_0&+q_1& & &+q_4& &-q_6&\equiv0\pmod q\\ -q_0&-q_1&+q_2& & &+q_5& &\equiv0\pmod q\\ &-q_1&-q_2&+q_3& & &+q_6&\equiv0\pmod q\end{matrix}$$ The matrix of coefficients is circulant, and its last line has the coefficients of $F$ in reverse order.

This one happens to have no solution except for $q=1$: if we sum all the lines we get $0\equiv1\pmod q$. Mere generally, except for $q=1$, there can't be a solution when $0=\sum f_i$ as in the example.

While we could in general solve the system (or find that it has no solution) by Gaussian elimination and careful application of arithmmetic in $\Bbb Z_q$, that has cost $\mathcal O(n^3\,\log q\,\log\log q)$ and uses $\mathcal O(n^2\,\log q)$ memory. And while there are better methods for a circulant matrix, I won't go further into that.

---

Better methods to solve this problem are derived from the Extended Euclidean Algorithm, which given $A$ and $B$ in a principal ring, finds $U$ and $V$ in that ring with $A\cdot U+B\cdot V=G$, where $G$ is the Greatest Common Divisor of $A$ and $B$. As a byproduct that gives the modular inverse $U$ of $A$ modulo $B\ne0$, or tells that it does not exist when $G\ne1$.

That algorithm finds the inverse in particular in these rings:

• The ring $\Bbb Z_q$ (the integers), where for non-negative $a$ and $b$ it can go:

  • If $b=0$, output "$a$ has no inverse modulo $b$" and stop.
  • $c\gets a$, $d\gets b$, $u\gets0$ and $v\gets1$.
  • Repeat
    1. If $c=0$, output "$a$ has no inverse modulo $b$" and stop.
    2. If $c=1$, output "the inverse of $a$ modulo $b$ is $v$" and stop.
    3. Perform Euclidean division of $d$ by $c$ yielding quotient $z$ and remainder $r$ with $0\le r<c$.
    4. $d\gets r$ and $u\gets u+z\cdot v$.
    5. If $d=0$, output "$a$ has no inverse modulo $b$" and stop.
    6. If $d=1$, output "the inverse of $a$ modulo $b$ is $b-v$" and stop.
    7. Perform Euclidean division of $c$ by $d$ yielding quotient $z$ and remainder $r$ with $0\le r<d$.
    8. $c\gets r$ and $v\gets v+z\cdot u$
       
       

• The ring of polynomials with coefficients in the field $\Bbb Q$ (the rationals), where it can go:

  • If $B=0$, output "$A$ has no inverse modulo $B$" and stop.
  • $C\gets A$, $D\gets B$, $U\gets0$ and $V\gets1$.
  • Repeat
    1. If $C=0$, output "$A$ has no inverse modulo $B$" and stop.
    2. If $C$ has degree $0$ (that is, has only term $c_0$), output "the inverse of $A$ modulo $B$ is $(1/c_0)\,V$" and stop.
    3. Perform polynomial division of $D$ by $C$ yielding quotient $Z$ and remainder $R$ of degree less than the degree of $C$.
    4. $D\gets R$ and $U\gets U+Z\cdot V$.
    5. If $D=0$, output "$A$ has no inverse modulo $B$" and stop.
    6. If $D$ has degree $0$ (that is, has only term $d_0$), output "the inverse of $A$ modulo $B$ is $(-1/d_0)\,V$" and stop.
    7. Perform polynomial division of $C$ by $D$ yielding quotient $Z$ and remainder $R$ of degree less than the degree of $D$.
    8. $C\gets R$ and $V\gets V+Z\cdot U$.
       
       

• The ring of polynomials with coefficients in a finite field $\Bbb Z_p$ for prime $p$: same as above, except that when a coefficient $\displaystyle\frac st$ is obtained, we replace it with the integer $0$ when $s=0$, or otherwise with the integer $(t/\gcd(s,t))^{-1}\,(s/\gcd(s,t))\bmod q$.

The later is exactly what we need for $F_p$: we feed $A=F$ and $B=x^n-1$ to the algorithm, and it computes $F_p=A^{-1}\bmod B$ (or tells that is does not exists).

However, for a composite $q$, it can appear $\displaystyle\frac st$ that can no be brought back in $\Bbb Z_q$ because $\gcd(t,q)\ne1$.

I'm not sure about:

• If we can conclude that when we hit the problem, we can stop and conclude that $F$ is not invertible.
• If we can compute the inverse in the ring of polynomials with coefficients in the field $\Bbb Q$, and reduce in the end. I think we could find that $F$ is not invertible, but it really is invertible modulo $q$.

When $q$ is the product of distinct primes, we can get around that by finding the inverse modulus each prime dividing $q$, and using the Chinese Remainder Theorem to work back the coefficients of the inverse modulo $q$. We do not need to know the factorization of $q$ in advance: when we hit the problem, the GCD gives us a (perhaps partial) factorization of $q$. However I'm not sure of what to do when $q$ is divisible by a square of a prime.

Under work: further straighten that, example.

---

For a full-blown, faster method, see Joseph H. Silverman, Almost Inverses and Fast NTRU Key Creation, NTRU Technical Report #014, 1999.