Now consider the general situation, let \(A=(a_{ij})_{m\times n}\). If \(m>n\), and \(\mathrm{rank}(A)\ge n\), then \(\mathscr {R}(A, c)\) defined by Eq. (7.5) is still a bounded region. Obviously if \(m<n\), or \(m=n\), \(\mathrm{rank}(A)<n\), then \(\mathscr {R}(A, c)\) is an unbounded region, and \(V=\infty \). Therefore, we have the following Corollary.

Property (i) can be derived from the boundedness of \(\mathscr {R}\), and property (ii) can be derived directly from the definition of \(\mathscr {R}(A, c)\). Later we will see that \(0\le F(x)<\infty \) holds for all \(x\in \mathbb {R}^n\). The main property of distance function F(x) is the following Lemma.

An important application of the above geometry of numbers is to solve the problem of rational approximation of real numbers, which is called Diophantine approximation in classical number theory. The main conclusion of this section is the following simultaneous rational approximation theorem of n real numbers.

Lattice is one of the most important concepts in modern cryptography. Most of the so-called anti-quantum computing attacks are lattice based cryptosystems. What is a lattice? In short, a lattice is a geometry in n-dimensional Euclidean space \(\mathbb {R}^n\), for example \(L=\mathbb {Z}^n\subset \mathbb {R}^n\), then \(\mathbb {Z}^n\) is a lattice in \(\mathbb {R}^n\), which is called an integer lattice or a trivial lattice. If \(\mathbb {Z}^n\) is rotated once, we get the concept of a general lattice in \(\mathbb {R}^n\), which is a geometric description of a lattice, next, we give an algebraic precise definition of a lattice.

In order to obtain a more explicit and concise mathematical expression of any lattice, we can regard an additive subgroup as a \(\mathbb {Z}\)-module. First, we prove that any lattice is a finitely generated \(\mathbb {Z}\)-module.

Lemma 7.12 is called the least square method in linear algebra, its significance is to find a vector \(x_0\) with the shortest length in the set \(\{Ax-b| x\in \mathbb {R}^m\}\) for a given \(n\times m\)-order matrix A and a given vector \(b\in \mathbb {R}^n\). Lemma 7.12 gives an effective algorithm, that is, to solve the linear equations \(A'Ax=A'b\), and \(x_0\) is the solution of the equations, Lemma 7.13 is called the diagonalization of quadratic form. Now, the main results are as follows:

It can be directly deduced from the above theorem

By Lemma 7.15, we immediately have the following corollary.

By definition, the basic neighborhood of a lattice is the representative element set of the additive quotient group \(\mathbb {R}^n/L\). Therefore, a basic neighborhood of any L forms an additive group under \({{\,\mathrm{mod}\,}}L\).

Equation (7.35) is usually called Hadamard inequality, and we give another proof here.

The following lemma is a useful lower bound estimate of the minimum distance \(\lambda _1\).

In Sect. 7.1, the geometry of numbers is relative to the integer lattice \(\mathbb {Z}^n\); next, we extend the main results to the general full rank lattice.

The above lemma shows that the upper bound (7.38) of \(\lambda _1\) is valid for \(\lambda _i\) in the sense of geometric average.

Finally, we discuss the computational difficulties on the lattice. These problems are the main scientific basis and technical support in the design of trap gate function, and they are also the cornerstone of the security of lattice cryptography.

In 1982, H. W. Lenstra, A. K. Lenstra and L. Lovasz creatively developed a set of algorithms in (1982) to effectively solve the approximation problem of the shortest vector, which is the famous LLL algorithm in lattice theory. The computational complexity of LLL algorithm is polynomial for the whole lattice, and the approximation coefficient \(r(n)=2^{\frac{n-1}{2}}\). How to improve the approximation coefficient in LLL algorithm to the polynomial coefficient of n is the main research topic at present. For example, Schnorr’s work in 1987 and Gama and Nguyen’s work (2008a, 2008b) are very representative, but they are still far from the polynomial function, so the academic circles generally speculate:

Conjecture 1: there is no polynomial algorithm that can approximate the shortest vector so that the approximation coefficient r(n) is a polynomial function of n.

There are many other difficult computational problems on lattice, such as the Successive Shortest vector problem, which is essentially to find a deterministic algorithm to approximate each \(\alpha _i\in L\), where \(|\alpha _i|=\lambda _i\) is the continuous minimum of L. However, SVP and CVP are commonly used in lattice cryptosystem design and analysis, and most of the research is based on the integer lattice.

It is easy to see from the definition that a lattice \(L=L(B)\) is an integer lattice \(\Leftrightarrow B \in \mathbb {Z}^{n\times n}\) is an integer square matrix, so the determinant \(d=d(L)\) of an entire lattice L is a positive integer.

The following lemma is a simple conclusion in algebra. For completeness, we prove the following.

The following lemma proves that a whole lattice has a unique HNF basis, so it is reasonable to use \(\mathrm{HNF}(L)\) to represent HNF basis.

Next, we discuss q-ary lattices, where \(q\ge 1\) is a positive integer, the following two q-ary lattices are often used in lattice cryptosystems.

Next, we discuss the transformation law of the corresponding orthogonal basis when making the elementary column transformation of the base matrix \([\beta _{1},\beta _{2} ,\ldots ,\beta _{n}]\).

Next, we introduce the concept of a set of Reduced bases of \(\mathbb {R}^{n}\).

Another important conclusion of this section is that for the integer lattice L estimation, the computational complexity of the Reduced basis of the integer lattice is obtained by using the LLL algorithm. We prove that the LLL algorithm on the integer lattice is polynomial.

The most important application of lattice Reduced basis and LLL algorithm is to provide approximation algorithms for the shortest vector problem and the shortest adjacent vector problem, and obtain some approximate results. Firstly, we prove the following Lemma.

The following theorem shows that if \(\{\beta _{1},\beta _{2},\ldots , \beta _{n} \}\) is a set of Reduced bases of a lattice L, then \(\beta _{1}\) is the approximation vector of the shortest vector \(u_{0}\) of lattice L, and the approximation coefficient \(r_n=2^{n-1}\).

The following results show that not only the shortest vector, the whole Reduced basis vector is the approximation vector of the Successive Shortest vector of the lattice.

Let \(U=\sum _{i=1}^{n-1}\mathbb {R}\beta _{i}=L(\beta _{1},\beta _{2},\ldots , \beta _{n-1})\subset \mathbb {R}^{n}\) be an \(n-1\)-dimensional subspace, \(L^{'}=\sum _{i=1}^{n}\mathbb {Z}\beta _{i}\subset L\) be a sublattice of L, and \(v \in L\), call \(U+v\) is an affine plane of \(\mathbb {R}^{n}\). When \(x \in \mathbb {R}^{n}\) given, if the distance between x and \(U+v\) is the smallest, \(U+v\) is called the nearest affine plane of x.

Let \(x^{'}\) be the orthogonal projection of x in the nearest affine plane \(U+v\), let \(y\in L^{'}\) be the vector closest to \(x-v\) in \(L^{'}\), and let \(w=y+v\) be the approximation of the vector closest to x in L.

Comparing Theorems 7.6 and 7.7, when \(x=0\), the approximation coefficient of Theorem 7.6 is \(2^{\frac{n-1}{2}}\), for general \(x\in \mathbb {R}^{n}\), there is an additional factor \(\sqrt{2}\) in the approximation coefficient. Using the rounding off technique, we can give an approximation to adjacent vectors, another main result in this section is

By Theorem 7.8, \([x]_{B}\in L\) is an approximation of the nearest lattice point \(u_{x}\), and the approximation coefficient is \(\gamma _{1}(n)=1+2n\left( \frac{9}{2}\right) ^{\frac{n}{2}}\), it is a little worse than the approximation coefficients generated by adjacent planes, but the approximation vector is relatively simple. In lattice cryptosystem, \([x]_{B}\) as input information has higher efficiency. To prove Theorem 7.8, we need the following Lemma.

Now we give the proof of 7.8:

Lattice-based cryptosystem is the main research object of postquantum cryptography. Since it was first proposed in 1996, it has only a history of more than 20 years. Among them, the representative technologies are Ajtai-Dwork cryptosystem, GGH cryptosystem, McEliece-Niederreiter cryptosystem and NTRU cryptosystem based on algebraic code theory. We will introduce them, respectively, below.

GGH cryptosystem is a cryptosystem based on lattice theory proposed by Goldreich, Goldwasser and Halevi in 1997. It is generally considered that it is a new public key cryptosystem to replace RSA in the postquantum cryptosystem era.

Comparing GGH with GGH/HNF, they choose the same encryption function, but the decryption transformation is very different. GGH adopts Babai’s rounding off method, while GGH/HNF adopts Babai’s nearest plane method. There is a certain difference between the two at the selection point of error vector e. The error vector e of GGH depends on each component of parameter \(\sigma \) and e, and \(\pm \sigma \). The error vector e of GGH/HNF depends on the parameter \(\rho \) as long as the length is less than \(\rho \). Therefore, GGH/HNF has greater flexibility in the selection of error vector e.

NTRU cryptosystem is a new public key cryptosystem proposed in 1996 by the number theory research unit (NTRU) composed of three digit theorists J. Hoffstein, J. Piper and J. Silverman of Brown University in the USA. Its main feature is that the key generation is very simple, and the encryption and decryption algorithms are much faster than the commonly used RSA and elliptic curve cryptography, NTRU, in particular, can resist quantum computing attacks and is considered to be a potential public key cryptography that can replace RSA in the postquantum cryptography era.

The essence of NTRU cryptographic design is the generalization of RSA on polynomials, so it is called the cryptosystem based on polynomial rings. However, NTRU can give a completely equivalent form by using the concept of q-ary lattice, so NTRU is also a lattice based cryptosystem. For simplicity, we start with polynomial rings.

Next, we give an equivalent characterization of cyclic matrix.

The following lemma characterizes the main properties of cyclic matrices.

With the above preparation, we now introduce the equivalent form of NTRU in lattice theory.

To sum up, when NTRU cryptosystem satisfies the additional restrictions (A)–(D) on the parameter system, the private key is \( \left[ \begin{array}{cccc} f \\ g \\ \end{array}\right] \) and the public key is HNF matrix H, the encryption and decryption algorithm can be based on the algorithm introduced above.

A cyclic code C corresponds to an ideal \(C(x)=\langle g(x) \rangle {{\,\mathrm{mod}\,}}x^{N}-1\) in R, we define

If \(g(x)=x^{N}-1\), then \(\langle x^{N}-1\rangle {{\,\mathrm{mod}\,}}x^{N}-1=0\), corresponding to zero ideal in R. Thus, the corresponding cyclic code \(C=\{0=00\cdots 0\}\) is called zero code. If \(g(x)=1\), then \( \langle g(x)\rangle {{\,\mathrm{mod}\,}}x^{N}-1=R\). The corresponding code \(C=\mathbb {F}_{q}^{N}\). Therefore, there are always two trivial cyclic codes in cyclic codes of length N, zero code and \(\mathbb {F}_{q}^{N}\), which correspond to zero ideal in R and R itself, respectively.

Next, we discuss the dual code of cyclic code and its check matrix.

Minimal cyclic codes are also called irreducible cyclic codes because they no longer contain the nontrivial cyclic codes of \(\mathbb {F}_{q}^{N}\) in \(M_{i}^{-}\). The irreducibility of minimal cyclic codes can be derived from the fact that the ideal \(M_{i}^{-}(x)\) in R corresponding to \(M_{i}^{-}\) is a field. We can give a proof of pure algebra.

In 1959, A. Hocquenghem and 1960, R. Bose and D. Chaudhuri independently proposed a special class of cyclic codes, which required minimal distance. At present, it is generally called BCH codes in academic circles.

Now, we can introduce the design principle of McEliece/Niederreiter cryptosystem. Its basic mathematical idea is based on the decoding principle of error correction code. Recall the concept of error correction code in Chap. 2, a code \(C\subset \mathbb {F}_{q}^{N}\) is called t-error correction code (\(t\ge 1\) is a positive integer). If for \(\forall ~ y\in \mathbb {F}_{q}^{N}\), there is at most one codeword \(c\in C\Rightarrow d(c,y)\le t, d(c,y)\) is the Hamming distance between c and y. We know that if the minimum distance of a code C is d, then C is a t-error correction code, where \(t=\left\lceil \frac{d-1}{2} \right\rceil \) is the smallest integer not less than \(\frac{d-1}{2}\). Lemma 7.60 proves the existence of t-error correction codes for any positive integer t, i.e., \(2t+1\)-BCH code \((\delta =2t+1)\), this kind of code is called Goppa code (see the next section), which provides a theoretical basis for McEliece/Niederreiter cryptosystem. Next, we will introduce the working mechanism of this kind of cryptosystem in detail. First, let’s look at the generation of key.

Private key: Select a t-error correction code \(C\subset \mathbb {F}_{q}^{N},C=[N,k]\), H is the check matrix of C, H is an \((N-k)\times N\)-dimensional matrix. For \(\forall ~x\in \mathbb {F}_{q}^{N}, x\rightarrow xH'\in \mathbb {F}_{q}^{N-k}\) is a correspondence of Spaces \(\mathbb {F}_{q}^{N}\) to \(\mathbb {F}_{q}^{N-k}\), let’s prove that this correspondence is a single shot on a special codeword whose weight is not greater than t.

We use t-error correction code C and check matrix H as the private key.

In order to obtain the anti-collision Hash function, the selection of \(n\times m\)-order matrix A is very important. First, we can select the parameter system: let \(d=2\), \(q=n^2\), n|m, and \(m\log 2>n \log q\), where n is a positive integer. In Ajtai/Dwork cryptographic algorithm, there are two choices of parameter matrix A, one is cyclic matrix and the other is more general ideal matrix. Their corresponding q-element lattice \(\Lambda _q^{\bot }(A)\) are cyclic lattice and ideal lattice, respectively.

Cyclic lattice

Algorithm 1: Hash function based on cyclic lattice.

Parameter: q, n, m, d is a positive integer, \(n \mid m, m \log d >n \log q\).

Secret key: \(\frac{m}{n}\) column vectors \(\alpha ^{(i)}\in \mathbb {Z}_{q}^{n}, 1 \le i \le \frac{m}{n}\).

Ideal matrix is a more general generalization of cyclic matrix. The former corresponds to a first n-degree polynomial h(x), and the latter corresponds to a special polynomial \(x^n-1\). We first prove that the ideal matrix \(T_{h}^{*}(g)\) and the rotation matrix \(T_{h}\) generated by any vector \(g\in \mathbb {Z}^{n}\) are commutative under matrix multiplication.

When the monic n-degree integer coefficient polynomial h is selected, we want to establish the corresponding relationship between the ideal and the integer lattice \(L\subset \mathbb {Z}^{n}\) in the quotient ring \(R=\mathbb {Z}[x]/\langle h(x)\rangle \). First, we define the concept of an ideal lattice. In short, an ideal lattice is an integer lattice generated by the ideal matrix.

Our main result is the 1-1 correspondence between ideal and ideal lattice in \(R=\mathbb {Z}[x]/\langle h(x) \rangle \). This also explains the reason why \(L(T_{h}^{*}(g))\) is called ideal lattice.

The above discussion on ideal matrix and ideal lattice can be extended to a finite field \(\mathbb {Z}_{q}\), because any quotient ring \(\mathbb {Z}_{q}[x]/\langle h(x)\rangle \) on polynomial ring \(\mathbb {Z}_{q}[x]\) in finite field is a principal ideal ring. Therefore, we can establish the 1-1 correspondence between all ideals in \(R=\mathbb {Z}_{q}[x]/\langle h(x)\rangle \) and linear codes on \(\mathbb {Z}_{q}\).

Algorithm 2: Hash function based on ideal lattice.

Parameter: q, n, m, d are positive integers, n|m, \(m\log d>n \log q\).

Secret key: \(\frac{m}{n}\) column vectors \(g^{(i)}\in \mathbb {Z}_{q}^{n}(1\le i \le \frac{m}{n})\), polynomial \(h(x)=x^n+a_{n-1}x^{n-1}+\cdots +a_{1}x+a_{0}\in \mathbb {Z}_{q}[x]\).

We will not introduce the anti-collision performance of hash functions constructed by cyclic lattices and ideal lattices here. Interested students can refer to the reference Micciancio and Regev (2009) in this chapter.