NTRU public key cryptosystem explained

Author: Mateusz Piotr Siwiec

Introduction

Most of modern cryptographic algorithms and protocols rely on computational hardness of certain mathematical problems such as factorization of products of two large prime numbers (RSA) or discrete logarithm over certain groups (Diffie-Hellman key exchange, ElGamal encryption system). These problems are believed to have no efficient (polynomial time) solutions, so any cryptographic protocol based on them should be at least as hard to break. Since we can assume that any potential adversary has bounded computational power we can expect those protocols to be secure. This is, however, not necessarily always the case. If the adversary has computing power of a quantum computer (which in a couple of years might not seem to be so abstract), such algorithmic problems (or at least some of them) turn out to be easily solvable. For example the RSA modulus $N = pq$ can be factored using Shor's algorithm in polynomial time. Therefore RSA and many other popular protocols such as the Diffie-Hellman key exchange, ElGamal encryption scheme, DES or ECC (Elliptic-curve cryptography) would be broken. Those will have to be replaced with something that will be secure assuming greater computing power of a potential adversary.

Luckily, there are several algorithmic problems that are believed to be hard to solve on both classical and quantum computers. There are numerous different groups of protocols such as hash-based or code-based cryptography, multivariate-quadratic-equations cryptography or lattice-based cryptography. NTRU (NTRUEncrypt and NTRUSign) is a public key cryptographic system based on hardness of a certain mathematical problem involving special points in a lattice.

NTRUEncrypt

Lattices

An $n$-dimensional lattice can be visualised as a regular "grid" of points in a $n$-dimensional space. It is a set of vectors (points)

where $v_1, v_2, \dots, v_n \in \mathbb{Z}^n$ are linearly independent vectors of integer coordinates. For example, in a $2$-dimensional space a simple lattice is a set of all points of integer coordinates (with $v_1 = [0,1]$ and $v_2 = [1,0]$). Equivalently, a lattice is a set of points with integer coordinates in certain basis.

We can also use a more coherent way of describing a lattice by simply putting all the vectors $v_1, v_2, \dots, v_n$ as columns of a matrix $B \in \mathbb{Z}^{n \times n}$ and writing that

We can now define a $q$-ary lattice which is going to be a lattice whose points' coordinates are all taken mod $q$.

Let's take any matrix $A \in \mathbb{Z}_q^{n\times m}$ (a matrix of integers with $n$ rows and $m$ columns). Now we can define an $m$-dimensional $q$-ary lattice

This definition is enough to formulate two most important computationally difficult problems which are the core of lattice-based cryptography protocols:

• SVP – Shortest Vector Problem: Given the basis vectors $v_1, v_2, \dots, v_n$ of an $n$-dimensional lattice $L$, find the shortest non-zero vector in $L$.
• CVP – Closest Vector Problem: Given the basis vectors $v_1, v_2, \dots, v_n$ of an $n$-dimensional lattice $L$ and the vector $v$, find a vector in $L$, that is closest to $v$.
• SIVP – Shortest Independent Vector Problem: Given the basis vectors $v_1, v_2, \dots, v_n$ of an $n$-dimensional lattice $L$, find a new base $v'_1, v'_2, \dots, v'_n$ of the lattice $L$, which minimizes the length of the longest basis vector.

where by the length of a vector we most often mean the Euclidean norm, defined simply by

$$\newcommand{\norm}[1]{\left\lVert#1\right\rVert}
\norm{x}_n = \norm{[x_1, x_2, \dots, x_n]}_n = \sqrt{x_1^2 + x_2^2 + \dots + x_n^2}.
$$

The basic idea behind lattice-based cryptography is that we can represent any lattice using many different bases, some of which are ``easy to work with'', whereas others require complex computations to achieve even a polynomial approximation of the solution to the SVP/CVP. The most popular way of finding an approximate solution to the SVP is the lattice reduction method: LLL (Lensta-Lenstra-Lovasz), which gives quite good results, but the solution (a short vector) found using LLL in polynomial time is only guaranteed to be shorter than $\left(\frac{2}{\sqrt{3}}\right)^Ns$, where $s$ is the length of the shortest vector in the lattice, which is often not enough.

In general, the CVP problem is known to be NP-complete and the SVP is thought to be NP-hard (it is still yet to be proven), and there are no efficient ways of finding even a good approximation of their solutions.

GGH

Two most famous examples of lattice-based public-key encryption protocols are GGH (Goldreich-Goldwaser-Halevi) and NTRUEncrypt. In 2008 some important GGH vulnerabilities were discovered by P. Nguyen, that showed information leakage from the ciphertext and the possibility of reducing the CVP problem (which was the basis of the security of the protocol) to its special case – which was a core design flaw and the protocol is no longer considered to be secure. The algorithm behind GGH, however, shows really well how the ``hardness'' of the CVP can be used to design a public-key cryptosystem.

Let's take two lattice bases ($N$ linearly independent vectors in $\mathbb{Z}^N$): $B$ and $H$. We can generate $B$ and $H$ in such a way that $L(B) = L(H)$ -- the two bases both generate the lattice $L = L(B) = L(H)$ and $B$ is easy to work with (is \textit{almost} orthogonal, and its vectors are as short as possible), whereas $H$ is not – it is difficult to solve the SVP and CVP in $L$ given only this basis. We set $B$ to be the private key and $H$ to be the public key. The encryption is simply taking any vector $v \in L$ and adding to it another vector  $m$ (the message). The ciphertext is then $c = v + m$. The decryption is simply finding a point $v'$ in $L$ which is closest to $c$ (we expect it to be the same $v$ as chosen during encryption) and subtracting it from $c$. It can be done only when given a basis $B$, with which it is easy to solve the CVP. If $v = v'$ we are able to decrypt the ciphertext and get the vector $m' = c - v'$. In order to have $m = m'$ we must choose the vector $m$ to be relatively short so that the closest vector $v' = v$.  This description of the protocol is very simplified but shows the general idea behind it.

NTRUEncrypt

Just like in any other public-key cryptosystem, in order to allow a secure communication we require both private and public key, and two functions:
$$
\texttt{Encrypt}(\texttt{message},\texttt{public_key})
$$
and
$$
\texttt{Decrypt}(\texttt{ciphertext},\texttt{private_key}).
$$
We further assume that there are some global values known to everybody:

• $N$ – an integer that determines the ``dimension'',
• $p$, $q$ – two co-prime integer moduli ($gcd(p,q) = 1$),
• $d_f$, $d_g$, $d_r$, $d_m$ – integer bounds on private key, public key, and the message space.

The encryption and decryption in NTRU is described in terms of polynomials (in $\mathbb{Z}\lbrack X\rbrack /(X^N-1)$) of integer coefficients of degree $\leq n-1$, but it is just a more coherent way of describing the protocol instead of using vectors in lattices. The main idea remains unchanged.

We need three operations on polynomials: convolutional product, finding an inverse of a polynomial and reduction of a polynomial modulo an integer.
Convolutional product of two polynomials $f$ and $g$ is defined simply by

$$\begin{equation}
f\star g = \sum_{i+j=k \text{ mod } N} f_i g_j,
\end{equation}$$

where

$$
f = \sum_{i=0}^{N-1} f_ix^i\text{, and }g = \sum_{i=0}^{N-1} g_ix^i.
$$
It means that after a ``normal'' multiplication of two polynomials we must also reduce all the powers of $X$ modulo $N$.

The inverse $f^{-1}$ of a polynomial $f$ is a polynomial $f^{-1}$ that
$$
f \star f^{-1} = f^{-1}\star f = 1
$$

Reducing a polynomial modulo $q$ simply means taking all is coefficients mod $q$.

We will also use the notation $\#_af$ which means the number of coefficients in $f$ equal to $a$. For example if $N = 5$
$$
f(x) = 2x^4 + 2x^3 + x + 3 \\
\#_0f = 1 \\
\#_1f = 1 \\
\#_2f = 2 \\
\#_3f = 1
$$

Private key

The private key consists of two polynomials $f$ and $g$, such that:

and:

We also require that $f$ in invertible modulo $q$ which means there exists a $f_p^{-1}$ and $f_q^{-1}$, such that
$$
f \star f_p^{-1} = 1 \text{ mod } p,
$$
$$
f \star f_q^{-1} = 1 \text{ mod } q.
$$
The pair $(f,g)$ is the private key. For efficiency reasons $f_q^{-1}$ is often calculated during key generation and later stored as a part of the private key.

Public key

The public key is simply
$$
h = f_q^{-1}\star g \text{ mod } q.
$$

Encryption

Encryption in NTRU consists of two steps. First, the message has to be encoded as a trinary message $m$ which must also satisfy:

and a random polynomial $r$ must be generated, such that:

Then the ciphertext $c$ is defined by
$$
c = m + pr\star h \text{ mod } q,
$$ where the coefficients of $c$ are reduced modulo $q$ in such a way that they are in $(-\frac{q}{2}, \frac{q}{2}]$, so that $c$ is also centered around $0$.

Decryption

The decryption is just $\star$-multiplying $c$ by $f$:

From which we can calculate $f\star m$ by reducing mod $p$
$$
f\star m = (f \star m + pr \star g \text{ mod } q) \text { mod } p,
$$ which – after multiplying by $f_p^{-1}$ – gives the plaintext $m$.

The above algorithm is called NTRUEncrypt (NTRU Encryption Algorithm) which with the NTRUSign (NTRU Signature Algorithm) form the NTRU public key cryptosystem, and was first described in NTRU: A newhigh speed public key cryptosystem (1996). There are multiple resources available online regarding the exact values of the parameters. Typically $p=3$, $q=2^{11}=2048$ and the dimension $N$ is set to be a prime number, for example $443$, $587$ or $743$ depending on the required level of security. There are multiple publications discussing the choice of NTRU parameters and the security estimates available.

Final remarks

There are multiple other properties of the NTRUEncrypt apart from being secure against a quantum computer attacks, such as being more efficient and faster then RSA. A lot of useful resources on the topic of post-quantum cryptography and the NTRU cryptosystem (and a lot more) are available in the resources listed below.

This article is a simplification and is by no means a reference for any more serious work. The purpose of this text is to explain the basic concepts and ideas behind the NTRUEncrypt algorithm. For a more detailed description please refer to the original papers and official standards and specifications. More detailed resources for further reading can be found in the "Useful links" section below.

Bibliography

[1] Daniele Micciancio, Oded Regev. 2009. Lattice-based Cryptography.
In: Daniel J. Bernstein, Johannes Buchmann, Erik Dahmen (eds) Post-
Quantum Cryptography. Springer, Berlin, Heidelberg.
[2] Daniel J. Bernstein. 2009. Introduction to post-quantum cryptography.
In: Daniel J. Bernstein, Johannes Buchmann, Erik Dahmen (eds) Post-
Quantum Cryptography. Springer, Berlin, Heidelberg.
[3] Jill Pipher. 2002. Lectures on the NTRU encryption algorithm and digital
signature scheme.
[4] Jeffrey Hoffstein, Daniel Lieman, Jill Pipher, Joseph H. Silverman. 1999.
NTRU: A Public Key Cryptosystem.
[5] Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman. 1996. NTRU: A new
high speed public key cryptosystem

Useful links

• https://pqcrypto.org/ – a website dedicated to post-quantum cryptography
• https://www.onboardsecurity.com/products/ntru-crypto
• https://eprint.iacr.org/ – a great source of most recent works in cryptography
• https://web.securityinnovation.com/hubfs/files/ntru-orig.pdf – NTRU: A new high speed public key cryptosystem

Enigma image protected by CC BY-SA 2.0 license. Author: Michele M. F.