Skip to main content

Section 8 The NTRU cryptosystem

The NTRU cryptosystem was developed in 1996 by Hoffstein, Pipher and Silverman. NTRU is a public key cryptosystem not based on factorization or discrete logarithm problems. NTRU is based on the shortest vector problem in a lattice. The NTRU public key cryptosystem is one of the fastest known public key cryptosystem. NTRU works in the ring of truncated polynomials

\begin{equation*} R_q=\frac{\mathbb{Z}_q[X]}{X^N-1}, \end{equation*}

where \(N\) is a fixed positive integer and \(\mathbb{Z}_q\) denotes the ring of integers modulo \(q.\) In this ring a polynomial \(f\) can be written as

\begin{equation*} f=(f_0,f_1,\ldots,f_{N-1})=\sum_{k=0}^{N-1}f_kX^k. \end{equation*}

The addition of two polynomials \(f=(f_0,f_1,\ldots,f_{N-1})\) and \(g=(g_0,g_1,\ldots,g_{N-1})\) is defined as pairwise addition of the coefficients of the same degree, that is

\begin{equation*} f+g=(f_0+g_0,f_1+g_1,\ldots,f_{N-1}+g_{N-1}). \end{equation*}

The multiplication of two polynomials \(f\) and \(g\) is given by a convolution multiplication as follows

\begin{equation*} f\star g=h= (h_0,h_1,\ldots,h_{N-1}),\mbox{ where }h_k=\sum_{i+j\equiv k\bmod{N}}f_ig_j. \end{equation*}

As an example let us compute

\begin{equation*} (x^4+2x^3+3)\star (x^4+3x^2+x+2)=x^8 + 2x^7 + 3x^6 + 7x^5 + 7x^4 + 4x^3 + 9x^2 + 3x + 6. \end{equation*}

In the polynomial ring \(\frac{\mathbb{Z}_3[X]}{X^5-1}\) it can be written as

\begin{equation*} x^3+2x^2+3x+7+7x^4+4x^3+9x^2+3x+6=x^4+2x^3+2x^2+1. \end{equation*}

For a given positive integer \(d\) define the set

\begin{equation*} B(d)=\left\{\sum_{k=0}^{N-1}f_kX^k : f_i=0\mbox{ or }1, \sum_{k=0}^{N-1}f_k=d\right\}. \end{equation*}

In NTRU the parameters are chosen as follows

  • \(N\) is a sufficiently large prime,

  • \(p\) and \(q\) are relatively prime numbers such that \(q\) is much larger than \(p.\)

  • \(d_f,d_g\) and \(d_r\) are integers such that the polynomials from which the private keys are selected are from the set \(B(d_f)\) and \(B(d_g).\) The set \(B(d_r)\) contains the polynomials from which the blinding value used during encryption is selected.

  • \(\frac{\mathbb{Z}_p[X]}{X^N-1}\) is the plaintext space.

Consider now the key generation.

  • Randomly choose a polynomial \(f\in B(d_f)\) such that \(f\)has an inverse modulo \(p\) and \(q\) as well,

  • set \(f_p\equiv f^{-1}\pmod{p}\) and \(f_q\equiv f^{-1}\pmod{q}.\)

  • Randomly choose a polynomial \(g\in B(d_g).\)

  • Compute \(h\equiv g\star f_q\pmod{q}.\)

  • public key: \((N, h),\) private key \((f, f_p ).\)

Let us describe the encryption.

  • The message is represented as a polynomial \(m\) from the plaintext space.

  • Randomly choose a polynomial \(r\in B(d_r).\)

  • Encrypt \(m\) using the rule \(e \equiv p \star r \star h + m \pmod{q}.\)

The steps used in the decryption can be given as follows.

  • Compute \(a \equiv f \star e \pmod{q}.\)

  • Transform \(a\) to a polynomial with coefficients in the interval \([-q/2,q/2[.\)

  • Compute \(m \equiv f_p \star a \pmod{p}.\)

Let us check the computation to see why the above procedure works. We have

\begin{equation*} \begin{aligned} a &\equiv & f \star e \pmod{q}\\ &\equiv & f \star (p \star r \star h + m) \pmod{q}\\ &\equiv & p \star r \star g \star f \star f_q + f \star m\pmod{q}\\ &\equiv & p \star r \star g + f \star m\pmod{q}.\\\end{aligned} \end{equation*}

We obtain that

\begin{equation*} f_p \star a \pmod{p}\equiv (p\star r \star g + f \star m) \star f_p \pmod{p}\equiv m \pmod{p}. \end{equation*}

To illustrate the NTRU encryption/decryption let us see an example with

\begin{equation*} \begin{aligned} && N=7, p=3, q=41,\\ && f=X^6-X^4+X^3+X^2-1,\\ && g=X^6+X^4-X^2-X,\\ && m=-X^5+X^3+X^2-X+1,\\ && r=X^6-X^5+X-1.\end{aligned} \end{equation*}

Here we get

\begin{equation*} \begin{aligned} && f_p=X^6 + 2X^5 + X^3 + X^2 + X + 1,\\ && f_q=8X^6 + 26X^5 + 31X^4 + 21X^3 + 40X^2 + 2X + 37,\\ && h=19X^6 + 38X^5 + 6X^4 + 32X^3 + 24X^2 + 37X + 8,\\ && e=31X^6 + 19X^5 + 4X^4 + 2X^3 + 40X^2 + 3X + 25. \end{aligned} \end{equation*}

In SageMath it can be implemented as follows.

Subsection 8.1 Lattice based attack on NTRU

The public key satisfies

\begin{equation*} h\equiv g\star f_q\pmod{q} \end{equation*}

hence we have that \(f \star h \equiv g\pmod{q}.\) Consider the lattice defined by

\begin{equation*} \Lambda=\left\{ (F_1,F_2)\in\ R_q\times R_q : F_1 \star h \equiv F_2\pmod{q} \right\} . \end{equation*}

Obviously \((f,g)\in \Lambda.\) The relation \(f \star h \equiv g\pmod{q}\) can be written as

\begin{equation*} f \star h - u \star q = g \mbox{ for some } u\in R_q. \end{equation*}

The above equation is the same as

\begin{equation*} \begin{pmatrix} f\\ g \end{pmatrix}= \begin{pmatrix} 1 & 0\\ h & q \end{pmatrix} \begin{pmatrix} f\\ -u \end{pmatrix} \end{equation*}

or in a more useful form

\begin{equation*} \begin{pmatrix} f_0\\ f_1\\ \vdots\\ f_{N-1}\\ g_0\\ g_1\\ \vdots\\ g_{N-1}\\ \end{pmatrix}= \begin{pmatrix} 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\\ 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{pmatrix} \begin{pmatrix} f_0\\ f_1\\ \vdots\\ f_{N-1}\\ -u_0\\ -u_1\\ \vdots\\ -u_{N-1}\\ \end{pmatrix} \end{equation*}

Let us remark that the coefficients of the polynomials \(f\) and \(g\) are small, therefore \((f,g)\) is a short vector in the lattice \(\Lambda.\) That is the LLL-algorithm can be applied. Let us apply the above ideas in case of the example we considered. The appropriate lattice can be obtained in SageMath as follows.

Subsection 8.2 CTRU: using polynomials over \(\mathbb{F}_2\)

Gaborit, Ohler and Solé introduced a variant of NTRU for which lattice based attacked can be avoided. Let \(N\) be a positive integer and \(R=A[X]/(X^N-1),\) where \(A\) denotes the ring of polynomials over \(\mathbb{F}_2.\) Two irreducible polynomials \(P\) and \(Q\) in \(A[X]\) are fixed. Let us denote the degrees of these polynomials by \(s\) and \(t,\) that is \(\deg P=s,\deg Q=t.\) These numbers should satisfy that \(2\leq s\leq t\) and \(\gcd(s,t)=1.\) This latter \(\gcd\) condition is needed to have \(\mathbb{F}_{2^s}\cap \mathbb{F}_{2^t}=\mathbb{F}_{2}.\) For a given polynomial

\begin{equation*} F=F_0(T)+F_1(T)X+\ldots+F_{N-1}X^{N-1}\in R \end{equation*}

the maximum degree in \(T\) of the coefficients of \(X\) is denoted by \(\deg_T(F).\) Define the set \(\mathcal{L}(d)\) in the following way

\begin{equation*} \mathcal{L}(d)=\{F\in R : \deg_T(F)<d\}. \end{equation*}

For a given \(X^i\) we have the coefficient polynomial

\begin{equation*} F_{i,0}+F_{i,1}T+\ldots+F_{i,d-1}T^{d-1}, \end{equation*}

where \(F_{i,j}\in\mathbb{F}_2.\) Hence the number of possible coefficient polynomials is \(2^d.\) There are \(N\) coefficients, therefore the size of the set \(\mathcal{L}(d)\) is \(2^{dN}.\) In CTRU we use three additional parameters \(d_f,d_g\) and \(d_{\phi},\) these are integers between 1 and \(t-1.\) Alice and Bob follow the steps given below.

  • Alice chooses a polynomial \(f\in\mathcal{L}(d_f+1)\) such that it has an inverse modulo \(P\) and also modulo \(Q.\) Denote by \(f_P\) the inverse of \(f\) modulo \(P\) and by \(f_Q\) the inverse modulo \(Q.\) She also picks a polynomial \(g\in\mathcal{L}(d_g+1).\) The public key is

    \begin{equation*} h=g*f_Q\pmod{Q}. \end{equation*}

  • Bob needs two polynomials to send a message, the first one is \(m,\) the polynomial representing the message and the second one is a random polynomial from \(\mathcal{L}(d_{\phi}+1)\) denoted by \(\phi.\) He encrypts the message using the formula

    \begin{equation*} e=P*\phi*h+m\pmod{Q}. \end{equation*}

  • Alice receives \(e\) and she computes

    \begin{equation*} a=e*f=P*\phi*h*f+m*f=P*\phi*g+m*f\pmod{Q} \end{equation*}

    and

    \begin{equation*} a*f_P=P*\phi*g*f_P+m*f*f_P=m\pmod{P}. \end{equation*}

Subsection 8.3 ITRU: a variant of NTRU

In 2017 Gaithuru, Salleh and Mohamad introduced a variant of NTRU called ITRU. Instead of working in a truncated polynomial ring ITRU is based on the ring of integers. The parameters and the main steps of ITRU are as follows.

  • The value of \(p\) is suggested to be 1000.

  • Random integers \(f,g\) and \(r\) are chosen such that \(f\) is invertible modulo \(p.\)

  • A prime \(q\) is fixed satisfying \(q>p\cdot r\cdot g+f\cdot m,\) where \(m\) is the representation of the message in decimal form. The suggested conversion is based on ASCII conversion tables, that is the one with \(a\rightarrow 97.\)

  • One computes \(F_p=f^{-1}\pmod{p}\) and \(F_q=f^{-1}\pmod{q}.\) These computations can be done by using the extended Euclidean algorithm.

  • The public key is \(h\equiv p\cdot F_q\cdot g\pmod{q}\) and \(q.\)

  • The encryption is similar to the one applied in NTRU, one generated a random integer \(r\) and computes

    \begin{equation*} e\equiv r\cdot h+m\pmod{q}. \end{equation*}

  • To get the plaintext from the ciphertext one determines \(a\equiv f\cdot e\pmod{q}.\) Recovering the message is done by computing

    \begin{equation*} F_p\cdot a\pmod{p}. \end{equation*}

We need to show that we obtain the original message at the end. We have

\begin{equation*} a\equiv f\cdot e\equiv f(r\cdot h+m)\equiv f(r\cdot p\cdot F_q\cdot g +m)\equiv r\cdot p\cdot g+f\cdot m\pmod{q}. \end{equation*}

Here we used the fact that \(f\cdot F_q\equiv 1\pmod{q}.\) It remains to compute \(F_p\cdot a\pmod{p}.\) We obtain that

\begin{equation*} F_p\cdot a\equiv F_p(r\cdot p\cdot g+f\cdot m)\equiv F_p\cdot f\cdot m\equiv m\pmod{p}. \end{equation*}

We note that to fix \(q\) one needs a bound for the largest possible value of the representation, so here if one only uses the letters from ’A’ to ’Z’ and ’a’ to ’z’, then the maximum is 122. In the SageMath implementation we will use 255.

Let us encrypt a paragraph from the article describing ITRU (without spaces):

'ThegoalofthisstudyistopresentavariantofNTRUwhichisbasedontheringof
integersasopposedtousingthepolynomialringwithintegercoefficients.
WeshowthatNTRUbasedontheringofintegers(ITRU),hasasimpleparameter
selectionalgorithm,invertibilityandsuccessfulmessagedecryption.
Wedescribeaparameterselectionalgorithmandalsoprovideanimplementation
ofITRUusinganexample.ITRUisshowntohavesuccessfulmessagedecryption,
whichprovidesmoreassuranceofsecurityincomparisontoNTRU.'

If the large modulus is 1104427 and the public key is given by 37619, then the ciphertext starts as

\begin{equation*} 301036,301056,301053,301055,301063,301049,301060,301063,301054\ldots. \end{equation*}

There are 32 different numbers appearing in the ciphertext these are between 300992 and 301073. A simple frequency analysis provides the following data

[(301056, 0.0380313199105145), (301057, 0.0850111856823266),
(301060, 0.0313199105145414), (301061, 0.0290827740492170),
(301062, 0.0648769574944072), (301063, 0.0738255033557047),
(301064, 0.0313199105145414), (301066, 0.0536912751677852),
(301067, 0.0850111856823266), (301068, 0.0693512304250559),
(301069, 0.0201342281879195), (301070, 0.0111856823266219),
(301071, 0.0111856823266219), (301072, 0.00223713646532438),
(301073, 0.0134228187919463), (300992, 0.00223713646532438),
(300993, 0.00223713646532438), (300996, 0.00671140939597315),
(300998, 0.00894854586129754), (301025, 0.00671140939597315),
(301030, 0.00671140939597315), (301034, 0.0134228187919463),
(301036, 0.0156599552572707), (301037, 0.0134228187919463),
(301039, 0.00447427293064877), (301049, 0.0693512304250559),
(301050, 0.00894854586129754), (301051, 0.0357941834451902),
(301052, 0.0246085011185682), (301053, 0.109619686800895),
(301054, 0.0223713646532438), (301055, 0.0290827740492170)]

That is the number 301053 appears the most in the ciphertext. Our guess is that 301053 represents either ’e’, ’a’ or ’t’. If it is ’e’, then we apply the formula \(c_i-300952\) and we get a sequence of numbers starting with

\begin{equation*} 84,104,101,103,111,97,108, 111. \end{equation*}

If we consider it as a sequence of ASCII codes and determine the corresponding plaintext, then we get the encoded message.

SageMath summary.
LLL()

Returns an LLL reduced system of vectors.

chr()

Returns an ASCII character given by a code.

coefficients()

Returns coefficients of a polynomial.

ord()

Returns the ASCII code of a given character.

Exercises 8.4 Exercises

1.

Let \(N=11, p=3\) and \(q=32.\) Determine polynomials \(f_p\) and \(f_q\) such that \(f\star f_p\equiv 1\pmod{p}\) and \(f\star f_q\equiv 1\pmod{q},\) where \(f=-1+X+X^2+X^4-X^5+X^8-X^{10}\) is an element of \(\mathbb{F}[X]/(X^{11}-1).\)

2.

NTRU encryption. Let \(N=11, p=3\) and \(q=23.\) We choose \(f=x^{10}-x^9+x^7+x^4-1\) and \(g=x^{10}+x^6-x^3-x^2+x+1.\) Alice would like to send the message \(m=x^{10}+2x^9+x^5+x+1\) to Bob. Alice chooses the random polynomial \(r=x^9-x^7+x^6+x^3-x-1.\) Compute the polynomial that Alice sends to Bob.

3.

NTRU decryption. Decrypt the message sent by Alice to Bob as it is described in the previous exercise.

4.

Try to determine \(f\) and \(g\) by means of the LLL-algorithm in case of the NTRU cryptosystem described in the previous exercises, that is \(N=11, q=23\) and

\begin{equation*} h=12 x^{10} + 21 x^{8} + 4 x^{7} + 12 x^{5} + 17 x^{4} + 22 x^{3} + 6 x^{2} + 16 x + 7. \end{equation*}
5.

Encrypt and decrypt the message "Fully secure systems do not exist today and they will not exist in the future" by means of the ITRU cryptosystem with \(f=557,g=806,r=17\) and \(q=13844041.\)