I want to break free from Lattice-based cryptography, but not even a quantum computer can help me

Introduction

Public key encryption is a secure way of sending information over the internet. It uses two keys: a public key and a private key. We use the public key to encrypt messages. We can share this key publicly. The private key is kept secret and only known to the owner, who can use it to decrypt messages. This concept was introduced in a groundbreaking paper by Diffie and Hellman in the late 1970s and offered several advantages over previously used methods, including enhanced security, secure key exchange, digital signatures, scalability, and easier key management.

The working principle behind public key cryptography is that some complex mathematical problem (which can be easily verified if we know the solution or some secret information, but it is otherwise computationally expensive) relates the keys. For example, in the RSA cryptosystem, the public key denoted as $e$, and the private key, represented as $d$, are related by the expression $d \times e \equiv 1 (\mod \phi(n))$. This means that $e$ is the multiplicative inverse of $d$ modulo a function called Euler's totient function evaluated at $n$, denoted as $\phi(n)$. There are efficient algorithms to compute modular inverses. Still, they require knowing the prime factorization of $n$, which is very hard for large numbers and could take longer than our lifespans, even with the fastest supercomputers.

Elliptic curve cryptography is another type of public key cryptography that uses a different mathematical approach. In this system, the secret key, denoted as $sk$, is related to the public key, denoted as $pk$, through a generator of a large subgroup of an elliptic curve, represented as $g$, by the expression $pk = g^{sk}$. We can recover the secret key from the public key if we find the exponent in this expression, known as the discrete logarithm problem. Depending on the properties of the curve and its subgroups, this problem can be tough to solve.

However, there is a potential threat to these public key encryption schemes posed by the advent of quantum computers, which are based on a different technology than conventional computers and can solve specific hard problems much faster. To address this, cryptographers have been working on other encryption schemes that can resist quantum computers, known as post-quantum secure cryptosystems. The NIST (National Institute of Standards and Technology) is standardizing one or more quantum-secure algorithms. Many of these schemes are based on the hardness of specific problems over lattices, leading to lattice-based cryptography.

Lattice-based cryptography is resistant to quantum computers and can also be used to construct fully homomorphic encryption schemes, which have important applications in secure computing and data privacy.

Lattices

In mathematics, a lattice is a regular arrangement of points in a multi-dimensional space, forming a grid-like structure. Imagine a piece of graph paper where the intersections of the horizontal and vertical lines create a lattice. Depending on the problem being addressed, lattices can have different shapes, sizes, and dimensions depending on the problem being addressed.

Formally, a lattice can be defined as a set of points generated by linear combinations of a set of basis vectors with integer coefficients. These basis vectors define the directions and spacing of the lattice points. The lattice can span multiple dimensions, with each dimension corresponding to a different basis vector. For example, in two-dimensional space, a lattice can be represented by two basis vectors that define the spacing between the lattice points along the horizontal and vertical directions. Below is the image of a hexagonal lattice spanned by two vectors forming a 120° angle.

Given a set of linearly independent vectors, $\mathbb{V} = { v_1 , v_2 , v_3 , ... , v_m }$ in $\mathbb{R}^n$, the lattice generated by $\mathbb{V}$ is given by the set,

$$ L = { a_1 v_1 + a_2 v_2 + \dots + a_m v_m : a_k \in \mathbb{Z}}$$

The dimension of $L$ is the number of vectors in a basis for $L$. We can use other vectors as basis $\mathbb{W} = { w_1 , w_2 , \dots , w_m}$ for $L$. The basis vectors are related by
$w_1 = a_{11} v_1 + a_{12} v_2 + \dots + a_{1m}v_m$
$w_2 = a_{21} v_1 + a_{22} v_2 + \dots + a_{2m}v_m$
$\vdots$
$w_m = a_{m1} v_1 + a_{m2} v_2 + \dots + a_{mm}v_m$

which can be written in matrix form as
$$\mathbf{w} = A \mathbf{v}$$

The matrix $A$ is invertible, and we can also write the relationship between the bases as
$$A^{-1} \mathbf{w} = \mathbf{v}$$

For example, in $\mathbb{R}^3$ we can have a cubic lattice using as vectors three perpendicular vectors, which we can represent as $E = { (1,0,0) , (0,1,0) , (0,0,1) }$; the lattice is given by the triple of integers $(x,y,z)$. We could also select as basis the vectors $B = { (2,1,1), (3,2,1), (1,1,1)}$. The matrix $A$ contains as rows the vectors from $B$.

Some bases are nicer than others. For example, the basis $E$ has three perpendicular (orthogonal) vectors of length 1. On the other hand, the vectors in basis $B$ are more prolonged and not perpendicular. We will shortly see that a nicer basis allows us to solve some lattice problems easily.

Shortest Vector Problem

Two important mathematical problems in lattices are the following:

• Shortest vector problem (SVP): we want to find a non-zero vector $\mathbf{v}$ in the lattice having the shortest length, $\Vert \mathbf{v} \Vert$.
• Closest vector problem (CVP): given $\mathbf{w}$ in a lattice, we want to find a vector $\mathbf{v}$ which is closest to $\mathbf{w}$, that is, we want the vector $\mathbf{w} - \mathbf{v}$ to have minimal length.

When we have an orthogonal set of basis vectors (that is, each pair of vectors is orthogonal), we can use the Pythagorean theorem to see that
$$\Vert \mathbf{u} \Vert^2 = a_1^2 \Vert \mathbf{v_1} \Vert^2 + a_2^2 \Vert \mathbf{v_2} \Vert^2 + \dots + a_m^2 \Vert \mathbf{v_m} \Vert^2$$
where all $a_k$ are integers. Therefore, the vectors of minimal length are contained in the set ${ \pm \mathbf{v_1} , \pm \mathbf{v_2} , \dots , \pm \mathbf{v_m}}$

If the basis is not orthogonal but still "nice," we can use Babai's algorithm to obtain a "good" approximation to the solution. This strategy fails if the basis vectors are close to each other.

Ring Learning with Errors

The Learning with Errors (LWE) problem is a mathematical problem used in cryptography to secure communication and protect data. It involves finding a hidden pattern in noisy data. Think of it like trying to solve a puzzle where you are given a bunch of equations with some errors, and you need to figure out the correct relationship between the variables despite the errors. In LWE, the equations are represented as numbers modulo a large prime number, and the goal is to find the hidden linear relationship between them despite the noise.

Formally, given pairs $(\mathbf{a} , b)$ related by some linear function $b_k \approx \mathbf{s^t}.\mathbf{a}$ the goal is to distinguish these pairs from uniformly sampled random points $(\mathbf{x} , y)$. Each pair $(\mathbf{a}_k , b_k)$ contains a random error $e_k$, and we have to find $\mathbf{s}$ despite these errors.

Convolution polynomial rings

Say we are working with the polynomials with coefficients over some ring, such as the integers, $\mathbb{Z}[x]$. The following set gives the $n$-th degree convolution polynomials
$$ R = \mathbb{Z}[x] / (x^n - 1) $$

This means we have polynomials modulo $x^n - 1$ analogously as we worked with integers. In integers, we said that $15 \equiv 1 \mod 7$ because it can be written as a multiple of $7$ plus a remainder, that is, $15=2\times 7 + 1$. We could work easily with $1$ instead of $15$ and operate with it. In polynomials, $x^5 + x^2 + 1 \equiv x + 2 \mod x^2 - 1$, because
$$ x^5 + x^2 + 1 = (x^2 - 1)(x^3 + x^2 + x +1) + (x + 2)$$

The exciting property when using $x^n -1$ is that whenever we spot a power $x^n$, we can replace $x^n$ by $1$ (in the case of more complex polynomials, we would have to carry out the division and find the remainder). This also leads to a more straightforward expression for polynomial multiplication. Let's look at an example first,
$$ (x^2 + 3 x + 5)(2x^2 + 2 x + 7) = p(x) \mod (x^3 - 1)$$
The standard calculation would make us apply distributive property, sum all terms with the same powers and reduce all powers greater than 2:
$$ 2x^4 + 2x^3 + 7x^2 + 6x^3 + 6x^2 + 21x + 10x^2 + 10 x +35 = p(x)$$
Summing,
$$ 2x^4 + 8x^3 + 23 x^2 + 31 x + 35 = p(x)$$
Applying the reduction,
$$p(x) = 23 x^2 + 33 x + 43$$
A more straightforward way would be to realize that the coefficient $p_k$ for term $x^k$ is given by this expression:
$$p_k = \sum_{i+j \equiv k \mod 3} a_i b_j$$
For $x^2$ we have
$$p_2 = a_2 b_0 + a_1 b_1 + a_0 b_2 = 7 + 6 + 10 = 23$$
For $x$ we have
$$p_1 = a_1 b_0 + a_0 b_1 + a_2 b_2 = 2 + 21 + 10 = 33$$
Finally,
$$p_0 = a_0 b_0 + a_2 b_1 + a_1 b_2 = 35 + 2 + 6 = 43$$

In general, we have
$$a(x) \times b(x) = c(x)$$
where
$$ c_k = \sum_{i+j \equiv k \mod n} a_i b_{k-i}$$

If you studied Laplace or Fourier transform, you'll find that it is the convolution of $a$ and $b$. If the coefficients of the polynomials can only take the values $-1, 0, 1$, then the previous calculation is even faster.

We can work with polynomials defined over some finite field, $\mathbb{Z}_q$. The convolution polynomial ring is
$$R_q = \mathbb{Z_q}[x]/(x^n - 1)$$

In $\mathbb{Z}_q$, we saw that an element $a$ had a multiplicative inverse $b$ (such that $a\times b \equiv 1 \mod q$) if and only if $a$ and $q$ are coprime, that is, $gcd(a,q) = 1$ (gcd stands for greatest common divisor). An analogous result exists in $R_q$, stating that a polynomial $p(x)$ has a multiplicative inverse, $q(x)$, ($p(x)q(x) \equiv 1 \mod x^n -1$) if and only if $gcd(p(x) , x^n -1)=1$.

Lattices and polynomial rings

We can map elements from a polynomial ring into points of a lattice. The simplest way is via the coefficient embedding: we see the $k$-th coefficient, $p_k$ as the $k-th$ coordinate of a vector in $\mathbb{Z}_q^k$. This embedding has the nice property that adding polynomials corresponds to the component-wise addition of lattice points, but multiplication does not have a nice geometrical interpretation. In an upcoming post, we will explain in more detail how to reduce the NTRU key recovery to the shortest vector problem over some lattice.

NTRU

NTRU (N-th degree Truncated polynomial Ring Units) is a public key encryption scheme that works using three convolution polynomial rings,
$$\mathcal{R} = Z[x]/(x^n - 1)$$
$$\mathcal{R_q} = Z_q[x]/(x^n - 1)$$
$$\mathcal{R_p} = Z_p[x]/(x^n - 1)$$

where $n$ is a prime number and not equal to $q$. A pair of polynomials gives the secret keys in NTRU, whose coefficients can only take the values $-1, 0, 1$. These polynomials are called trinary polynomials and denote their families by $\mathcal{T}(d_1 , d_2)$. $d_1$ is the number of coefficients equal to one, and $d_2$ is the number of coefficients equal to $-1$ (given that the polynomial has degree at most $n$, there are $n - d_1 - d_2$ coefficients equal to zero). For example, $x^3 - x^2 + 1$ is a trinary polynomial ($d_1 = 2$, $d_2 = -1$), while $2x^3 + x - 3$ is not. The private key is given by the pair $f(x)$ and $g(x)$, where
$f(x) \in \mathcal{T}(d+1 , d)$
$g(x) \in \mathcal{T}(d , d)$

The polynomial $f(x)$ has $d+1$ ones, and $d$ coefficients equal $-1$ (If the polynomial has the same amount of $-1$ and $1$, it has no multiplicative inverse).

We next calculate $F_q (x) = {f(x)}^{-1}$ and $F_p (x) = {f(x)}^{-1}$ in the rings $\mathcal{R_q}$ and $\mathcal{R_p}$, respectively and obtain the public key as
$h(x) = F_q (x) g(x)$
in $\mathcal{R_q}$ (If the polynomial $f(x)$ has no inverse, we have to choose another one). This is the key we will use to encrypt messages. The decryption key is given by $(f(x) , F_p(x))$.

We must encode messages as polynomials in the ring $\mathcal{R_p}$ to encrypt messages. As such, they will have coefficients in the range ${ -p/2, -(p-1)/2, ..., -1, 0, 1, ..., p/2}$. We sample some random polynomial, $r(x)$ in $\mathcal{T}(d,d)$ and compute the ciphertext as
$c(x) = p h(x) r(x) + m(x) \mod q$
We can see we are adding some "random noise" to the plaintext to hide it.

If we want to decrypt, we first compute
$a (x) = f(x) c(x) \mod q$
$b (x) = F_p (x) a(x) \mod p$

If we choose the parameters correctly, then $b(x) = m(x)$, which we can decode to obtain the message. To specify NTRU, we need to set the values $(n, q, p, d)$, where $n$ and $q$ are coprime and $q > (6 d +1 )p$. To understand why this works, we can look at the calculations in more detail:
$a(x) = f(x) c(x) \mod q$
If we expand $c(x)$,
$a(x) = p f(x) F_q (x) g(x) r(x) + f(x)m(x) \mod q$
but $f(x) F_q (x) \equiv 1 \mod q$, so
$a(x) = p g(x) r(x) + f(x)m(x) \mod q$
The assumption $q > (6d + 1)p$ ensures that the polynomial $a(x)$ is computed exactly and there is no wrap-around $q$.
When we apply $F_p (x)$, we get
$b(x) = p F_p (x) g(x) r(x) + F_p (x) f(x) m(x) \mod p$
Given that all the coefficients of $p F_p (x) g(x) r(x)$ are multiples of $p$ (the factor $p$ first ensures this), that polynomial vanishes modulo $p$. We are left with
$b(x) = F_p (x) f(x) m(x) \mod p$
but $F_p (x)$ is the inverse of $f(x)$ in $\mathcal{R_p}$, so
$b(x) = m(x)$

Summary

Lattice-based cryptography is a promising solution to protect against potential attacks from quantum computers. Lattices are organized arrangements of points in multi-dimensional spaces that form the foundation of lattice-based cryptography. These lattices allow for the construction of encryption schemes. The hardness of specific problems over lattices, such as the Learning With Errors (LWE) problem and the Shortest Vector Problem (SVP), serve as the basis for the security of lattice-based cryptography. These problems are believed to be difficult even for quantum computers, making lattice-based cryptography a compelling option for post-quantum security. In upcoming posts, we will cover more on the fundamentals of lattices and encryption schemes such as CRYSTALs Kyber.