1 of 3

Applications

We shall now provide a few instances where lattices are used in various algorithms. Most of these uses the LLL algorithm as it is quite fast.

Coppersmith algorithm

This algorithm solves for small roots of polynomials modulo any integer, meaning given some polynomial $f(x)\in\mathbb Z[x]$ of degree $d$ and any integer $N$ , then if $f(x_0)=0\pmod{N},|x_0|<N^{\frac1d}$ , this algorithm can find $x_0$ with time polynomial in $\log N$ and $d$ . The key idea behind this algorithm is to construct a polynomial $g(x)$ such that $g(x_0)=0$ in $\mathbb R$ . As roots of polynomials over the reals can be found easily, this gives an easy way to find $x_0$ . We shall introduce the Coppersmith algorithm in a few iterations, with each iteration approaching the $N^{\frac1d}$ bound.

Polynomials in lattices

We first consider a criteria for a root of a polynomial modulo $N$ to exists over the reals as well. Suppose $f(x)=\sum_{i=0}^df_ix^i$ is a polynomial of degree $d$ . Define the $\ell_2$ norm $\left\lVert f(x)\right\rVert_2$ of a polynomial to be $\sqrt{\sum_{i=0}^df_i^2}$ . Given $|x_0|<B,f(x_0)=0\pmod N$ , if

\left\lVert f(Bx)\right\rVert_2=\sqrt{\sum_{i=0}^d\left(f_iB^i\right)^2}\leq\frac N{\sqrt{d+1}}

then $f(x_0)=0$ in $\mathbb R$ . The proof is a relatively straightforward chain of inequalities:

\begin{align*} \frac N{\sqrt{d+1}}&\geq\sqrt{\sum_{i=0}^d\left(f_iB^i\right)^2}\\&\geq\sqrt{\sum_{i=0}^d\left(f_ix_0^i\right)^2}\\ &\geq\frac1{\sqrt{d+1}}\sum_{i=0}^d\left|f_ix_0^i\right|\\ &\geq\frac1{\sqrt{d+1}}\left|\sum_{i=0}^df_ix_0^i\right|\\ \end{align*}

and since $f(x_0)=0\pmod N$ implies $f(x_0)=kN$ for some $k\in\mathbb Z$ , we know that $k$ must be $0$ to satisfy the inequality above.

With this, if we can find some polynomials $f_i$ such that $f_i(x_0)=0\pmod N$ , then if we can find some $c_i$ such that $\left\lVert\sum_ic_if_i(x)\right\rVert_2\leq\frac N{\sqrt{d+1}}$ , then we can find $x_0$ easily. This gives a brief idea as to why lattices would be useful in such a problem.

To use lattices, notice that we can encode the polynomial $f(x)=\sum_{i=0}^df_ix^i$ as the vector with components $f_i$ . In this way, adding polynomials and multiplying polynomials by numbers still makes sense. Lets suppose that $f(x_0)=0\pmod N,x_0<B$ and $f_d=1$ (otherwise multiply $f$ by $f_d^{-1}\pmod N$ . Consider the polynomials $g_i(x)=Nx^i$ and consider the lattice $L$ generated by $f(Bx)$ and $g_i(Bx)$ , $0\leq i\leq d-1$ . As a matrix, the basis vectors are

\mathcal B=\begin{pmatrix} N&0&0&\dots&0&0\\ 0&NB&0&\dots&0&0\\ 0&0&NB^2&\dots&0&0\\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\ 0&0&0&\dots&NB^{d-1}&0\\ f_0&f_1B&f_2B^2&\dots&f_{d-1}B^{d-1}&B^d\\ \end{pmatrix}

the basis vectors of our lattice would look like

Exercises

Let

Extensions of Coppersmith algorithm

The Coppersmith algorithm can be made even more general. There are two main extensions, first to an unknown modulus, then to multivariate polynomials.

Unknown modulus

This extension of Coppersmith allows one to find small roots modulo an unknown some unknown factor of a number. More specifically, suppose that we have some unknown factor $b$ of $N$ such that $b<N^\beta$ and some monic polynomial $f$ of degree $d$ such that $f(x_0)=0\pmod b$ for some $x_0<N^{\frac{\beta^2}d}$ . Then we can find $x_0$ in time polynomial in $\log N,d$ .

One key reason why this is possible is because we dont need to explicitly know the modulus to determine if a small root exists, i.e. $\left\lVert f(Bx)\right\rVert_2\leq\frac b{\sqrt{d+1}}\leq\frac{N^{\beta}}{\sqrt{d+1}}$ is sufficient for a root less than $B$ to exist. The algorithm here is extremely similar to the Coppersmith algorithm, except we add more polynomials into the lattice. The polynomials that we will use are

\begin{align*} g_{i,j}(x)&=N^{h-j}f(x)^jx^i&0\leq i<d,0\leq j<h\\ g_{i,h}(x)&=f(x)^hx^i&0\leq i<t \end{align*}

The lattice $L$ generated by these polynomials would have

\dim(L)=dh+t=n\quad\text{vol}(L)=N^{\frac{dh(h+1)}{2}}B^{\frac{(n-1)n}2}

As we require the shortest vector to have length at most $\frac{N^{\beta h}}{\sqrt{n}}$ , repeating the computations from the previous section, we obtain

B<\sqrt{\frac{4\delta-1}4}\left(\frac1n\right)^{\frac1{n-1}}N^{\frac{2\beta h}{n-1}-\frac{dh(h+1)}{n(n-1)}}

Exercises

Extensions of Coppersmith algorithm

The Coppersmith algorithm can be made even more general. There are two main extensions, first to an unknown modulus, then to multivariate polynomials.

Unknown modulus

\begin{align*} g_{i,j}(x)&=N^{h-j}f(x)^jx^i&0\leq i<d,0\leq j<h\\ g_{i,h}(x)&=f(x)^hx^i&0\leq i<t \end{align*}

The lattice $L$ generated by these polynomials would have

\dim(L)=dh+t=n\quad\text{vol}(L)=N^{\frac{dh(h+1)}{2}}B^{\frac{(n-1)n}2}

As we require the shortest vector to have length at most $\frac{N^{\beta h}}{\sqrt{n}}$ , repeating the computations from the previous section, we obtain

B<\sqrt{\frac{4\delta-1}4}\left(\frac1n\right)^{\frac1{n-1}}N^{\frac{2\beta h}{n-1}-\frac{dh(h+1)}{n(n-1)}}

It turns out that the maxima of $\frac{2\beta h}{n-1}-\frac{dh(h+1)}{n(n-1)}$ is $\frac{\beta^2}d$ as $n,h\to\infty$ . One way to achieve this is by setting $n=\frac d\beta h$ and we obtain

B<\sqrt{\frac{4\delta-1}4}\left(\frac1n\right)^{\frac1{n-1}}N^{\frac{(h-1)\beta^2}{dh-\beta}}

and this indeed achieves the $O\left(N^{\frac{\beta^2}d}\right)$ bound. Similar to the Coppersmith algorithm, one chooses a sufficiently big $h,n$ such that the remainding bits can be brute forced in constant time while the algorithm still remains in polynomial time.

Exercises

1) We show that the maximum of $\frac{2\beta h}{n-1}-\frac{dh(h+1)}{n(n-1)}$ is indeed $\frac{\beta^2}d$ . We can assume that $d\geq2,h\geq1,0<\beta\leq1,n\geq2$ . Since $\frac h{n-1}\left(2\beta-d\frac{h+1}{n}\right)$ and $\frac h{n-1}<\frac{h+1}n$ , the maximum occurs when $h,n\to\infty$ and $\frac h{n-1},\frac{h+1}n\to x$ , hence we have reduced this to maximizing $2\beta x-dx^2$ which achieves its maximum of $\frac{\beta^2}d$ at $x=\frac\beta d$ .

Coppersmith algorithm

Polynomials in lattices

\left\lVert f(Bx)\right\rVert_2=\sqrt{\sum_{i=0}^d\left(f_iB^i\right)^2}\leq\frac N{\sqrt{d+1}}

then $f(x_0)=0$ in $\mathbb R$ . The proof is a relatively straightforward chain of inequalities:

\begin{align*} \frac N{\sqrt{d+1}}&\geq\sqrt{\sum_{i=0}^d\left(f_iB^i\right)^2}\\&\geq\sqrt{\sum_{i=0}^d\left(f_ix_0^i\right)^2}\\ &\geq\frac1{\sqrt{d+1}}\sum_{i=0}^d\left|f_ix_0^i\right|\\ &\geq\frac1{\sqrt{d+1}}\left|\sum_{i=0}^df_ix_0^i\right|\\ \end{align*}

and since $f(x_0)=0\pmod N$ implies $f(x_0)=kN$ for some $k\in\mathbb Z$ , we know that $k$ must be $0$ to satisfy the inequality above.

\mathcal B=\begin{pmatrix} N&0&0&\dots&0&0\\ 0&NB&0&\dots&0&0\\ 0&0&NB^2&\dots&0&0\\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\ 0&0&0&\dots&NB^{d-1}&0\\ f_0&f_1B&f_2B^2&\dots&f_{d-1}B^{d-1}&B^d\\ \end{pmatrix}

As every element in this lattice is some polynomial $g(Bx)$ , if $f(x_0)=0\pmod N$ , then $g(x_0)=0\pmod N$ . Furthermore, if $|x_0|<B$ and a short vector $v(Bx)$ has length less than $\frac N{\sqrt{d+1}}$ , then we have $v(x_0)=0$ in $\mathbb R$ .

The volume of this lattice is $N^dB^{\frac{d(d+1)}2}$ and the lattice has dimension $d+1$ . By using the LLL algorithm, we can find a vector $v(Bx)$ with length at most

\left\lVert v(Bx)\right\rVert_2=\underbrace{\left(\frac4{4\delta-1}\right)^{\frac d4}}_{c_{\delta,d}}\text{vol}(L)^\frac1{d+1}=c_{\delta,d}N^{\frac d{d+1}}B^{\frac d2}

As long as $c_{\delta,d}N^{\frac d{d+1}}B^{\frac d2}<\frac N{\sqrt{d+1}}$ , then by the above criteria we know that this vector has $x_0$ has a root over $\mathbb R$ . This tells us that

B<N^{\frac2{d(d+1)}}\left(c_{\delta,d}\sqrt{d+1}\right)^{-\frac 2d}

While this isn't the $N^{\frac1d}$ bound that we want, this gives us an idea of what we can do to achieve this bound, i.e. add more vectors such that the length of the shortest vector decreases.

Achieving the $N^{\frac1d}$ bound

One important observation to make is that any coefficients in front of $N^x$ does not matter as we can simply brute force the top bits of our small root in $O(1)$ time. Hence we only need to get $B=kN^{\frac1d}$ for some fixed constant $k$ .

In order to achieve this, notice that if $f(x_0)=0\pmod N$ , then $f(x_0)^h=0\pmod{N^h}$ . This loosens the inequality required for a polynomial to have $x_0$ as a small root as our modulus is now larger. With this in mind, consider the polynomials

g_{i,j}(x)=N^{h-j}f(x)^jx^i\quad0\leq i<d,0\leq j<h

where we will determine $h$ later. Here $g_{i,j}(x_0)=0\pmod{N^h}$ , hence we shall consider the lattice $L$ generated by $g_{i,j}(Bx)$ . As an example, if we have

f(x)=x^3+2x^2+3x+4\quad h=3

the basis vectors of our lattice would look like

\footnotesize{\left(\begin{array}{rrrrrrrrr} N^{3} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & B N^{3} & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & B^{2} N^{3} & 0 & 0 & 0 & 0 & 0 & 0 \\ 4 \, N^{2} & 3 \, B N^{2} & 2 \, B^{2} N^{2} & B^{3} N^{2} & 0 & 0 & 0 & 0 & 0 \\ 0 & 4 \, B N^{2} & 3 \, B^{2} N^{2} & 2 \, B^{3} N^{2} & B^{4} N^{2} & 0 & 0 & 0 & 0 \\ 0 & 0 & 4 \, B^{2} N^{2} & 3 \, B^{3} N^{2} & 2 \, B^{4} N^{2} & B^{5} N^{2} & 0 & 0 & 0 \\ 16 \, N & 24 \, B N & 25 \, B^{2} N & 20 \, B^{3} N & 10 \, B^{4} N & 4 \, B^{5} N & B^{6} N & 0 & 0 \\ 0 & 16 \, B N & 24 \, B^{2} N & 25 \, B^{3} N & 20 \, B^{4} N & 10 \, B^{5} N & 4 \, B^{6} N & B^{7} N & 0 \\ 0 & 0 & 16 \, B^{2} N & 24 \, B^{3} N & 25 \, B^{4} N & 20 \, B^{5} N & 10 \, B^{6} N & 4 \, B^{7} N & B^{8} N \end{array}\right)}

We have the following immediate computations of $L$ :

\dim(L)=dh\quad\text{vol}(L)=N^{\frac{dh(h+1)}2}B^{\frac{(dh-1)dh}2}

hence when using the LLL algorithm, the shortest LLL basis vector $v(Bx)$ has length

\begin{align*} \left\lVert v(Bx)\right\rVert_2&=\left(\frac4{4\delta-1}\right)^{\frac{\dim(L)-1}4}\text{vol}(L)^{\frac1{\dim(L)}}\\ &=\left(\frac4{4\delta-1}\right)^{\frac{dh-1}4}N^{\frac{h+1}2}B^{\frac{dh-1}2}\\ \end{align*}

and we need $\left\lVert v(Bx)\right\rVert_2<\frac{N^h}{\sqrt{dh}}$ for $v(x_0)=0$ . Hence we have

B<\sqrt{\frac{4\delta-1}4}\left(\frac1{dh}\right)^{\frac1{dh-1}}N^{\frac{h-1}{dh-1}}

Since $\lim_{h\to\infty}\frac{h-1}{dh-1}=\frac1d$ , this will achieve the $N^{\frac1d}$ bound that we want. However as for big $h$ , the LLL algorithm would take a very long time, we typically choose a suitably large $h$ such that the algorithm is still polynomial in $\log N,d$ and brute force the remaining bits.

Exercises

1) We often see $h=\left\lceil\max\left(\frac{d+d\varepsilon-1}{d^2\epsilon},\frac7d\right)\right\rceil$ in literature. We shall now show where this mysterious $\frac7d$ comes from. The other term will appear in the next exercise. Typically, one sets $\delta=\frac34$ to simplify calculations involving the LLL algorithm as $\frac4{4\delta-1}=2$ . Suppose we want $B>\frac12N^{\frac{h-1}{dh-1}}$ , show that this gives us $dh\geq7$ .

2) We show that we can indeed find small roots less than $N^{\frac1d}$ in polynomial time. In the worse case, the longest basis vector cannot exceed $O\left(B^{dh-1}N^h\right)$ . Hence the LLL algorithm will run in at most $O(d^6h^6(d+h)^2\log^2N)$ time.

Let

\varepsilon=\frac1d-\frac{h-1}{dh-1}\quad h=\frac{d+d\varepsilon-1}{d^2\epsilon}\approx\frac1{d\varepsilon}

and choose $\varepsilon=\frac1{\log N}$ , then $N^\varepsilon$ is a constant hence the number of bits needed to be brute forced is a constant. This gives us the approximate run time of $O((d+\frac1d\log N)^2\log^8N)$ .

3) We shall show that this is the best bound we can hope for using lattice methods. Suppose there exists some algorithm that finds roots less than $O\left(N^{\frac1d+\epsilon}\right)$ in polynomial time. Then consider the case when $N=p^2$ and $f(x)=x^2+px$ . Show that this forces the lattice to have a size too big for the algorithm to run in polynomial time, assuming the algorithm finds all small roots.

Applications

Coppersmith algorithm

Polynomials in lattices

Exercises

Extensions of Coppersmith algorithm

Unknown modulus

Exercises

Applications

Extensions of Coppersmith algorithm

Unknown modulus

Exercises

Coppersmith algorithm

Polynomials in lattices

Achieving the N1dN^{\frac1d}Nd1​bound

Exercises

Achieving the N1dN^{\frac1d}Nd1​bound

Achieving the $N^{\frac1d}$ bound

Achieving the $N^{\frac1d}$ bound