Solving SVP in Dimension 2

Reduced Basis

Definition 2.1 - Let $[a,b]$ be a lattice basis. The basis is reduced if

$$|\parallel a\parallel ,\parallel b\parallel \le \parallel a+b\parallel ,\parallel a-b\parallel$$

Intuition Behind

Consider constructing a triangle with known two edges $a$ and $b$, the third edge is unknown. If $[a,b]$ is reduced, by definition, we can say that $a,b$ are the shortest two edges of the triangle.

---

Lemma 2.1 - Consider three vectors on a line, $x,x+y,x+ay$, where $a\in \mathbb{R}$. Then if $\parallel x\parallel \le \parallel x+y\parallel$ then $\parallel x+y\parallel \le \parallel x+ay\parallel$, moreover $\parallel x+y\parallel \le \parallel x+ay\parallel$.

Explanation

Intutively, given $x,x+y$, if $\parallel x\parallel \le \parallel x+y\parallel$, then we are clear that both $x$ and $y$ are pointing in roughly the same direction, and adding any multiple of $y$ to $x+y$ will only increase the norm.

Similarly, if $\parallel x\parallel \le \parallel y-x\parallel$, then $y$ and $x$ are pointing in roughly the contradictory direction, furthermore, $\parallel x\parallel \le \parallel y-x\parallel \le \parallel ay-x\parallel$.

IMPORTANT

So what is the relationship between reduced basis and the successive minima of the lattice?

Theorem 2.2 - Let $[a,b]$ be a lattice basis, and let ${\lambda }_1$ and ${\lambda }_2$ be the successive minima of the lattice. If the basis is reduced, then $\parallel a\parallel ={\lambda }_1$ and $\parallel b\parallel ={\lambda }_2$.

Explanation

From the definition of reduced basis, we know that whether $a$ and $b$ have the same direction or not, we need to ensure that either of $a$ or $b$ is the shortest vector in the lattice. Without loss of generality, we assume $\parallel a\parallel \le \parallel b\parallel$ :

• if $a,b$ have the same direction, then $\parallel b\parallel \le \parallel a+b\parallel$.
• if $a,b$ have the opposite direction, then $\parallel b\parallel \le \parallel a-b\parallel$. put them together, we need to ensure $\parallel b\parallel \le min\{\parallel a+b\parallel ,\parallel a-b\parallel \}$. Therefore,

$$\parallel a\parallel \le \parallel b\parallel \le min\{\parallel a+b\parallel ,\parallel a-b\parallel \}$$

In general, we have

$$\parallel a\parallel ,\parallel b\parallel \le \parallel a+b\parallel ,\parallel a-b\parallel$$

namely, basis $[a,b]$ is reduced.

Gauss Algorithm

Definition 2.2 - For a lattice basis $[a,b]$, without loss of generality, we assume $\parallel a\parallel \le \parallel b\parallel$, if $\parallel a\parallel \le \parallel a-b\parallel \le \parallel b\parallel$, then we call the basis $[a,b]$ a well-ordered basis.

Algorithm

Explanation

For the line-1 and line-2, we are trying to ensure

• lattice vector $a$ is the smaller one, i.e., $\parallel a\parallel \le \parallel b\parallel$
• both lattice vectors $a$ and $b$ are in the same direction, i.e., $\parallel a-b\parallel \le \parallel a+b\parallel$.

---

After then we will consider following cases :

1. For the line-3, it is the simplest case where $\parallel b\parallel \le min\{\parallel a+b\parallel ,\parallel a-b\parallel \}=\parallel a-b\parallel$, in this case, we must have :

   $$|\parallel a\parallel \le \parallel b\parallel \le \parallel a-b\parallel \le \parallel a+b\parallel$$

   then the basis $[a,b]$ is strictly reduced, and they are in the same direction, return $[a,b]$.

2. For the rest of lines, it is the case of $\parallel a-b\parallel <\parallel b\parallel$, there are two subcases to consider:

   • (2.1) for the line-4, $\parallel a\parallel \le \parallel a-b\parallel <\parallel b\parallel$, then basis $[a,b]$ is a typical well-ordered basis, and they are in the same direction.

   • (2.2) for line-5 and line-6, $\parallel a-b\parallel \le \parallel a\parallel \le \parallel b\parallel$, then there are two subcases to consider :

     • (2.2.1) for the line-5, $\parallel a-b\parallel \le \parallel a\parallel =\parallel b\parallel$, this is a very special case, $\parallel a\parallel =\parallel b\parallel$ and $\parallel a-b\parallel \le \parallel a\parallel$ ensure that vectors $a-b$ and $a$ are in the same direction, in this case, $\parallel a\parallel =\parallel b\parallel \le \parallel 2a-b\parallel$. Since $\parallel (a-b)-a\parallel =\parallel b\parallel$, thus the basis $[a-b,a]$ is reduced, and they are in the same direction, return $[a-b,a]$.

     • (2.2.2) from line-6, $\parallel a-b\parallel \le \parallel a\parallel <\parallel b\parallel$, we do not know the whether $a-b$ and $a$ are in the same direction or not, but $\parallel a\parallel \le \parallel b\parallel$ and $\parallel a-b\parallel \le \parallel a\parallel$ ensures that vectors $b-a$ and $a$ are in the same direction, so $\parallel b-a\parallel \le \parallel (b-a)-a\parallel \le \parallel a\parallel$. Therefore, the basis $[b-a,a]$ is well-ordered basis.

---

The remaining problem is how to find the reduced basis through well-ordered basis in the loop :

1. Since $[a,b]$ is a well-ordered basis, there are other lattice vectors that can be fit between $[\parallel a\parallel ,\parallel b\parallel ]$, what we need to do is finding the smallest one. This is achieved by find the integer $\mu$ such that $\parallel b-\mu a\parallel$ is minimal, then replace $b$ with $b-\mu a$.

2. Now we can check that if the updated basis $[a,b]$ is reduced, but before checking we need to make sure that $\parallel a\parallel \le \parallel b\parallel$, if not, swap $a$ and $b$.

3. repeat the above steps until the basis $[a,b]$ is reduced.

Next, we will focus on how to find the minimal vector between two well-ordered basis vectors in the Gauss loop.

Minimal Vector in Gauss Loop

Lemma 2.3 - Let $a,b$ be two vectors such that $\parallel b-a\parallel <\parallel b\parallel$. Then, one can efficiently find an integer $\mu$ such that $\parallel b-\mu a\parallel$ is minimal. Moreover, $\mu$ satisfies $1\le \mu \le \lceil 2\frac{\parallel b\parallel }{\parallel a\parallel }\rceil$.

Explanation

Note that, in Gauss algorithm, before entering the loop, we have ensured that the basis $[a,b]$ is well-ordered, i.e., $\parallel a\parallel \le \parallel b\parallel$ and $\parallel a\parallel \le \parallel a-b\parallel \le \parallel b\parallel$. But, this theorem does only mentioned last-half condition of well-ordered basis, i.e., $\parallel a-b\parallel \le \parallel b\parallel$. So this is a more general setting than the well-ordered basis condition.

---

For better understanding Gauss algorithm, we will specially consider the l2 norm, and explain why we are able to find the minimal vector between $a$ and $b$ in Gauss loop if $[a,b]$ is well-ordered with geometric intuition.

Condition $\parallel a\parallel \le \parallel a-b\parallel <\parallel b\parallel$ implies :

• vectors $a,b$ are in the same direction.
• projection scalar of $b$ onto $a$, i.e., $\frac{⟨a,b⟩}{\parallel a{\parallel }^2}>1/2$.
• the minimal distance between $b$ and $a$ is $\parallel b-\frac{⟨a,b⟩}{\parallel a{\parallel }^2}a\parallel$.

Two cases involved in finding the optimal integer $\mu$ are:

1. If $\frac{1}{2}<\frac{⟨a,b⟩}{\parallel a{\parallel }^2}\le 1$, then $\parallel b-\mu a\parallel ,u\in \mathbb{N}$ increases as $\mu$ moves away from the minimal value $\frac{⟨a,b⟩}{\parallel a{\parallel }^2}$. In this case, $\mu =1$ is the optimal integer choice.
2. If $\frac{⟨a,b⟩}{\parallel a{\parallel }^2}>1$, then $\parallel b-\mu a\parallel ,u\in \mathbb{N}$ increases in the range $[1,\frac{⟨a,b⟩}{\parallel a{\parallel }^2})$, and decreases in the range $(\frac{⟨a,b⟩}{\parallel a{\parallel }^2},\mathrm{\infty })$. In this case, the optimal integer choice must come from either $\lfloor \frac{⟨a,b⟩}{\parallel a{\parallel }^2}\rfloor$ or $\lceil \frac{⟨a,b⟩}{\parallel a{\parallel }^2}\rceil$.

---

Additionally, we will simply explain why $\frac{⟨a,b⟩}{\parallel a{\parallel }^2}>1/2$ in the contex of well-ordered basis with one diagraph below.

Why Gauss Loop Works

For now, we have only illustrated how Gauss loop works, and more specially how to find the minimal vector between two well-ordered basis vectors in the Gauss loop. But we have not touched why the loop works? or why we are able to eventually reach a reduced basis through repeated iterations from a well-ordered basis.

---

We know that the first step of Gauss loop is to find the minimal vector between the two basis vectors $a$ and $b$ which are well-ordered, i.e., $b^{\prime }=b-\mu a$, where $\mu$ is the integer that minimizes $\parallel b-\mu a\parallel$. Theoretically, the new vector $b^{\prime }$ could be :

1. $\parallel a\parallel \le \parallel b^{\prime }\parallel$,
2. $\parallel b^{\prime }\parallel <\parallel a\parallel$.

For the condition (1), since $\parallel b^{\prime }\parallel =\parallel b-\mu a\parallel$ is minimized, so :

• $\parallel b-\mu a\parallel \le \parallel b-(\mu -1)a\parallel$ implies $\parallel b^{\prime }\parallel \le \parallel b^{\prime }+a\parallel$
• $\parallel b-\mu a\parallel \le \parallel b-(\mu +1)a\parallel$ implies $\parallel b^{\prime }\parallel \le \parallel b^{\prime }-a\parallel$

Thus, if $\parallel a\parallel \le \parallel b^{\prime }\parallel$, then basis $[a,b^{\prime }]$ is already reduced. The Gauss loop will terminate for this pair of vectors.

For the condition (2), we know that step two of Gauss loop ensures that $b^{\prime }$ and $a$ are in the same direction by flipping the sign of the new vector $b^{\prime }$ if necessary, i.e., $\parallel b^{\prime }-a\parallel \le \parallel b^{\prime }+a\parallel$. Since $\parallel b^{\prime }\parallel <\parallel a\parallel$, we have $\parallel b^{\prime }-a\parallel \le \parallel a\parallel$, furthermore, $\parallel b^{\prime }\parallel \le \parallel b^{\prime }-a\parallel \le \parallel a\parallel$. Therefore, basis $[b^{\prime },a]$ is well-ordered.

Then the Gauss loop will continue with the new well-ordered basis $[b^{\prime },a]$, repeating the process until a reduced basis is obtained.

Running Time Analysis

By analysing the Gauss loop, we know that given input well-ordered basis $[b,c]$, we can obtain a new well-ordered basis $[a,b]$ unless the basis is already reduced. Note that, in one iteration vector $b$ not changed, only vector $a$ is invented. Then repeating the process more times will eventually lead to a reduced basis. So our concern is : is the number of iterations (time complexity) bounded by a polynomial of the input size $N$ (bits of one vector entry)? The answer is yes, but before our final conclusion, a lemma is needed.

---

Suppose the first input basis vector is $[a_{n-1},a_n]$, next input is $[a_{n-2},a_{n-1}]$, ..., till the last input is $[a_1,a_2]$, and $[a_1,a_2]$ is reduced.

Lemma 2.4 - For $i\ge 3$, $\parallel a_i\parallel \le 1/2\parallel a_{i+1}\parallel$.

Explanation

Let $[a,b,c]=[a_{i-1},a_i,a_{i+1}]$, given input well-ordered basis $[b,c]$ output another well-ordered basis $[a,b]$. Then we need to show the input lengths satisfy $\parallel b\parallel \le 1/2\parallel c\parallel$.

As we know, $a=\pm (c-\mu b)$ for some integer $\mu$ that minimizes $\parallel a\parallel$. We can consider it with following cases :

1. $\mu =1$
2. $\mu =2$
3. $2\le \mu$

We omit the details proof here.

---

Given the input basis $[a,b]$ of Gauss algorithm, and $[a_k,a_{k+1}]$ is the first well-ordered basis entering the Gauss loop, after $k$ iterations, we obtain the following inequality :

$$2^{k-2}\le 2^{k-2}\parallel a_3\parallel \le \parallel a_{k+1}\parallel \le \parallel a\parallel +\parallel b\parallel$$

Since before entering the Gauss loop, we may have swapping, negation, or substrating operations, but :

$$\parallel a_{k+1}\parallel \le \parallel a\parallel +\parallel b\parallel$$

always holds. It is clear that the number of iterations is bounded :

$$k\le {\log }_2(\parallel a\parallel +\parallel b\parallel )+2$$

If the number of bits of one vector entry is $N$, suppose there are $m$ entries in one vector, then :

$$\parallel a\parallel \le \sqrt{m\cdot (2^N\cdot 2^N)}=\sqrt{m}\cdot 2^N$$

So we have :

$$k\le (N+3)+{\log }_2\sqrt{m}$$

As $m$ is fixed, the term ${\log }_2\sqrt{m}$ is constant, so $k=O(N)$.

Approximating SVP in Dimension n

Approximating CVP in Dimension n