For my Cryptography class I did my final paper and on the NTRU Cryptography System, a crypto system created by professors at Brown. Here’s the paper remade for the web using this $\LaTeX$ to markdown/html converter.

NTRU is a lattice-based cryptosystem that is efficient and is currently secure against quantum attacks. In this paper, we give an overview of the NTRU cryptosystem, comparing it to other cryptosystems we’ve discussed in class, discussing its efficiency and quantum resistance, and giving a basic overview of the algebraic perspective of NTRU.

Comparison with Previous Methods #

Most of the cryptosystems we’ve discussed in class have involved problems in groups. For example, we’ve seen Elgamal PKC that is based on the discrete logarithm problem for $R^{\ast}_p$, but the construction works generally using the DLP in any group including elliptic curves, that also form a group under addition ¹.

As an extension of a monoid, groups are algebraic structures that have one operation; therefore, these group based cryptosystems are based on the hardness of one operation, such as multiplication modulo $m$ in RSA, or elliptic curve addition in ECC.

However, the NTRU cryptosystem lives in the realm of rings, which are algebraic structures that have two operations, addition and multiplication, which are connected via the distributive law ¹. Specifically, NTRU operates in the ring $R = (Z_n, +, \star)$, where $\star$ is cyclic convolution ². Interestingly, it has an alternate perspective in lattices and is based on the Shortest Vector Problem (SVP) or Closest Vector Problem (CVP) in a lattice ¹.

Background #

Motivation for NTRU #

Efficiency #

Compared to the cryptosystems we’ve discussed in class, NTRU has a clear efficiency advantage with faster encryption/decryption and parallelization ¹. Lattice based cryptosystems are generally between 1 and 2 orders of magnitude faster than RSA or ECC systems at equivalent security levels ³. The main operation used in NTRU is the convolution, which is simpler than the modular exponentiation used in RSA and repeated squaring/doubling used in ECC ⁴. Not only does this mean that NTRU is suitable for machines with limited computing power, but it also allows for parallelization, which means that we can split the operations between multiple processors to improve speed ⁴. Furthermore, NTRU also has a lower time complexity of $O(N^2)$ ($O(N \log N)$ with the Fast Fourier Transform) compared to RSA’s $O(N^3)$ ⁴. However, these speed differences have become less relevant as machines have gotten faster and NTRU’s resilience to quantum attacks has become more important ³.

Quantum Resistance #

Classical computers are constrained by the resources of time and space. Typically, these two resources are at odds with each other (e.g., using more memory can lead to faster computation through techniques like caching). However, quantum computers have an additional resource of precision which allows them another avenue of decreasing time-complexity ⁵. Quantum computers get this extra resource by using quantum states of objects (e.g., atoms, photons, or nuclear spins) which do not have the binary classification of 0 or 1, but can exist in a superposition of states. This superposition is the decrease of precision that allows quantum computers to simulate the behavior of multiple states at once. Of course, this when the superposition is measured, the quantum state collapses to a single state, but by using clever tricks we can select the information we want at the expense of losing erroneous information ⁵.

Using classical mechanics, the best factoring algorithm asymptotically is the general number field sieve (GNFS) ⁶. However, Peter Shor showed that a quantum computer could factor numbers in polynomial time, surpassing the GNFS ⁵.

The main idea behind Shor’s algorithm is to use quantum Fourier transform, a quantum version of the Fast Fourier Transform, in order to study of the order of elements in a group ¹. This is the trick that allows Shor’s algorithm to force the quantum superposition to collapse to a state that reveals the factors of a number at the cost of precision with knowing about all the trials.

Using this process, Shor is easily able to find a solution $r$ to this problem:

$$ x^r \equiv 1 \mod n $$

where $r$ is the order of $x$ modulo $n$.

This is a key step to factor numbers since if $x$ is chosen randomly and has an even order $r$, then $\gcd(x^{r/2} - 1, n)$ is likely to be a nontrivial odd factor of $n$ ¹.

Furthermore, Shor also develops a way to find discrete logarithms in $F^\ast_p$ on a quantum computer with two modular exponentiations and two quantum Fourier transforms ⁵.

So, Shor is also easily able to find a solution $x$ to this problem:

$$ g^x \equiv h \mod p $$

where $x$ is the discrete logarithm of $h$ to the base $g$

And as we’ve seen in class, most of the cryptosystems we’ve discussed are based on the hardness of factorization or the discrete logarithm problem. The prime factorization algorithm breaks down RSA, the discrete logarithm algorithm breaks down Elgamal and the elliptic curve discrete logarithm problem breaks down ECC. Although a sufficiently large quantum computer has not been built yet, they have the potential to break these cryptosystems. However, is it still unknown how to solve the shortest or closest vector problems, the common basis for lattice-based cryptosystems, in polynomial time on a quantum computer ¹. This means that lattice-based cryptosystems are currently secure even against the construction of a quantum computer. In particular, according to a survey of quantum resistant public key cryptography by the National Institute of Standards and Technology (NIST), “the NTRU family of cryptographic algorithms appears to be the most practical” ⁷.

Basic Definitions #

The majority of operations we will use are addition and multiplication modulo $x^N-1$ in $R$. Where elements of $R$ look like:

$$f(x)=f_0+f_1x+\cdots+f_{N-1}x^{N-1} \quad \text{where } f_i\in\mathbb{Z}.$$

Elements do not have degree greater than $N-1$ since we can deduce by a factor of $x^N-1$. Moreover, the other rings $R_p, R_q$ are similar to $R$ but with the additional constraint of $f_i$ from $\mathbb{Z}/p\mathbb{Z}$ or $\mathbb{Z}/q\mathbb{Z}$ respectively.

Addition in these rings is straightforward, we add the coefficients of the same degree term and reduce by modulo if needed.

$$ a_0 + \cdots + a_{N-1}x^{N-1} + b_0 + \cdots + b_{N-1}x^{N-1} = (a_0+b_0) + \cdots + (a_{N-1}+b_{N-1})x^{N-1} \ $$ $$ \text{In vector form: }(a_0, \ldots, a_{N-1}) + (b_0, \ldots, b_{N-1}) = (a_0+b_0, \ldots, a_{N-1}+b_{N-1}) $$

However, multiplication is a bit more complicated. Note how the multiplication of two polynomials is like a convolution of the coefficients.

After multiplying two polynomials, we need to reduce the polynomial by modulo $x^N-1$. This is because the coefficients of the polynomial can be greater than the modulus, and we need to reduce them to the appropriate range.

NTRU Cryptosystem #

Ring-based Encryption #

Public Parameter Creation #

First we pick the public parameters $(N, p, q, d)$ we’ll use for the encryption. Typically, $N$ is between $250$ and $2500$, $p$ is a prime number, and $q$ such that $\gcd(p, q) = \gcd(N, q) = 1, q > (6d + 1)p$. The parameter $d$ is typically around half of $N$ ^{3 1}.

Why This Works #

Consider $a = pg \star r + f \star m \mod q$. Before the mod by $q$, because we start with $f, g, r$ as ternary polynomials and bounds on $m$, we have the polynomial have coefficients with magnitude smaller than $q / 2$ guaranteed by the $q > (6d + 1)p$ condition. This means $a$ is the same in $R$ and not just modulo $q$ ^{8 1}. Therefore, we get our message back when we multiply by $F_p$ and reduce by $p$.

$$ F_p \star a \equiv F_p \star (pg \star r + f \star m) \pmod{p} $$

$$ \equiv F_p \star (pg \star r) + F_p \star (f \star m) \pmod{p} $$

$$ \equiv p F_p \star (g \star r) + F_p \star (f \star m) \pmod{p} $$

$$ \equiv F_p \star (f \star m) \pmod{p} $$

$$ \equiv (F_p \star f) \star m \pmod{p} $$

$$ \equiv m \pmod{p} $$

Conclusion #

The NTRU cryptosystem is an alternate approach to most of the methods in class, operating within the realm of rings. This change in environment allows for faster encryption/decryption and parallelization. Furthermore, NTRU is currently resistant to quantum attacks, which is a growing concern as quantum computers become more powerful.

References #