Introduction to Cryptography with Coding Theory, 3rd Edition

23.1 Lattices

Let $v_1\text{,}\dots \text{,}{v}_n$ be linearly independent vectors in $n$-dimensional real space ${\mathbf{R}}^n$. This means that every $n$-dimensional real vector $v$ can be written in the form

$$v=a_1{v}_1+\cdots +a_n{v}_n$$

with real numbers $a_1\text{,}\dots \text{,}{a}_n$ that are uniquely determined by $v$. The lattice generated by $v_1\text{,}\dots \text{,}{v}_n$ is the set of vectors of the form

$$m_1{v}_1+\cdots +m_n{v}_n$$

where $m_1\text{,}\dots \text{,}{m}_n$ are integers. The set $\{v_1\text{,}\dots \text{,}{v}_n\}$ is called a basis of the lattice. A lattice has infinitely many possible bases. For example, suppose $\{v_1\text{,}{v}_2\}$ is a basis of a lattice. Let $k$ be an integer and let $w_1=v_1+k{v}_2$ and $w_2=v_2$. Then $\{w_1\text{,}{w}_2\}$ is also a basis of the lattice: Any vector of the form $m_1{v}_1+m_2{v}_2$ can be written as $m_1^{\prime }{w}_1+m_2^{\prime }{w}_2$ with ${m_1}^{\prime }=m_1$ and $m_2^{\prime }=m_2-k{m}_1$, and similarly any integer linear combination of $w_1$ and ...