## Chapter 3 Algorithm for the Closest and Shortest Vector Problems

### 3.1 Babai’s Rounding Technique

Theorem 3.1.1. Given a vector we can write $\underline{\omega}=\sum_{i=1}^{n}\alpha_{i}\underline{b_{i}}$ with $\alpha_{i}\in R$. The rounding technique is simply to set

$\left|\underline{v}-\underline{w}\right|$ is within an exponential factor of the minimal value if the basis is LLL-Reduced. The method trivially generalises to non-full-rank lattices as long as $\underline{\omega}$ lies in the R-span of the basis.

Theorem 3.1.2. Let $\{\underline{b}_{1},…,\underline{b}_{n}\}$ be an LLL-Reduced basis (with factor $\delta=\frac{3}{4}$) for a Lattice $L\subset R^{n}$. Then the output $\underline{v}$ of the Babai rounding method on input $\underline{\omega}\in R^{n}$ satisfies

for all $\underline{u}\in L$.

### 3.2 The Embedding Technique

Theorem 3.2.1. Embedding’s solution to the CVP corresponds to integers $l_{1},…,l_{n}$ such that

The idea is to define a lattice L’ that contains the short vector $\underline{e}(\underline{e}=\underline{\omega}-\sum_{i=1}^{n}l_{i}\underline{b_{i}})$. Let $M\in R_{>0}$ (usually let M=1). The lattice L’ is defined by the vectors (which are a basis for $R^{n+1}$)

Hence, we might be able to find $\underline{e}$ by solving the SVP problem in the lattice L’. Then we can solve the CVP by subtracting $\underline{e}$ from $\underline{\omega}$.

Example: the CVP whose basis is for $R^{1}$

add $(\underline{\omega},M)$ to define L’ in $R^{2}$

solving the SVP to find $\delta$

Lemma 3.2.2. Let $\{\underline{b}_{1},…,\underline{b}_{n}\}$ be a basis for a lattice $L\subset Z^{n}$ and donate by $\lambda_1$ the shortest Euclidean length of a non-zero element of L. Let $\underline{\omega}\in R^{n}$ and let $\underline{v}\in L$ be a closest lattice point to $\underline{\omega}$. Define $\underline{e}=\underline{\omega}-\underline{v}$. Suppose that $\left|\underline{e}\right|<\lambda_1/2$ and let $M=\left|\underline{e}\right|$. Then $(\underline{e},M)$ is a shortest non-zero vector in the lattice L’ of the embedding technique.

Proof: All vectors in L’ are of the form

for some $l_{i}\in Z$. It is clear that every non-zero vector with $l_{n+1}=0$ is of length at least $\lambda_{1}$.

Since $\left|(\underline{e},M)\right|^{2}=\left|\underline{e}\right|^{2}+M^{2}=2M^{2}<\frac{\lambda^{2}}{2}$, the vector $(\underline{e},M)$ has length at most $\frac{\lambda_1}{\sqrt{2}}$. Since $\underline{v}$ is a closest vector to $\underline{\omega}$ in the lattice L, $\forall_{\underline{x}\in L},s.t.\left|\underline{e}\right|\leq \left|\underline{e}+\underline{x}\right|$. SVP’s correctness proved.

### 3.3 Korkine-Zolotarev Bases

Schnorr has developed the block Korkine-Zolotarev lattice basis reduction algorithm, which computes a Korkine-Zolotarev basis for small dimensional projections of the original lattice and combines this with the LLL algorithm. The output basis can be proved to be of a better quality than an LLL-reduced basis. This is the most powerful algorithm for fifinding short vectors in lattices of large dimension.

### 4.1 Coppersmith’s Method for Modular Univariate Polynomials

#### 4.1.1 First Steps to Coppersmith’s Method

Let $F(x)=x^{d}+a_{d-1}x^{d-1}+…+a_{1}x+a_{0}$ be a monic polynomial of degree d with integer coefficients. Suppose we know that there exist one or more integers $x_{0}$ such that $F(x)\equiv 0(mod\ M)$ and that $x_{0}<M^{\frac{1}{d}}$. The problem is to find all such roots.

Since $|x_{0}^{i}|<M$ for all $0\leq i\leq d$ then, if the coefficients of F(x) are small enough, one might have $F(x_{0})=0$ over Z. In this case, the problem can be easily solved by Newton’s method (round the approximations of the roots to the nearest integer and check whether they are solutions of F(x)). However, we wanna deal with polynomials F(x) having a small solution but whose coefficients are not small.

Coppersmith’s idea is to build from F(x) a polynomial G(x) that still has the same solution $x_{0}$, but which has coefficients small enough.

Theorem 4.1.1. (Howgrave-Graham [296]) Let $M, X\in N$ and let $F(x)=\sum_{i=0}^{d}a_{i}x^{i}\in Z[x]$. Suppose $x_{0}\in Z$ is a solution to $F(x)\equiv 0(mod\ M)$ such that $|x_{0}|<X$. We associate with the polynomial F(x) the row vector $b_F=(a_0,a_{1}X,a_{2}X^{2},…,a_{d}X^{d})$. If $\left|b_{F}\right|<\frac{M}{\sqrt{d+1}}$ then $F(x_{0})=0$.

Proof: Cauchy-Schwarz inequality $\rightarrow\sum_{i=1}^{n}x_{i}\leq \sqrt{n\sum_{i=1}^{n}x_{i}^{2}}$.

So, $|F(x_{0})|=|\sum_{i=0}^{d}a_{i}x_{0}^{i}|\leq \sum_{i=0}^{d}|a_{i}||x_{0}|^{i}\leq \sum_{i=0}^{d}|a_{i}|X^{i}\leq \sqrt{d+1}\left|b_{F}\right|<\sqrt{d+1}\frac{M}{\sqrt{d+1}}=M$.

$\therefore F(x_{0})=0$.

Then how to transform F(x) to G(x) we need?

To do this, consider the d+1 polynomials $G_{i}(x)=Mx^{i}$ for $0\leq i<d$ and F(x). They all have the solution $x=x_{0}$ module M. Define the lattice L with the basis B