# Learning with Errors: A Lattice-Based Keystone of Post-Quantum Cryptography
## 3 Lattices  
### Basic Definitions  
Although lattices have been studied for centuries, mostly because of their associations with quadratic forms and algebraic number theory, interest in their algorithmic aspect began in the 1980's and since then has become a well-thought-out and crucial tool in the science of cryptology. An \(n\)-dimensional lattice \(\mathcal{L}\) can be viewed as an additive, discrete subgroup of \(\mathbb{R}^{n}\) possessing a periodic structure. There are certain lattices with particular significance, like the integer lattice, which is a subgroup of \(\mathbb{Z}^{n}\), or the scaled lattice \(a\mathcal{L}\) for a real number \(a\) and a lattice \(\mathcal{L}\). Each lattice is generated and described by a set of linearly independent vectors, its basis. **Definition 8**. : _A set of vectors \(\{b_{1},b_{2},\ldots,b_{m}\}\in\mathbb{R}^{n}\) is linearly independent if the equation_  
\[\lambda_{1}b_{1}+\lambda_{2}b_{2}+\cdots+\lambda b_{m}=0,\quad\text{where} \quad\lambda_{i}\in\mathbb{R}\]  
_accepts only the trivial solution \(\lambda_{1}=\lambda_{2}=\cdots=\lambda_{m}=0\)._  
**Definition 9**. : _Given \(n\) linearly independent vectors \(b_{1},b_{2},\ldots,b_{m}\in\mathbb{R}^{n}\), the lattice generated by them is defined as the set_  
\[\mathcal{L}(b_{1},b_{2},\ldots,b_{m})=\ \{\sum_{i}x_{i}b_{i}:x_{i}\in\mathbb{Z}, \quad 1\leq i\leq n\}\]  
The set of the vectors \(\{b_{1},b_{2},\ldots,b_{m}\}\) is called a basis of the lattice \(\mathcal{L}\). Let \(\mathcal{B}\) denote the \(n\times m\) matrix with columns \(b_{1},b_{2},\ldots,b_{m}\), then a lattice can be written as  
\[\mathcal{L}(B)=\mathcal{L}(b_{1},b_{2},\ldots,b_{m})=\ \{Bx|x\in\mathbb{Z}^{n}\}\]  
where \(Bx\) is the usual matrix-vector multiplication. **Definition 10**. : _The same number, \(dim\mathcal{L}\), of elements of all the bases of a lattice \(\mathcal{L}\) is called the rank of the lattice since it matches the dimension of the vector subspace spanned by \(\mathcal{L}\)._  
We call \(m\) the rank of the lattice and \(n\) the dimension. If \(n=m\), the lattice \(\mathcal{L}\) is called a full-rank lattice. A lattice \(\mathcal{L}\) can be generated by different bases; for example, \(\mathbb{Z}^{2}\) has as its basis the vectors \(b_{1}=(1,0)^{T},b_{2}=(0,1)^{T}\) but also the vectors \(b_{1}=(1,1)^{T},b_{2}=(2,1)^{T}\). A lattice generated by two different bases is demonstrated in Figure 1.  
This is generalized with the help of the unimodular matrix. Figure 1: Different bases of a lattice. **Definition 11**. : _A matrix \(U\in\mathbb{Z}^{n\times n}\) is called unimodular if det \(U=\pm 1\)._  
**Theorem 1**. : _For a basis \(B\) of a lattice \(\mathcal{L}\) and any unimodular matrix \(U\in\mathbb{Z}^{n\times n}\), \(B\cdot U\) is also a basis of \(\mathcal{L}(B)\) due to the fact that \(U\cdot\mathbb{Z}^{n}=\mathbb{Z}^{n}\)._  
Besides that fact, \(n\) independent linear vectors are not necessarily a basis of \(\mathbb{R}^{n}\) or \(\mathbb{Z}^{n}\); for example, \((2,0)^{T}\) and \((1,1)^{T}\) are not a basis of \(\mathbb{Z}^{2}\). **Definition 12**. : _Let \(\mathcal{L}\) be a lattice with dimension \(n\) and \(B=\{b_{1},b_{2},\ldots,b_{n}\}\) a basis of the lattice. We define the fundamental parallelepiped of \(\mathcal{L}\) to be the set_  
\[\mathcal{P}(\mathcal{B})=\{Bx|x\in\mathbb{R}^{n},\,\forall i:0\leq x_{i}<1\}.\]  
**Definition 13**. : _Let \(\mathcal{L}=\mathcal{L}(\mathcal{B})\) be a lattice of rank \(n\) and \(B\) a basis of \(\mathcal{L}\). The determinant of \(\mathcal{L}\) denoted by det\((\mathcal{L})\) is the \(n\)-dimensional volume of \(\mathcal{P}(\mathcal{B})\)._  
The determinant can be written as  
\[\text{det}(\mathcal{L}(\mathcal{B}))=\text{vol}(\mathcal{P})\quad\text{and also}\quad\text{det}(\mathcal{L})=\sqrt{\text{det}(B^{T}B)}.\]  
**Definition 14**.