A Gentle Introduction to Mathematical Cryptography, Part 3: NTRU

Note that this is the third post in a three-part series on cryptography. The first post giving an introduction is here, and the second post, covering notions of security in cryptography, is here.

What is NTRU?

The NTRU cryptosystem was first presented in 1996 at a crypto rump session by Hoffstein, Pipher, and Silverman, and first described in a publication [4] in 1998. NTRU is one of the fastest public key encryption schemes and it also appears to be secure against attacks by quantum computers [8]. NTRU has undergone many changes in response to security weaknesses discovered by researchers throughout the years, but the essence of its original framework has been retained. We will present the NTRU cryptosystem as described by Hoffstein, Pipher, and Silverman in [5]. Before we can fully describe the NTRU cryptosystem we will need a bit of background.

Definition (ring of convolutional polynomials)Fix a positive integer $N$. The ring of convolution polynomials (of rank $N$) is the quotient ring $$ R=\frac{\mathbb{Z}[x]}{x^N-1} $$ Similarly, the ring of convolution polynomials (modulo q) is the quotient ring $$ R_q=\frac{(\mathbb{Z}/q\mathbb{Z})[x]}{x^N-1}$$

Note that every element in $R$ or $R_q$ has a unique representative of the form $$a_0 + a_1x + a_2x^2 + \cdots + a_{N-1}x^{N-1} $$ with coefficients in $\mathbb{Z}$ or $\mathbb{Z}/q\mathbb{Z}$, respectively. Operations in convolution polynomial rings are not difficult. Addition, $+$, is performed in the usual way as with polynomials (reducing coefficients mod $q$ in $R_q$) while multiplication, which we denote $\star$, is done in the usual manner as well, except we reduce mod $x^N-1$. This merely means that we require $x^N$ to be equal to $1$, so when $x^N$ appears we replace it with $1$.

Notation: A polynomial $\textbf{a}(x) \in R$ will be written as $$ \textbf{a} = \sum_{i=0}^{N-1} a_ix^i = [a_0, a_1, \dots, a_{N-1}] $$

Theorem (multiplication in $R$): The product of two polynomials $\textbf{a}(x),\textbf{b}(x) \in R$ is given by $$ \textbf{a}(x) \star \textbf{b}(x) = \textbf{c}(x)\ with\ c_k = \sum_{i+j \equiv k\ (mod\ N)} a_ib_{k-i} $$

The proof of this theorem is omitted, but it is merely an exercise in applying the definition of multiplication in $R$. Note that multiplication in $R_q$ is identical, except that coefficients will be reduced modulo $q$

We are now ready to describe the NTRU cryptosystem. Fix an integer $N\ge1$ and two moduli $p$ and $q$, and let $R$, $R_p$, and $R_q$ be the convolution polynomial rings $$ R=\frac{\mathbb{Z}[x]}{x^N-1}, \quad R_p=\frac{(\mathbb{Z}/p\mathbb{Z})[x]}{x^N-1}, \quad R_q=\frac{(\mathbb{Z}/q\mathbb{Z})[x]}{x^N-1}, $$ as described above. Note that in our description when we refer to computations mod $p$ we are working in $R$ mod $p$, which is equivalent to $R_p$. The same is true for $R_q$.

We require $N$ to be prime, and while $p$ and $q$ need not be prime, we require $gcd(N,q)=gcd(p,q)=1$. We will now introduce a piece of notation to make our description easier.

Notation: For any positive integers $d_1$ and $d_2$, let $$\mathcal{T}(d_1,d_2) = \left\{ \textbf{a}(x) \in R: \begin{array}{lr} \textbf{a}(x)\ has\ d_1\ coefficients\ equal\ to\ 1,\\ \textbf{a}(x)\ has\ d_2\ coefficients\ equal\ to\ -1,\\ \textbf{a}(x)\ has\ all\ other\ coefficients\ equal\ to\ 0 \end{array} \right\}$$

Polynomials in the set $\mathcal{T}(d_1,d_2)$ are called ternary polynomials. They are similar to binary polynomials which have only 0's and 1's as coefficients. In describing NTRU we will make use of the Alice and Bob terminology introduced in the first post of this series. For the NTRU cryptosystem, we assign public parameters $(N,p,q,d)$ satisfying the requirements stated above. To create a private key, Alice randomly selects two polynomials $$ \textbf{f}(x) \in \mathcal{T}(d+1,d) \quad and \quad \textbf{g}(x) \in \mathcal{T}(d,d). $$

The polynomial $\textbf{f}(x)$ must be invertible mod $p$ and mod $q$. If either inverse fails to exist, Alice discards this $\textbf{f}(x)$ and selects a new one. Note that $\textbf{f}(x)$ cannot be drawn from $\mathcal{T}(d,d)$ because elements of this set never have inverses (for any $\textbf{a}(x) \in \mathcal{T}(d,d),\ \textbf{a}(1)=0$). Alice next computes the inverses $$ \textbf{F}_p(x)=\textbf{f}(x)^{-1}\ in\ R_p \quad and \quad \textbf{F}_q(x)=\textbf{f}(x)^{-1}\ in\ R_q. $$

Hence we have $$ \textbf{F}_p(x) \star \textbf{f}(x) \equiv 1 \ (mod\ p) \quad and \quad \textbf{F}_q(x) \star \textbf{f}(x) \equiv 1 \ (mod\ q). $$ Alice then computes $$ \textbf{h}(x) \equiv \textbf{F}_q(x) \star \textbf{g}(x) \quad (mod\ q). $$

Alice's public key is the polynomial $\textbf{h}(x)$ and her private key is the pair $(\textbf{f}(x),\textbf{F}_p(x))$. That is, if Bob wants to send Alice a message, he will encrypt the plaintext using $\textbf{h}(x)$ and Alice will use $(\textbf{f}(x),\textbf{F}_p(x))$ to decrypt the message. Now let's see how encryption works.

Bob's plaintext must be a polynomial $\textbf{m}(x) \in R$ with coefficients between $\frac{-1}{2}p$ and $\frac{1}{2}p$. Hence, $\textbf{m}$ is in fact the centered lift of a polynomial in $R_p$. Bob randomly chooses a polynomial $\textbf{r}(x) \in \mathcal{T}(d,d)$ and computes $$ \textbf{e}(x) \equiv p\textbf{h}(x) \star \textbf{r}(x) + \textbf{m}(x) \quad (mod\ q). $$

The polynomial $\textbf{e}(x)$ is Bob's ciphertext, and it is in the ring $R_q$. After computing $\textbf{e}(x)$ Bob can send this ciphertext to Alice who will decrypt it using her private key.

When Alice receives Bob's ciphertext, she begins decrypting the message by computing $$ \textbf{a}(x) \equiv \textbf{f}(x) \star \textbf{e}(x) \quad (mod\ q). $$ Next, Alice center lifts $\textbf{a}$ so that its coefficients lie in the interval from $\frac{-q}{2}$ to $\frac{q}{2},$ and computes $$ \textbf{b}(x) \equiv \textbf{F}_p(x) \star \textbf{a}(x) \quad (mod\ p). $$

If the parameters have been chosen properly, this polynomial $\textbf{b}(x)$ is in fact equal to Bob's plaintext $\textbf{m}(x)$. In the original NTRU description, $\textbf{b}(x)$ was only equal to $\textbf{m}(x)$ with a high degree of probability, but it was later realized that this chance of decryption failure could be eliminated with a proper selection of parameters. It is not immediately clear why $\textbf{b}(x)$ is equal to $\textbf{m}(x)$, so we will explain the decryption process in more detail.

The polynomial $\textbf{a}(x)$ that Alice computes satisfies $$\begin{eqnarray*} \textbf{a}(x) &\equiv & \textbf{f}(x) \star \textbf{e}(x) \quad (mod\ q) \\ &\equiv & \textbf{f}(x) \star (p\textbf{h}(x) \star \textbf{r}(x) + \textbf{m}(x)) \quad (mod\ q) \\ &\equiv & \textbf{f}(x) \star (p(\textbf{F}_q(x) \star \textbf{g}(x)) \star \textbf{r}(x) + \textbf{m}(x)) \quad (mod\ q) \\ &\equiv & p(\textbf{f}(x) \star \textbf{F}_q(x) \star \textbf{g}(x) \star \textbf{r}(x)) + \textbf{f}(x) \star \textbf{m}(x) \quad (mod\ q) \\ &\equiv & p\textbf{g}(x) \star \textbf{r}(x) + \textbf{f}(x) \star \textbf{m}(x) \quad (mod\ q) \end{eqnarray*}$$

Now consider the polynomial $ p\textbf{g}(x) \star \textbf{r}(x) + \textbf{f}(x) \star \textbf{m}(x) $ computed in $R$, rather than modulo $q$. We want the polynomial to remain the same when we reduce its coefficients modulo $q$, so we need to try to bound the largest coefficient. Recall that $\textbf{g}(x)$ and $\textbf{r}(x)$ are selected from $\mathcal{T}(d,d)$, so if all of their $1$'s match up and all of their $-1$'s match up, the largest possible coefficient of $\textbf{g}(x) \star \textbf{r}(x)$ is $2d$. Similarly, we have $\textbf{f}(x) \in \mathcal{T}(d+1,d)$ and the coefficients of $\textbf{m}(x)$ lie in the interval $\frac{-1}{2}p$ to $\frac{1}{2}p$, so the largest possible coefficient of $\textbf{f}(x) \star \textbf{m}(x)$ is $(d+1)\cdot(\frac{1}{2}p) + (d)\cdot(\frac{1}{2}p) = (2d+1)\cdot(\frac{1}{2}p)$.

Hence, if the largest coefficient of $\textbf{g}(x) \star \textbf{r}(x)$ coincides with the largest coefficient of $\textbf{f}(x) \star \textbf{m}(x)$ , the largest possible coefficient for $p\textbf{g}(x) \star \textbf{r}(x) + \textbf{f}(x) \star \textbf{m}(x)$ is $$p\cdot2d + (2d+1)\cdot(\frac{1}{2}p) = \left(3d + \frac{1}{2}\right)p.$$ So if we take $q > (6d+1)p$ then the largest coefficient will be strictly less than $\frac{1}{2}q$. Therefore, when Alice computes $\textbf{a}(x)$ modulo $q$ and center lifts it to $R$, she in fact recovers exactly the polynomial $p\textbf{g}(x) \star \textbf{r}(x) + \textbf{f}(x) \star \textbf{m}(x)$. That is, we actually have $$\textbf{a}(x) = p\textbf{g}(x) \star \textbf{r}(x) + \textbf{f}(x) \star \textbf{m}(x)$$ in $R$, rather than just a congruence modulo $q$.

Now we can finally explain the last step of decryption, in which Alice multiplies $\textbf{a}(x)$ by $\textbf{F}_p(x)$ and reduces the product modulo $p$

$$\begin{eqnarray*} \textbf{b}(x) &=& \textbf{F}_p(x) \star \textbf{a}(x) \\ &=& \textbf{F}_p(x) \star (p\textbf{g}(x) \star \textbf{r}(x) + \textbf{f}(x) \star \textbf{m}(x)) \\ &\equiv & \textbf{F}_p(x) \star \textbf{f}(x) \star \textbf{m}(x) \quad (mod\ p) \\ &\equiv & \textbf{m}(x) \quad (mod\ p). \end{eqnarray*}$$

Hence, we have shown that $\textbf{b}(x)$ and $\textbf{m}(x)$ are in fact the same modulo $p$.

Theorem (NTRU decryption): If the NTRU parameters $(N,p,q,d)$ are chosen to satisfy $$ q > (6d+1)p, $$ then the polynomial $\textbf{b}(x)$ is equal to Bob's plaintext $\textbf{m}(x)$.

The proof of the theorem was presented in our explanation of the decryption process. Note that our discussion of NTRU follows that presented in [5].

From this description of NTRU, it is not immediately clear why it is referred to as a "lattice based cryptosystem", and we will not provide much detail on this point as it is outside of the scope of this post. In lieu of an in depth discussion, we will provide a couple of basic definitions and recommend further reading for those who are interested. We refer to [5] for our discussion of lattices.

Definition (lattice): Let $\textbf{v}_1,\dots,\textbf{v}_n \in \mathbb{R}^m$ be a set of linearly independent vectors. The lattice $\mathcal{L}$ generated by $\textbf{v}_1,\dots,\textbf{v}_n$ is the set of linear combinations of $\textbf{v}_1,\dots,\textbf{v}_n$ with coefficients in $\mathbb{Z}$, $$\mathcal{L} = \{a_1\textbf{v}_1 + a_2\textbf{v}_2 + \cdots +a_n\textbf{v}_n : a_1, a_2, \dots, a_n \in \mathbb{Z}\}.$$

A helpful way of thinking about a lattice is as a vector space, but over $\mathbb{Z}$ instead of a field. As with vector spaces, a $\textit{basis}$ for a lattice $\mathcal{L}$ is any set of linearly independent vectors that generates $\mathcal{L}$ while the $\textit{dimension}$ of $\mathcal{L}$ is the number of vectors in a basis for $\mathcal{L}$. Note that one can equivalently define a lattice as a discrete additive subgroup of $\mathbb{R}^n$ [9].

Once we have a lattice, we can define difficult computational problems. Two of these fundamental lattice problems are:

Definition (Shortest Vector Problem (SVP)): Given an arbitrary basis of some lattice $\mathcal{L}$, find a shortest nonzero lattice vector, i.e., find a $\textbf{v} \in \mathcal{L}$ such that $\|\textbf{v}\| = \min\limits_{\textbf{v} \in \mathcal{L} \setminus \{0\}} \|\textbf{v}\|$

Definition (Closest Vector Problem (CVP)): Given a vector $\textbf{w} \in \mathbb{R}^m$ that is not in $\mathcal{L}$, find a vector $\textbf{v} \in \mathcal{L}$ that is closest to $\textbf{w}$, i.e., find a vector $\textbf{v} \in \mathcal{L}$ that minimizes $\|\textbf{w} - \textbf{v}\|$.

Note that in the above definitions $\| \cdot \|$ is the Euclidean norm. Both SVP and CVP are considered to be very hard problems computationally, and as we have seen with integer factorization and RSA, it is possible to leverage the hardness of these (or related) lattice problems to create a secure cryptosystem. Without going into any details, we mention that the NTRU problem is related to SVP for key recovery and to CVP for plaintext recovery, and to another problem known as $\textit{Ring Learning with Errors}$ [5],[9]. It is important to note, however, that "there is no known reduction from any worst-case lattice problem to any standard version of the NTRU problem, nor from the the NTRU problem to breaking the cryptosystem's semantic security" [9]. There is a rich theory and deep mathematical questions involved in lattice based cryptography, and, if the reader is interested in delving into this material, there are many readily available sources including [9], [5], [6], [1], and [12].

The Semantic Security of NTRU

The NTRU cryptosystem as originally presented, and also the slightly modified description we have presented, is in fact not semantically secure (i.e. CPA secure). The original presentation of NTRU in [4] did not make any mention of the modern notions of cryptographic security such as CPA and CCA security, so it is unclear as to whether or not the authors were aware that their construction was not CPA secure. It is surprisingly easy to demonstrate that NTRU is not CPA secure, and it is has been mentioned in several papers including [8] and in an updated description of NTRU released by NTRU Cryptosystems and including Daniel Lieman as an author.

The failure to provide semantic security comes from the construction of the encrypted messages. Recall that an encrypted message has the form $ \textbf{e}(x) \equiv p\textbf{h}(x) \star \textbf{r}(x) + \textbf{m}(x) \quad (mod\ q). $ Now, we will also recall that $\textbf{m}(x) \in R$, $\textbf{r}(x) \in \mathcal{T}(d,d)$, and $\textbf{h}(x) \equiv \textbf{F}_q(x) \star \textbf{g}(x) \quad (mod\ q).$ Finally, we also note that $\textbf{g}(x) \in \mathcal{T}(d,d).$ Now if we remember our earlier definition, we can see that all polynomials in $\mathcal{T}(d,d)$ have $d$ coefficients equal to $1$, $d$ coefficients equal to $-1$, and all other coefficients equal to $0$. Hence, any polynomial in $\mathcal{T}(d,d)$ evaluated at $x=1$ will be equal to zero. That is, $\textbf{r}(1) = 0$ and $\textbf{g}(1) = 0$ (and hence $\textbf{h}(1) \equiv 0 \quad (mod\ q)$). Therefore if we evaluate the encrypted message $\textbf{e}(x)$ at $x=1$ we will have

$$\begin{eqnarray*} \textbf{e}(1) &\equiv & p\textbf{h}(1) \star \textbf{r}(1) + \textbf{m}(1) \quad (mod\ q) \\ &\equiv & p0 \star 0 + \textbf{m}(1) \quad (mod\ q) \\ &\equiv & \textbf{m}(1) \quad (mod\ q) \end{eqnarray*}$$

Using this knowledge, we will now refer to our test of CPA security to show why NTRU is not semantically secure. Recall that the adversary, $\mathcal{A}$, is allowed to choose two messages $m_0, m_1 \in \mathcal{P}$ such that $m_0 \not= m_1$. In particular, the adversary is able to choose $\textbf{m}_0(x), \textbf{m}_1(x) \in \mathcal{R}$ such that $\textbf{m}_0(1) \not\equiv \textbf{m}_1(1) \quad (mod\ q)$. Next, a random bit $b \in \{0,1\}$ is chosen and the challenge ciphertext $c \leftarrow \texttt{Enc}_{pk}(m_b)$ is computed and given to $\mathcal{A}$. In the case of NTRU we will have $c= \textbf{e}(x) \equiv p\textbf{h}(x) \star \textbf{r}(x) + \textbf{m}_b(x) \quad (mod\ q)$ for some $p$, $\textbf{h}(x)$, and $\textbf{r}(x)$ from their respective spaces. At this point the adversary can compute any function it likes on $c$, and, in particular, it can evaluate $c=\textbf{e}(x)$ at $x=1$. Now when $\mathcal{A}$ evaluates $c$ at $x=1$ it will get $$\textbf{e}(1) \equiv \textbf{m}_b(1) \quad (mod\ q).$$ As the adversary has chosen two messages $\textbf{m}_0, \textbf{m}_1$ such that $\textbf{m}_0(1) \not\equiv \textbf{m}_1(1) \quad (mod\ q)$, it will now know precisely which message was encrypted to give the challenge ciphertext. Hence, $\mathcal{A}$ can win the CPA security experiment with probability equal to one - so NTRU is not CPA secure.

Padding Schemes and NTRU Today

After it became clear that NTRU was not semantically secure, its creators introduced several padding schemes with the aim of improving NTRU's security, and, in particular, achieving semantic security. In response to these proposed padding schemes, Phong Q. Nguyen and David Pointcheval published [8] in which they explore NTRU's padding schemes and propose several of their own. Nguyen and Pointcheval carefully explain the NTRU assumption, and demonstrate that, contrary to claims from NTRU's creators, the three padding schemes are not IND-CCA2 secure, and in fact the first is not even IND-CPA secure. The authors then propose two padding schemes of their own, which are provably secure in the random oracle model.

The two schemes which they present are based on OAEP (Optimal Asymmetric Encryption Padding) and REACT (Rapid Enhanced-security Asymmetric Cryptosystem Transform) respectively. OAEP and REACT are padding schemes that can be applied to any cryptosystem which satisfies certain properties, and are not unique to NTRU. For example, OAEP is generally used in combination with RSA [8]. We will not go into the technical details regarding these padding schemes, as an understanding of the schemes and their security requires further knowledge of cryptography, but we hope the interested reader will explore these schemes on their own.

NTRU continues to be seen as a strong candidate for a post quantum public-key encryption scheme, but there still needs to be more research into NTRU in order to build more confidence about the cryptosystem's security. In 2011, Damien Stehle and Ron Steinfeld developed a version of NTRU that is provably secure in the standard model, but in achieving this level of security the cryptosystem became too inefficient to be practically used [10]. Steinfeld further extended this work in [11], but the resulting modifications to the encryption scheme are still too inefficient. Whether it is through a padding scheme, or some other alteration, we can hope that a provably secure version of NTRU, that maintains its efficiency, will be discovered sometime in the near future.

References

Daniel J. Bernstein, Johannes Buchmann, and Erik Dahmen. Post Quantum Cryptography. 2009: Springer-Verlag, Berlin.
Dan Boneh and Ramarathnam Venkatesan. (1998). Breaking RSA may not be equivalent to factoring. Advances in Cryptology - EUROCRYPT '98. Lecture Notes in Computer Science, Volume 1403, 59-71. Springer, Berlin.
Shafi Goldwasser and Silvio Micali. (1982). Probabilistic Encryption & How to Play Mental Poker Keeping Secret all Partial Information. STOC '82 Proceedings of the fourteenth annual ACM symposium on Theory of computing (pp. 365-377). ACM, New York.
Jeffrey Hoffstein, Jill Pipher, and Joseph H. Silverman. (1998). NTRU: A ring based public key cryptosystem. Lecture Notes in Computer Science, Volume 1423, 267-288. Springer, Berlin.
Jeffrey Hoffstein, Jill Pipher, and Joseph H. Silverman. An Introduction to Mathematical Cryptography. 2008: Springer, N.Y.
Jonathan Katz and Yehuda Lindell. Introduction to Modern Cryptography. 2007: CRC Press, N.Y.
Vadim Lyubashevsky, Chris Peikert, and Oded Regev. (2010). On Ideal Lattices and Learning with Errors over Rings. In H. Gilbert (ed.), Advances in Cryptology - EUROCRYPT 2010 (pp. 1-23). Springer, Berlin.
Phong Q. Nguyen and David Pointcheval. (2002). Analysis and Improvements of NTRU Encyption Paddings. In M. Yung (ed.), Advances in Cryptology - Proceedings of CRYPTO 2002 (pp. 210-225). Springer-Verlag, Berlin.
Chis Peikert. A Decade of Lattice Cryptography 2016: Now Publishers.
Damien Stehle and Ron Steinfeld. (2011). Making NTRU as Secure as Worst-Case Problems over Ideal Lattices. In K.G. Patterson (ed.), Advances in Cryptology - EUROCRYPT 2011 (pp. 27-47). Springer, Berlin.
Ron Steinfeld et al. (2012). NTRUCCA: How to Strengthen NTRUEncrypt to Chosen-Ciphertext Security in the Standard Model. Lecture Notes in Computer Science, Volume 7293, 353-371. Springer, Berlin.
Douglas Stinson. Cryptography Theory and Practice. 2002: CRC Press, Boca Raton.