Intro to Lattice-based cryptography

$$The main reference is Mathematics of Public Key Cryptography by Steven Galbraith and J. Silverman's note for PCMI 2022.

Lattice

In a vector space ${\mathbb{R}}^n$, a lattice is a discrete subgroup which is equivalent to $\mathbb{Z}$-span of a basis. For example, $\mathbb{Z}$-span of $v_1=(1,0)$ and $v_2=(0,1)$,
$$L=\mathbb{Z}⟨v_1,v_2⟩=\{(c_1,c_2)\mid c_1,c_2\in \mathbb{Z}\}$$
is a lattice.

Like a vector space, a single lattice can have various bases. For example, $w_1=(2,-1)$ and $w_2=(-1,1)$ spans the same $L$. To check a certain basis spans the lattice, we need to see basis basis-changing matrix. Since $\{v_1,v_2\}$ and $\{w_1,w_2\}$ are both $\mathbb{R}$-basis, we have an invertible matrix $A$ such that
$$\left(w_1|w_2\right)=A\left(v_1|v_2\right)$$
Then, two bases span the same lattice if and only if $A\in {\mathrm{GL}}_n(\mathbb{Z})$, that is, entries of $A$ are all integers and $detA=\pm 1$. In our example, $A=\left(\begin{array}{cc}2& -1\\ -1& 1\end{array}\right)$ whose determinant is 1. For future applications, we will define the fundamental domain of a lattice with respect to a basis
$$F(L,v_1,\dots ,v_n)=\{c_1{v}_1+\cdots +c_n{v}_n\mid 0\le c_i<1\}$$

Hard Lattice Problems

Like a prime factorization in RSA, we will need a hard problem for cryptographic applications. For a given lattice $L$ and $z\in {\mathbb{R}}^n$, the closest vector problem (CVP) is to find a lattice point that is closest to the target point $z$. That is,
$$\mathrm{CVP}(L,z)={\arg min}_{v\in L}\Vert v-z\Vert$$

A generous version of CVP is the approximate closed vector problem ($\kappa$-CVP). This problem is to find a reasonably close vector to $z$. Formally, for $\kappa \ge 1$, the solution satisfies
$$\Vert \kappa \text{-CVP}(L,z)-z\Vert \le \kappa \underset{v\in L}{min}\Vert v-z\Vert$$
If $\kappa =1$, $\kappa$-CVP is equivalent to CVP.

In RSA, we can solve the hard problem easily with a private key. The same thing happens for lattice problems. A private key will be a "good" basis (I will explain it precisely later). With a good basis, we can solve $\kappa$-CVP easily using Babai's rounding-off algorithm. The algorithm is simple. Given a lattice $L$ and a basis $\{v_1,\dots ,v_n\}$, the target point $z\in {\mathbb{R}}^n$ can be written as $z=c_1{v}_1+\cdots +c_n{v}_n$. Then, the output is $[c_1]v_1+\cdots +[c_n]v_n$, where $[c_i]$ is the integer closest to $c_i$. We hope this vector is a solution to CVP, but it's not in general.

In the previous example, let the target point $z=(-0.2,-0.2)$. With basis $\{v_1,v_2\}$, $z=-0.2v_1-0.2v_2$, so Babai's rounding-off algorithm outputs $(0,0)$, which is a correct answer to CVP. But, with basis $\{w_1,w_2\}$, $z=-0.4w_1-0.6w_2$, so the output is $-w_2=(1,-1)$. Babai's rounding-off algorithm highly depends on the basis, one can see that the rounding-off algorithm with the first basis $\{v_1,v_2\}$ solves every CVP because $v_1$ and $v_2$ are orthogonal. So, the desired "good" property is "nearly orthogonal" which can be formalized by LLL-reduced condition. And, with an LLL-reduced basis, we can solve $\kappa$-CVP for some $\kappa$. I will explain this in another post. Let's just note that some efficient algorithm with a "good" basis can solve $\kappa$-CVP.

Goldreich-Goldwasser-Halevi Cryptosystem

GGH cryptosystem is based on the hardness of CVP. The private key is a "good" basis $B=\{v_1,\dots ,v_n\}$. We can consider the lattice $L$ spanned by $B$ With private key, one can make a "bad" basis $B^{\prime }=UB$ for some random integer matrix with determinant $\pm 1$. Then, $B^{\prime }$ is also a basis of $L$, and it is a public key. With the public key $B^{\prime }$ and a message $m\in {\mathbb{Z}}^n$, the ciphertext is $x=B^{\prime }m+e$ where $e\in {\mathbb{R}}^n$ is a random small vector. Note that the vector $B^{\prime }m$ belongs to the lattice $L$. We want $e$ is small enough so that the closest lattice point of $x$ is $B^{\prime }m$. With a knowledge of the good basis $B$, one can decrypt the ciphertext by solving CVP and multiply $B^{\prime -1}$.
One way to attack the GGH system is to obtain another good basis from public key $B^{\prime }$ using LLL reduction. To prevent this, the size of the lattice should be large enough.

The problem with GGH is the length of the keys. To prevent known attacks on GGH, we need large $n>2000$. But, the size of public/private keys of GGH is $O(n^2)$, which is really large even compared to secure 4096 bits RSA.

NTRU Cryptosystem

We first define a binary operation convolution on ${\mathbb{Z}}^n$. For $(a_i),(b_i)\in Z^n$, define
$$(a_i)\odot (b_i)=(c_i),c_i=\sum _{j+k\equiv i\text{ mod }n}{a}_j{b}_k.$$
Note that this convolution is the same as the multiplication in $\mathbb{Z}[X]/(X^n-1)$, by interpreting $(a_i)$ as $a_0+a_{1}x+\cdots +a_{n-1}{x}^{n-1}$. Similarly, we can define convolution ${\odot }_p$ on $(\mathbb{Z}/p\mathbb{Z}{)}^n$ for any integer $p$.

The public/private keys of NTRU are generated like this. First, choose a prime $n$ and two integers $p<<q$. Then choose small $f,g\in {\mathbb{Z}}^n$ and find $f_p,f_q\in {\mathbb{Z}}^n$ such that

$$\overline{f}{\odot }_p\overline{f_p}=(1,0,0,\dots 0),\overline{f}{\odot }_q\overline{f_q}=(1,0,0,\dots 0).$$
Here, $\overline{f}$ is a projection from ${\mathbb{Z}}^n$ to $(\mathbb{Z}/p\mathbb{Z}{)}^n$ or $(\mathbb{Z}/q\mathbb{Z}{)}^n$ (which is certain in context). The public key is $h=\overline{g}{\odot }_q\overline{f_q}$ and the private key is $f$. For a small message $m\in (\mathbb{Z}/p\mathbb{Z}{)}^n$, the ciphertext is

$$c=p\cdot \overline{r}{\odot }_{q}h+m\text{ mod }q$$

where $r$ is a small random vector.

To recover the ciphertext $c$, first compute

$$a=c{\odot }_q\overline{f}=(p\cdot \overline{r}{\odot }_{q}g{\odot }_q{f}_q+m){\odot }_q\overline{f}=p\cdot \overline{r}{\odot }_{q}g+m{\odot }_q\overline{f}\text{ mod }q$$

The equation above is in $(\mathbb{Z}/q\mathbb{Z}{)}^n$. But, since $f,g,r,m$ are small and $p<<q$,

$$a=p\cdot \overline{r}{\odot }_{q}g+m{\odot }_q\overline{f}\in {\mathbb{Z}}^n$$

Now, multiplying $f_p$ to obtain

$$a{\odot }_p\overline{f_p}=p\cdot \overline{r}{\odot }_{q}g{\odot }_p\overline{f_p}+m{\odot }_q\overline{f}{\odot }_p\overline{f_p}=m\text{ mod }p$$

We want to interpret this cryptosystem as a lattice problem. We first convert the convolution relation into a lattice membership problem. Let $h=(h_0,\dots ,h_{n-1})\in {\mathbb{Z}}^n$ and

$$B_h=\left(\begin{array}{cc}{I}_n& 0\\ \begin{array}{cccc}{h}_0& h_1& \dots & h_{n-1}\\ h_{n-1}& h_0& \dots & h_{n-2}\\ ⋮& ⋮& \ddots & ⋮\\ h_1& h_2& \dots & h_0\end{array}& q{I}_n\end{array}\right)$$

Let $L_h$ be the lattice spanned by $B_h$. Suppose $a,b\in {\mathbb{Z}}^n$ satisfies

$$\overline{a}{\odot }_q\overline{h}=\overline{b}\text{ mod }q.$$

This implies we have $u\in {\mathbb{Z}}^n$ such that

$$q\cdot u=b-a\odot h$$

Then, $B_h(\genfrac{}{}{0ex}{}{a}{u})=(\genfrac{}{}{0ex}{}{a}{b})\in L_h$. One can also show that $(\genfrac{}{}{0ex}{}{a}{b})\in L_h$ if and only if $\overline{a}{\odot }_q\overline{h}=\overline{b}$.

In the NTRU cryptosystem, the ciphertext is

$$c=p\cdot \overline{r}{\odot }_{q}h+m\text{ mod }q$$

This equation is equivalent to

$$(0|c)=(0|p\cdot \overline{r}{\odot }_{q}h+m)=(r|r\odot ph)+(-r,m)$$

Since $r,m$ is small and $(r|r\odot ph)\in L_{ph}$, recovering $m$ is equivalent to solve CVP for $(0|c)$. In other words, NTRU is based on a lattice problem for special type lattice $B_{ph}$. The circular property of the basis reduces the length of keys into $O(n\log n)$.