$$T e\_k = e\_{k+1}, \text{ and } T^k(e\_0) = e\_k, \ 0 \le k \le n-1. \tag{3.1.3}$$

**Definition 3.1.1** Let α = ⎛ ⎜ ⎝ α0 . . . α*n*−1 ⎞ ⎟ ⎠ ∈ R*n*, the circulant matrix *T* ∗(α) generated by

α is defined by

$$T^\*(\alpha) = [\alpha, T\alpha, \dots, T^{n-1}\alpha]\_{n \times n} \in \mathbb{R}^{n \times n}.\tag{3.1.4}$$

It is easy to verify that the circulant matrix *B* generated by the linear combination vector is the linear combination of the corresponding circulant matrices, i.e.

$$T^\*(a\alpha + b\beta) = aT^\*(\alpha) + bT^\*(\beta). \tag{3.1.5}$$

Specially, for any α = ⎛ ⎜ ⎝ α0 . . . α*n*−1 ⎞ ⎟ ⎠ ∈ R*n*, the circulant matrix *T* ∗(α) generated by α

could be written as

$$T^\*(\alpha) = T^\*\left(\sum\_{i=0}^{n-1} \alpha\_i e\_i\right) = \sum\_{i=0}^{n-1} \alpha\_i T^\*(e\_i),\tag{3.1.6}$$

therefore, any circulant matrix is the linear combination of circulant matrices generated by the standard basis vectors *ei* . It is easy to verify that

$$T^\*(e\_k) = T^k, \ 0 \le k \le n - 1. \tag{3.1.7}$$

In particular, the unit matrix *In* is a circulant matrix generated by the vector *e*0. The basis properties about the circulant matrix are summarized in the following lemma, and the corresponding proofs could be found in Sect. 7.7 in Zheng (2022).

$$\textbf{Lemma 3.1.1 }\text{ Let } \alpha = \begin{pmatrix} \alpha\_0 \\ \alpha\_1 \\ \vdots \\ \alpha\_{n-1} \end{pmatrix}, \beta = \begin{pmatrix} \beta\_0 \\ \beta\_1 \\ \vdots \\ \beta\_{n-1} \end{pmatrix} \text{ be two vectors in } \mathbb{R}^n, \text{ then we have}$$

We take the characteristic polynomial *x n* − 1 as modulo and construct the one-toone correspondence between polynomial quotient rings and *n* dimensional vectors, which is called the geometric theory of polynomial rings. We consider the following three polynomial quotient rings. Let R[*x*], Z[*x*] and Z*q* [*x*] be the polynomial rings of one variable on R, Z and Z*q* respectively, defined by

$$\overline{R} = \mathbb{R}[\mathbf{x}]/<\mathbf{x}^n - 1> = \left\{ \sum\_{i=0}^{n-1} a\_i \mathbf{x}^i \mid a\_i \in \mathbb{R} \right\},\tag{3.1.8}$$

$$R = \mathbb{Z}[\mathbf{x}]/<\mathbf{x}^n - 1> = \left\{ \sum\_{i=0}^{n-1} a\_i \mathbf{x}^i \mid a\_i \in \mathbb{Z} \right\},\tag{3.1.9}$$

and

$$R\_q = \mathbb{Z}\_q[\mathbf{x}]/<\mathbf{x}"-1> = \left\{ \sum\_{i=0}^{n-1} a\_i \mathbf{x}^i \mid a\_i \in \mathbb{Z}\_q \right\}.\tag{3.1.10}$$

In fact, the right hand side of the above formula is a set of representative elements of the polynomial quotient ring.

For any α(*x*) = α0 + α1*x* +···+ α*n*−1*x n*−1 ∈ *R*, we construct the following correspondence

$$\alpha(\mathbf{x}) = \alpha\_0 + \alpha\_1 \mathbf{x} + \dots + \alpha\_{n-1} \mathbf{x}^{n-1} \in \overline{R} \longleftrightarrow \alpha = \begin{pmatrix} \alpha\_0 \\ \alpha\_1 \\ \vdots \\ \alpha\_{n-1} \end{pmatrix} \in \mathbb{R}^n,\tag{3.1.11}$$

written as α(*x*) ←→ α or α ←→ α(*x*). Then (3.1.11) gives a one-to-one correspondence between *R* and R*n*. In the same way, α(*x*) ←→ α also gives the one-to-one correspondences of *R* → Z*n* and *Rq* → Z*n q* . It is not hard to see that the above correspondence is an Abel group isomorphism. To establish ring isomorphism, we introduce the concept of convolution multiplication of vectors.

**Definition 3.1.2** For any two vectors α, β in R*n*, Z*n* or Z*n q* , we define the convolution α ⊗ β by

$$
\alpha \otimes \beta = T^\*(\alpha) \cdot \beta. \tag{3.1.12}
$$

Under the above definition, R*n*, Z*n* and Z*n q* become a commutative ring with unit element, respectively. Obviously, the convolution defined by (3.1.12) is closed on Z*n* or Z*n q* . If α ∈ Z*n*, then *T* ∗(α) ∈ Z*n*×*n*, thus, α ⊗ β = *T* ∗(α)β ∈ Z*n*, so is Z*n q* . Based on the property (iii) of lemma 3.1.1,

$$T^\*(\alpha \otimes \beta) = T^\*(T^\*(\alpha)\beta) = T^\*(\alpha)T^\*(\beta) = T^\*(\beta)T^\*(\alpha) = T^\*(\beta \otimes \alpha),$$

so we have α ⊗ β = β ⊗ α. On the other hand,

$$(\alpha + \alpha') \otimes \beta = T^\*(\alpha + \alpha')\beta = T^\*(\alpha)\beta + T^\*(\alpha')\beta = \alpha \otimes \beta + \alpha' \otimes \beta,$$

hence, R*n*, Z*n* and Z*n q* are commutative rings with the same unit element *e*0. Since *T* ∗(*e*0) = *In*, then

$$e\_0 \otimes \beta = T^\*(e\_0)\beta = I\_n\beta = \beta.$$

**Lemma 3.1.2** *Suppose R, R and Rq are defined by (3.1.8), (3.1.9) and (3.1.10), then we have the following three ring isomorphisms:*

$$
\overline{\mathcal{R}} \cong \mathbb{R}^n, \; \mathcal{R} \cong \mathbb{Z}^n \; \text{and} \; \mathcal{R}\_q \cong \mathbb{Z}\_q^n.
$$

*Proof* We only prove *R* ∼= R*n*, the other two conclusions could be proved in the same way. ∀α(*x*) ∈ *R*, α(*x*) ←→ α ∈ R*n* is a one-to-one correspondence and an Abel group isomorphism. We are to prove

$$
\alpha(\mathbf{x})\beta(\mathbf{x}) \longleftrightarrow \alpha \otimes \beta,\ \forall \alpha(\mathbf{x}), \beta(\mathbf{x}) \in \overline{R}.\tag{3.1.13}
$$

Let β(*x*) = β0 + β1*x* +···+ β*n*−1*x n*−1, then

$$\begin{aligned} \alpha \boldsymbol{\beta}(\mathbf{x}) &= \beta\_0 \mathbf{x} + \beta\_1 \mathbf{x}^2 + \dots + \beta\_{n-2} \mathbf{x}^{n-1} + \beta\_{n-1} \mathbf{x}^n, \\ &= \beta\_{n-1} + \beta\_0 \mathbf{x} + \dots + \beta\_{n-2} \mathbf{x}^{n-1}, \end{aligned}$$

so *x*β(*x*) ←→ *T*β. For all *k*, 0 *k n* − 1, we know

$$x^k \beta(x) \longleftrightarrow T^k \beta.$$

Let α(*x*) = α0 + α1*x* +···+ α*n*−1*x n*−1, it follows that

$$\alpha(\alpha)\beta(\alpha) = \sum\_{k=0}^{n-1} \alpha\_k \pi^k \beta(\alpha) \longleftrightarrow \sum\_{k=0}^{n-1} \alpha\_k T^k \beta = T^\*(\alpha)\beta = \alpha \otimes \beta.$$

Therefore, we prove that *R* ∼= R*n*. Similarly, we have *R* ∼= Z*n* and *Rq* ∼= Z*n q* .

Since R*n* is Euclidean space, the Euclidean distances in Z*n* and Z*n q* could also be defined as the Euclidean distance in R*n*, which is called the embedding of Euclidean distance in Z*n* and Z*n q* . By Lemma 3.1.2, we treat *R*, *R*, *Rq* and R*n*, Z*n*, Z*n q* as the same and write *R* = R*n*, *R* = Z*n*, *Rq* = Z*n q* . Therefore, the polynomial rings *R*, *R* and *Rq* also have Euclidean distance, which constructs the geometry of the polynomial ring. For any polynomial α(*x*) ∈ *R*, we define

$$|\alpha(\mathbf{x})| = |\alpha|, \text{ if } \alpha(\mathbf{x}) \longleftrightarrow \alpha. \tag{3.1.14}$$

**Lemma 3.1.3** *For any* α(*x*)*,* β(*x*) ∈ *R (or R, Rq ), we have*

$$|\alpha(\mathbf{x})\beta(\mathbf{x})| \lesssim \sqrt{n}|\alpha(\mathbf{x})| \cdot |\beta(\mathbf{x})|.$$

*Proof* To prove this lemma, we only prove that for any α, β ∈ R*n* (the same as Z*n* or Z*n q* ), we have

$$|\alpha \otimes \beta| \leqslant \sqrt{n}|\alpha| \cdot |\beta|. \tag{3.1.15}$$

By Definition 3.1.2,

$$\alpha \otimes \beta = T^\*(\alpha)\beta = [\alpha, T\alpha, \dots, T^{n-1}\alpha]\beta = \begin{pmatrix} b\_1 \\ b\_2 \\ \vdots \\ b\_n \end{pmatrix} \in \mathbb{R}^n.$$

Let α be the conjugation vector of α, i.e.

$$
\alpha = \begin{pmatrix} \alpha\_0 \\ \alpha\_1 \\ \vdots \\ \alpha\_{n-1} \end{pmatrix} \Rightarrow \overline{\alpha} = \begin{pmatrix} \alpha\_{n-1} \\ \alpha\_{n-2} \\ \vdots \\ \alpha\_0 \end{pmatrix},
$$

then, the circulant matrix *T* ∗(α) generated by α can be divided into rows

$$T^\*(\alpha) = \begin{pmatrix} \overline{\alpha}^T T^T \\ \overline{\alpha}^T (T^T)^2 \\ \vdots \\ \overline{\alpha}^T (T^T)^n \end{pmatrix},$$

where *T T* is the transposed matrix of *T* . So *bi* = α*T* (*T T* )*i* β (1 *i n*) and we get

$$|b\_i| \lesssim |\alpha| \cdot |\beta|, \ 1 \leqslant i \leqslant n.$$

It follows that

$$|\alpha \otimes \beta| = \left(\sum\_{i=1}^n b\_i^2\right)^{\frac{1}{2}} \le \sqrt{n}|\alpha| \cdot |\beta|.$$

We complete the proof.

Finally we discuss the relation between circulant matrix and lattice. Let *B* ∈ R*n*×*n* be a square matrix of order *n*, the lattice *L*(*B*) ⊂ R*n* generated by *B* is defined by

$$L(B) = \{ Bx \mid x \in \mathbb{Z}^n \}.$$

If *B* is an invertible matrix, then *L*(*B*) is called an *n* dimensional full rank lattice.

**Definition 3.1.3** Let *L*(*B*) ⊂ R*n* be a lattice, we call *L*(*B*) a cyclic lattice, if *L*(*B*)is closed under the linear transformation *T* , i.e. for any α ∈ *L*(*B*) we have *T* α ∈ *L*(*B*). If *L*(*B*) ⊂ Z*n* is a cyclic lattice, then *L*(*B*) is called a cyclic integer lattice.

**Lemma 3.1.4** *Let* α ∈ R*n, then the lattice L*(*T* ∗(α)) *generated by the circulant matrix T* ∗(α) *is a cyclic lattice, which is the smallest cyclic lattice containing* α*.*

*Proof* Based on the definition *T* ∗(α) = [α, *T* α, . . . , *T n*−1α], we get

$$L(T^\*(\alpha)) = \left\{ \sum\_{i=0}^{n-1} a\_i \, T^i \alpha \mid a\_i \in \mathbb{Z} \right\}.$$

For any β ∈ *L*(*T* ∗(α)),

$$\beta = \sum\_{i=0}^{n-1} b\_i T^i \alpha \Rightarrow T\beta \in L(T^\*(\alpha)), \ b\_i \in \mathbb{Z},$$

so *L*(*T* ∗(α))is a cyclic lattice. Assume *L* is a cyclic lattice containing α, since α ∈ *L*, *T* α ∈ *L*,..., *T n*−1α ∈ *L*, then any linear combination of integer coefficients

$$\sum\_{i=0}^{n-1} a\_i T^i \alpha \in L \Rightarrow L(T^\*(\alpha)) \subset L.$$

This means that *L*(*T* ∗(α)) is the smallest cyclic lattice containing α.

**Lemma 3.1.5** *Let L*(*B*) ⊂ R*n be a cyclic lattice,* α ∈ *L*(*B*) *be a lattice vector, then there is an integer matrix D* ∈ Z*n*×*n such that*

$$T^\*(\alpha) = BD.\tag{3.1.16}$$

*Proof* Since α ∈ *L*(*B*), *L*(*B*) is a cyclic lattice, then *T* α ∈ *L*(*B*), *T* 2α ∈ *L*(*B*), . . . , *T n*−1α ∈ *L*(*B*). Let (0 *k n* − 1)

$$T^k \alpha = Bd\_k, \ d\_k \in \mathbb{Z}^n, \ D = [d\_0, d\_1, \dots, d\_{n-1}]\_{n \times n} \in \mathbb{Z}^{n \times n},$$

the circulant matrix *T* ∗(α) generated by α could be written as

$$T^\*(\alpha) = [\alpha, T\alpha, \dots, T^{n-1}\alpha] = [Bd\_0, Bd\_1, \dots, Bd\_{n-1}] = BD.$$

Lemma 3.1.5 holds.

Let *L* ⊂ R*n* be a lattice, for any *x* ∈ R*n*, there exists *ux* ∈ *L* ⇒

$$|\mathbf{x} - \boldsymbol{u}\_{\mathbf{x}}| = \min\_{\boldsymbol{\alpha} \in L, \boldsymbol{\alpha} \neq \mathbf{x}} |\boldsymbol{\alpha} - \boldsymbol{x}| = |\mathbf{x} - L|. \tag{3.1.17}$$

*ux* is called the nearest lattice vector of *x*. We define the covering radius ρ(*L*) of *L* by

$$\rho(L) = \max\_{x \in \mathbb{R}^n} |x - \mu\_x| = \max\_{x \in \mathbb{R}^n} |x - L|. \tag{3.1.18}$$

Obviously, the covering radius ρ(*L*) satisfies that any sphere *N*(*x*,ρ(*L*)) with radius ρ(*L*) contains at least one lattice vector. If *L*1 ⊂ *L* is a sublattice, then for any *x* ∈ R*n*,

$$|\mathbf{x} - L| \lessapprox |\mathbf{x} - L\_1| \Rightarrow \rho(L) \lessapprox \rho(L\_1). \tag{3.1.19}$$

If *L* = *L*(*B*), we write ρ(*L*) = ρ(*B*). The final goal of this section is to prove the existence of the covering radius and give an upper bound estimate of ρ(*L*) using Babai's nearest plane algorithm.

Let *L* = *L*(*B*), *S* = {*s*1,*s*2,...,*sn*} ⊂ *L* be *n* linearly independent lattice vectors. *S*∗ = {*s*∗ 1 ,*s*∗ 2 ,...,*s*∗ *n* } is the orthogonal basis corresponding to *S* by the Gram-Schmidt method. We define

$$\sigma(S) = \left(\sum\_{i=1}^{n} |s\_i^\*|^2\right)^{\frac{1}{2}}.\tag{3.1.20}$$

**Lemma 3.1.6** *(Babai) Let L* = *L*(*B*) ⊂ R*n be a full rank lattice, S* ⊂ *L be the set of n linearly independent lattice vectors, then for any t* ∈ R*n, there exists a lattice vector* w ∈ *L* ⇒

$$|t - w| \leqslant \frac{1}{2}\sigma(\mathbb{S}).\tag{3.1.21}$$

*Specially, the covering radius* ρ(*L*) *of L exists and satisfies* ρ(*L*) - 1 2σ (*S*)*.*

*Proof* Without loss of generality, we only prove for the case *S* = *B*. Since *L*(*S*) ⊂ *L*(*B*) is a full rank sublattice, by (3.1.21) w ∈ *L*(*S*) ⇒ w ∈ *L*(*B*) and ρ(*L*) - ρ(*S*) - 1 2σ (*S*). Let *B* = [β1, β2,...,β*n*], the corresponding orthogonal basis is *B*∗ = [β∗ 1 , β∗ 2 ,...,β∗ *n* ]. Babai's algorithm is based on the following two techniques:

(1) Rounding off (see Theorem 7 of Chap. 7 in Zheng (2022))

∀*x* ∈ R*n*, let *x* = *n i*=1 *xi*β∗ *i* , where *xi* ∈ R. Define δ*i* ∈ Z is the nearest integer of *xi* , and

$$\{x\}\_B = \sum\_{i=1}^n \delta\_i \beta\_i^\*, \ \{x\}\_B = \sum\_{i=1}^n a\_i \beta\_i^\*, \ -\frac{1}{2} < a\_i \leqslant \frac{1}{2}, \ 1 \leqslant i \leqslant n.$$

It is easy to see *x* = [*x*]*B* + {*x*}*B*, where [*x*]*B* ∈ *L* is a lattice vector.

#### (2) Nearest plane

Let *U* = *L*(β1, β2,...,β*n*−1) ⊂ R*n* be an *n* − 1 dimensional subspace,

$$L' = \sum\_{i=1}^{n-1} \mathbb{Z}\beta\_i \subset L \text{ is a sublattice of } L.$$

After *x* ∈ R*n* is given, let v ∈ *L*, such that *U* + v is the nearest plane of *x*. Let *x* be the orthographic projection of *x* in *U* + v, *y* ∈ *L* be the nearest lattice vector of *x* − v, w = *y* + v be an approximation of the nearest lattice vector of *x* in *L*. Based on the above definitions, we can prove that (see (7.82) of Chap. 7 in Zheng (2022))

$$\begin{cases} U = L(\beta\_1, \beta\_2, \dots, \beta\_{n-1}) = L(\beta\_1^\*, \beta\_2^\*, \dots, \beta\_{n-1}^\*) \\ v = \delta\_n \beta\_n \in L \\ \mathbf{x}' = \sum\_{i=1}^{n-1} \mathbf{x}\_i \beta\_i^\* + \delta\_n \theta\_n^\* \\ \mathbf{y} \text{ is the nearest lattice vector of } \mathbf{x} - \boldsymbol{\upsilon} \text{ in } L' \\ w = \mathbf{y} + \boldsymbol{\upsilon} \in L \end{cases} (3.1.22)$$

Since v = δ*n*β*n*, *x* = *n*−1 *i*=1 *xi*β∗ *i* + δ*n*β∗ *n* ,

$$|x - x'| = |x\_n - \delta\_n| |\beta\_n^\*| \lesssim \frac{1}{2} |\beta\_n^\*|.$$

The distance between any two planes in {*U* + *z* | *z* ∈ *L*} is at least |β∗ *n* |, and |*x* − *x* | is the distance of *x* from the nearest plane, so we have

$$|x - x'| \lesssim |x - u\_x|.$$

Let w = *y* + v = *y* + δ*n*β*n* ∈ *L*, we are to prove

$$\left|\mathbf{x} - w\right|^2 = \left|\mathbf{x} - \mathbf{x}'\right|^2 + \left|\mathbf{x}' - w\right|^2. \tag{3.1.23}$$

This is because

$$
\infty - \mathbf{x}' = (\mathbf{x}\_n - \delta\_n)\beta\_n^\*, \ \mathbf{x}' - w = \mathbf{x}' - v - \mathbf{y} \in U,
$$

therefore,

$$(\mathbf{x} - \mathbf{x'})\perp(\mathbf{x'} - \mathbf{w}),$$

and (3.1.23) holds. Based on the assumption:

$$|x'-w|^2 \lesssim \frac{1}{4} \left( |\beta\_1^\*|^2 + \dots + |\beta\_{n-1}^\*|^2 \right).$$

It follows that

$$\left| |\mathbf{x} - w|^2 \right|^2 \leqslant \frac{1}{4} (|\beta\_1^\*|^2 + \dots + |\beta\_{n-1}^\*|^2 + |\beta\_n^\*|^2) = \left(\frac{1}{2}\sigma(B)\right)^2 \dots$$

Let *x* = *t* ∈ R*n*, we get w ∈ *L* such that

$$|t - w| \le \frac{1}{2}\sigma(\mathcal{B}).$$

This lemma holds.

The calculation of the covering radius on lattice is also a kind of hard problem. We define the covering radius problem (CDPγ ) based on parameter approximation.

**Definition 3.1.4** (CDPγ ) Let *L* be a full rank lattice, γ (*n*) be a parameter, CDPγ problem is to find an *r* such that

$$
\rho(L) \leqslant r \leqslant \nu(n)\rho(L). \tag{3.1.24}
$$

#### **3.2 SIS and Knapsack Problem on Ring**

Let *q* be a positive integer, Z*q* be the residue class ring mod *q*, and Z*q* [*x*] be the polynomial ring of one variable on Z*q* . By (3.1.10), we define a quotient ring *Rq* on Z*q* [*x*]

$$R\_q = \mathbb{Z}\_q[\mathbf{x}]/<\mathbf{x}^n - 1> \cong (\mathbb{Z}\_q^n, +, \otimes). \tag{3.2.1}$$

To define the SIS problem on *Rq* , for any *m* polynomials *A* = {*a*1(*x*), . . . , *am*(*x*)} ⊂ *Rq* , *A* could be regarded as an *m* dimensional vector in *Rq* , i.e. *A* = (*a*1(*x*), . . . , *am*(*x*)) ∈ *Rm q* , with the norm |*A*| defined by

$$|A| = \left(\sum\_{i=1}^{m} |a\_i(\chi)|^2\right)^{\frac{1}{2}} = \left(\sum\_{i=1}^{m} |a\_i|^2\right)^{\frac{1}{2}},\tag{3.2.2}$$

where *ai*(*x*) ←→ *ai* ∈ Z*n q* . **Definition 3.2.1** Let β > 0 be a positive real number, *n*, *m*, *q* be positive integers. The SIS problem on *Rq* is defined as follows: for any given uniformly distributed vector *A* = (*a*1(*x*), . . . , *am*(*x*)) ∈ *Rm q* , find an *m* dimensional vector *z* = (*z*1(*x*),*z*2(*x*), . . . ,*zm*(*x*)) ∈ *Rm q* such that

$$\begin{cases} f\_A(z) = \sum\_{i=1}^m a\_i(\mathbf{x}) z\_i(\mathbf{x}) = 0\\ 0 < |z| = \left(\sum\_{i=1}^m |z\_i(\mathbf{x})|^2\right)^{\frac{1}{2}} \ll \beta \end{cases} \tag{3.2.3}$$

This problem is denoted as *Rq* − SIS*q*,β,*m*.

**Remark 3.2.1** By the above definition, *f A*(*z*) ∈ *Rq* , so *f A*(*z*) = 0 is equivalent to

$$f\_A(z) = \sum\_{i=1}^{m} a\_i(\mathbf{x}) z\_i(\mathbf{x}) \equiv 0 \pmod{x^n - 1},$$

here 0 < |*z*| β is computed in the real number field R.

**Remark 3.2.2** In order to guarantee the *Rq* − SIS*q*,β,*m* problem has solution, we only need *m* > log2*q*, which has big difference from the requirement *m* > *n*log*q* of the classical SIS problem (see Sect. 2.2 in the last chapter). In fact, if *A* = (*a*1(*x*), *a*2(*x*), . . . , *am*(*x*)) is given, the selection of *z* = (*z*1(*x*), . . . ,*zm*(*x*)) could be considered in Z*n q* . For each *zi*(*x*) ←→ *zi* ∈ Z*n q* , choose each coordinate of *zi* as 0 or 1 so that the *n* dimensional vector *zi* has a short length. There are about 2*n* such short vectors *zi* , so there are about 2*mn* choices of *z* in total. If 2*mn* > *qn*, i.e. *mn* > *n*log2*q*, *m* > log2*q*, then *z* ∈ *Rm q* , *z* ∈ *Rm q* ⇒

$$f\_A(z') = f\_A(z'') \Rightarrow f\_A(z' - z'') = 0.1$$

So *z* = *z* − *z* is the solution satisfying (3.2.3).

#### **Geometric definition of** *Rq* − SIS*q*,β,*m*:

Given *m* vectors *A* = (*a*1, *a*2,..., *am*) uniformly distributed on Z*n q* , *ai* ∈ Z*n q* , solve a group of nonzero short vectors *z* = (*z*1,*z*2,...,*zm*), *zi* ∈ Z*n q* , such that

$$\begin{cases} f\_A(z) = \sum\_{i=1}^m a\_i \otimes z\_i = 0\\ |z\_i| \ll \sqrt{n}, \ 1 \ll i \ll n \end{cases} . \tag{3.2.4}$$

Obviously, *Rq* − SIS problem is a special case of the knapsack problem on ring.

**Definition 3.2.2** (Knapsack problem on ring) Let *R* be a commutative ring with identity, *a*1,..., *am* be *m* nonzero elements in *R*, *X* ⊂ *R*, |*X*| = 2*n*, *b* ∈ *R* is called the target element. Knapsack problem on ring is to solve *m* elements *z*1,*z*2,...,*zm* ∈ *X* in *X* such that

$$f\_A(z) = \sum\_{i=1}^m a\_i z\_i = b,\ \forall z\_i \in X. \tag{3.2.5}$$

If *R* = Z is a ring of integers, *X* = {0, 1}, or *X* = {0, 1,..., 2*n* − 1}, then the above problem is the classical knapsack problem. It has been proved that the computational complexity of solving the knapsack problem on Z is subexponential, such as the super increasing sequence is polynomial. If *R* = *Rq* , *b* = 0, then the above problem becomes the SIS problem on *Rq* . The main result in this section is the following theorem:

**Theorem 3.2.1** *Let m* = *O*(log *n*)*, k* = *O*˜(log *n*)*, q* 4*mkn* 5 2 *, and* γ 16*mkn*3*, if we can solve the knapsack problem (3.2.6) on Rq , then there exists a probabilistic polynomial algorithm solving the covering radius problem CDP*γ *for any n dimensional full rank cyclic lattice.*

The knapsack problem on *Rq* in Theorem 3.2.1 is the more general case of (3.2.4), which is summarized in the following definition.

**Knapsack problem on** *Rq* : Choose *m* vectors *A* = (*a*1, *a*2,..., *am*) uniformly distributed on Z*n q* randomly and any target vector *b* ∈ Z*n q* , find a set of short vectors *z* = (*z*1,*z*2,...,*zm*) such that

$$f\_A(z) = \sum\_{i=1}^m a\_i \otimes z\_i = b, \ |z\_i| \le \sqrt{n}, \ 1 \le i \le m. \tag{3.2.6}$$

From Theorem 3.2.1, the knapsack problem on *Rq* on the average case has a more difficult computational complexity than the covering radius problem on any full rank cyclic lattice under positive probability, which is another reduction principle from the worst case to the average case by Ajtai.

The core idea of the proof of Theorem 3.2.1 is to approximate the covering radius ρ(*L*) of *L* by 1 2σ (*S*) for any cyclic lattice *L* = *L*(*B*) ⊂ R*n* under the assumption that (3.2.6) is solvable, where *S* = {*s*1,*s*2,...,*sn*} ⊂ *L* is a set of *n* linearly independent vectors, and

$$\sigma(S) = \left(\sum\_{i=1}^{n} |s\_i^\*|^2\right)^{\frac{1}{2}}.$$

{*s*∗ 1 ,*s*∗ 2 ,...,*s*∗ *n* } is the corresponding orthogonal basis of *S* using Gram-Schmidt algorithm. Since |*s*∗ *i* | - |*si*| (1 *i n*), we have

64 3 Learning with Error

$$\sigma(S) = \left(\sum\_{i=1}^{n} |s\_i^\*|^2\right)^{\frac{1}{2}} \lessdot \left(\sum\_{i=1}^{n} |s\_i|^2\right)^{\frac{1}{2}}.\tag{3.2.7}$$

By Lemma 3.1.6, ρ(*L*) - 1 2σ (*S*). The core steps of approximating ρ(*L*) by 1 2σ (*S*) is summarized as follows.

#### **(1) Reduced algorithm**

Randomly choose *S* = {*s*1,*s*2,...,*sn*} ⊂ *L* is a set of *n* linearly independent lattice vectors, assume that

$$|S| = |s\_n| = \max\_{1 \le i \le n} |s\_i|.$$

If 1 2σ (*S*) γρ(*L*), then the CDPγ problem on *L* is solved. If σ (*S*) > 2γρ(*L*), we can find a lattice vector *s* ∈ *L*, such that

$$|\mathbf{s'}| \lesssim \frac{1}{2}|\mathbf{s}\_n| = \frac{1}{2}|\mathbf{S}|,$$

and *s*1,*s*2,...,*sn*−1,*s* are linearly independent. Replace *S* with the new set of vectors *S* = {*s*1,*s*2,...,*sn*−1,*s* }, that is, replace *sn* with *s* in *S*. Repeat this process *n* times and we can get

$$|S'| \ll \frac{1}{2}|S|.\tag{3.2.8}$$

Repeat the above reduced algorithm, and find a set of linearly independent vectors *S* ⊂ *L*, such that

$$|S| \ll \frac{2\gamma}{\sqrt{n}} \rho(L),\tag{3.2.9}$$

and the computational complexity of the algorithm is polynomial. Based on (3.2.9), we have

$$
\rho(L) \lesssim \frac{1}{2}\sigma(\mathcal{S}) \lesssim \frac{\sqrt{n}}{2}|\mathcal{S}| \lesssim \chi\rho(L).
$$

So we complete solving the CDPγ problem.

#### **(2) Approximation of standard orthogonal basis**

Let {*e*0, *e*1,..., *en*−1} ⊂ Z*n q* be a standard orthogonal basis, *L* = *L*(*B*) ⊂ R*n* be a given cyclic lattice. Define the parameter

$$\beta = \left(\frac{4nq}{\nu} + \frac{\sqrt{n}}{2}\right) \sigma(\mathcal{S}),\tag{3.2.10}$$

where *S* = {*s*1,*s*2,...,*sn*} ⊂ *L* is a set of *n* linearly independent vectors, such that

$$
\sigma(\mathbb{S}) \succ 2\gamma\rho(L). \tag{3.2.11}
$$

To find *s* in the reduced algorithm, by Lemma 3.1.6, there is a lattice vector *c* ∈ *L* ⇒

$$|c - \beta e\_0| \leqslant \frac{1}{2}\sigma(\mathcal{S}).\tag{3.2.12}$$

Since *T* is an orthogonal matrix, it is an orthogonal linear transformation in R*n*, i.e.

$$|T\alpha| = |\alpha|, \,\forall \alpha \in \mathbb{R}^n.$$

Therefore, for any 0 *k n* − 1,

$$|T^k(c - \beta e\_0)| = |c - \beta e\_0| \lesssim \frac{1}{2}\sigma(S).$$

Note that *T k e*0 = *ek* , so

$$|T^k c - \beta e\_k| \lesssim \frac{1}{2} \sigma(S).$$

Because *c* ∈ *L* and *L* is a cyclic lattice, then *T k c* ∈ *L* (0 *k n* − 1). The circulant matrix *T* ∗(*c*) = [*c*, *T c*,..., *T k*−1*c*] implements the approximation of standard orthogonal basis.

In order to give a complete proof of theorem 3.2.1, we denote

$$B' = q(T^\*(c))^{-1}B.\tag{3.2.13}$$

**Lemma 3.2.1** *The lattice L*(*B* ) *generated by B satisfies q*Z*n* ⊂ *L*(*B* )*.*

*Proof* By Lemma 3.1.5, since *c* ∈ *L* and *L* is a cyclic lattice, there exists an integer matrix *D* ∈ Z*n*×*n* such that

$$T^\*(c) = BD \Rightarrow B^{-1}T^\*(c) \in \mathbb{Z}^{n \times n},$$

thus,

$$B'(B^{-1}T^\*(c)) = q(T^\*(c))^{-1} \cdot B \cdot B^{-1}T^\*(c) = qI\_n.$$

Each column of the above matrix *qe j* (0 *j n* − 1) ∈ *L*(*B* ) ⇒ *q*Z*n* ⊂ *L*(*B* ).

Based on Lemma 3.2.1, *q*Z*n* is an additive subgroup in *L*(*B* ). Randomly choose *mk* vectors *x i j* ∈ *G* (1 *i m*, 1 *j k*) in the quotient group *G* = *L*(*B* )/*q*Z*n*, the integral vectors w *i j* of *x i j* is defined by

$$w\_{ij}^{'} = [\boldsymbol{\chi}\_{ij}^{'}] \in \mathbb{Z}^{n}, \ 1 \leqslant i \leqslant m, \ 1 \leqslant j \leqslant k.$$

Let

$$a\_{\boldsymbol{i}} \equiv \sum\_{j=1}^{k} w\_{ij}^{'} \pmod{q} \Rightarrow a\_{\boldsymbol{i}} \in \mathbb{Z}\_q^n,\tag{3.2.14}$$

*A* = (*a*1, *a*2,..., *am*) contains the above *m* vectors in Z*n q* , consider the knapsack problem on *Rq* = (Z*n q* , +, ⊗),

$$f\_A(z) = \sum\_{i=1}^m a\_i \otimes z\_i, \ \forall z\_i \in \mathbb{Z}\_q^n, \ |z\_i| \le \sqrt{n}.$$

If we can solve the knapsack problem on *Rq* , then *f A*(*z*) collision is also solvable. So there are integral vectors *y* = (*y*1, *y*2,..., *ym*), *y*ˆ = (*y*ˆ1, *y*ˆ2,..., *y*ˆ*m*) such that

$$f\_A(\mathbf{y} - \hat{\mathbf{y}}) = \sum\_{i=1}^{m} a\_i \otimes (\mathbf{y}\_i - \hat{\mathbf{y}}\_i) = 0,\ \forall |\mathbf{y}\_i| \leqslant \sqrt{n},\ |\hat{\mathbf{y}}\_i| \leqslant \sqrt{n},\tag{3.2.15}$$

where

$$\mathbf{y} = (\mathbf{y}\_1, \mathbf{y}\_2, \dots, \mathbf{y}\_m), \ \hat{\mathbf{y}} = (\hat{\mathbf{y}}\_1, \hat{\mathbf{y}}\_2, \dots, \hat{\mathbf{y}}\_m). \tag{3.2.16}$$

Based on the vector clusters *y* and *y*ˆ in Z*n q* , we define

$$\begin{cases} \mathbf{x}\_{ij} = \frac{1}{q} T^\*(c) \mathbf{x}\_{ij}^{'} \text{ and } w\_{ij} = \frac{1}{q} T^\*(c) w\_{ij}^{'}\\\mathbf{s}^{'} = \sum\_{i=1}^{m} \sum\_{j=1}^{k} (\mathbf{x}\_{ij} - w\_{ij}) \otimes (\mathbf{y}\_i - \hat{\mathbf{y}}\_i) \end{cases} \tag{3.2.17}$$

The *s* defined by the above formula is just the *s* in the reduced algorithm. First, we prove the following lemma.

**Lemma 3.2.2** *xi j* ∈ *L*(*B*) *is a lattice vector in the given cyclic lattice L (*1 *i* - *m*, 1 *j k), and if f A*(*y*) = *f A*(*y*ˆ)*, s* ∈ *L*(*B*) *is also a lattice vector.*

*Proof* Since *x i j* ∈ *L*(*B* ), there is α ∈ Z*n* such that *x i j* = *B* α, we get

$$\alpha\_{ij} = \frac{1}{q} T^\*(c) B' \alpha = \frac{1}{q} T^\*(c) \cdot q(T^\*(c))^{-1} \cdot B \alpha = B \alpha \in L(B).$$

To prove *s* ∈ *L*(*B*), by (3.2.17) and the property of circulant matrix (see (3.1.5))

$$\begin{split} s' &= \sum x\_{ij} \otimes (\mathbf{y}\_{ij} - \hat{\mathbf{y}}\_{ij}) - \sum w\_{ij} \otimes (\mathbf{y}\_{ij} - \hat{\mathbf{y}}\_{ij}) \\ &= \sum T^\*(\mathbf{x}\_{ij})(\mathbf{y}\_{ij} - \hat{\mathbf{y}}\_{ij}) - \sum T^\*(w\_{ij})(\mathbf{y}\_{ij} - \hat{\mathbf{y}}\_{ij}) \\ &= \sum\_{i=1}^m T^\*(\sum\_{j=1}^k \mathbf{x}\_{ij})(\mathbf{y}\_i - \hat{\mathbf{y}}\_i) - \sum\_{i=1}^m T^\*(\sum\_{j=1}^k w\_{ij})(\mathbf{y}\_i - \hat{\mathbf{y}}\_i). \end{split} \tag{3.2.18}$$

Based on the first conclusion, *xi j* ∈ *L*(*B*) ⇒ *k j*=1 *xi j* ∈ *L*(*B*), since *yi* and *y*ˆ*i* are integral vectors in Z*n q* , it follows that

$$T^\* \left(\sum\_{j=1}^k x\_{ij}\right) (\mathbf{y}\_i - \hat{\mathbf{y}}\_i) \in L(B).$$

Next we prove the second term of (3.2.18) is also a lattice vector. By the definition of w*i j* ,

$$w\_{ij} = \frac{1}{q} T^\*(c) w\_{ij}^{'}, \text{ then } \sum\_{j=1}^{k} w\_{ij} = \frac{1}{q} T^\*(c) \left(\sum\_{j=1}^{k} w\_{ij}^{'}\right).$$

Hence,

$$T^\*\left(\sum\_{j=1}^k w\_{ij}\right) = \frac{1}{q} T^\*(c) T^\*\left(\sum\_{j=1}^k w\_{ij}^{'}\right).$$

The second term of (3.2.18) could be written as

$$\begin{split} \sum\_{i=1}^{m} T^\*(\sum\_{j=1}^{k} w\_{ij})(\mathbf{y}\_i - \hat{\mathbf{y}}\_i) &= \frac{1}{q} T^\*(c) \sum\_{i=1}^{m} T^\*(\sum\_{j=1}^{k} w\_{ij}')(\mathbf{y}\_i - \hat{\mathbf{y}}\_i) \\ &= \frac{1}{q} T^\*(c) \sum\_{i=1}^{m} \sum\_{j=1}^{k} w\_{ij}' \otimes (\mathbf{y}\_i - \hat{\mathbf{y}}\_i). \end{split} \tag{3.2.19}$$

Since

$$\sum\_{i=1}^{m} \sum\_{j=1}^{k} w\_{ij}^{'} \otimes (\mathbf{y}\_{i} - \hat{\mathbf{y}}\_{i}) \equiv \sum\_{i=1}^{m} a\_{i} \otimes (\mathbf{y}\_{i} - \hat{\mathbf{y}}\_{i}) \bmod q \equiv f\_{A}(\mathbf{y}) - f\_{A}(\hat{\mathbf{y}}) \bmod q,$$

by *f A*(*y*) = *f A*(*y*ˆ), we know the second term of (3.2.18) is in *L*(*B*), i.e.

$$\sum\_{i=1}^{m} T^\*(\sum\_{j=1}^{k} w\_{ij})(\mathbf{y}\_i - \hat{\mathbf{y}}\_i) \in L(B).$$

Finally we have *s* ∈ *L*(*B*) based on (3.2.18).

**Lemma 3.2.3** *The lattice vector s defined in (3.2.17) satisfies*

$$|s'| \ll \frac{1}{2}|s\_n| = \frac{1}{2}|S|.\tag{3.2.20}$$

#### 68 3 Learning with Error

*Proof* We only prove |*s* | σ (*S*)/2 √*n*, since

$$\sigma(S) \lesssim \left(\sum\_{i=1}^n |s\_i|^2\right)^{\frac{1}{2}} \lesssim \sqrt{n}|S| = \sqrt{n}|s\_n|,$$

we can get |*s* | - 1 2 |*sn*|, and the lemma is proved. Based on the definition of *s* ,

$$|s'| \ll \sum\_{i=1}^{m} \sum\_{j=1}^{k} |(\mathbf{x}\_{ij} - w\_{ij}) \otimes (\mathbf{y}\_i - \hat{\mathbf{y}}\_i)|. \tag{3.2.21}$$

It follows that

$$x\_{ij} - w\_{ij} = \frac{1}{q} T^\*(c)(\boldsymbol{x'\_{ij}} - \boldsymbol{w'\_{ij}}) = \frac{1}{q} c \otimes (\boldsymbol{x'\_{ij}} - \boldsymbol{w'\_{ij}}).$$

Let α = *c* − β*e*0, then |α| - 1 2σ (*S*) (see (3.2.12)), and

$$\begin{split} \boldsymbol{x}\_{ij} - \boldsymbol{w}\_{ij} &= \frac{1}{q} (\boldsymbol{\alpha} + \beta \boldsymbol{e}\_{0}) \otimes (\boldsymbol{\alpha'\_{ij}} - \boldsymbol{w'\_{ij}}) = \frac{1}{q} \boldsymbol{T^\*} (\boldsymbol{\alpha} + \beta \boldsymbol{e}\_{0}) (\boldsymbol{\alpha'\_{ij}} - \boldsymbol{w'\_{ij}}) \\ &= \frac{1}{q} \beta \boldsymbol{T^\*} (\boldsymbol{e}\_{0}) (\boldsymbol{x'\_{ij}} - \boldsymbol{w'\_{ij}}) + \frac{1}{q} \boldsymbol{T^\*} (\boldsymbol{\alpha}) (\boldsymbol{x'\_{ij}} - \boldsymbol{w'\_{ij}}) \\ &= \frac{\beta}{q} (\boldsymbol{x'\_{ij}} - \boldsymbol{w'\_{ij}}) + \frac{1}{q} \boldsymbol{T^\*} (\boldsymbol{\alpha}) (\boldsymbol{x'\_{ij}} - \boldsymbol{w'\_{ij}}). \end{split}$$

Since

$$|\boldsymbol{x}\_{ij}^{'} - \boldsymbol{w}\_{ij}^{'}| \leqslant \frac{1}{2}\sqrt{n},$$

combine with (3.1.15) in the last section, we have (β is determined by (3.2.10))

$$\begin{split} |x\_{ij} - w\_{ij}| &\leqslant \frac{\beta}{q} |x\_{ij}^{'} - w\_{ij}^{'}| + \frac{1}{q} |\alpha \otimes (x\_{ij}^{'} - w\_{ij}^{'})| \\ &\leqslant \frac{\beta}{q} \cdot \frac{1}{2} \sqrt{n} + \frac{1}{q} \cdot \frac{\sqrt{n}}{2} \cdot \sqrt{n} \cdot \frac{1}{2} \sigma(S) \\ &= \frac{\beta}{q} \cdot \frac{\sqrt{n}}{2} + \frac{1}{q} \sqrt{n} \cdot \frac{\sigma(S)}{2} \cdot \frac{\sqrt{n}}{2} \\ &= \sigma(S) \left( \frac{2n^{\frac{3}{2}}}{\mathcal{Y}} + \frac{n}{2q} \right) \\ &\leqslant \sigma(S) \left( \frac{1}{8} \cdot \frac{1}{mkn^{\frac{1}{2}}} + \frac{1}{8} \cdot \frac{1}{mkn^{\frac{1}{2}}} \right) \\ &= \frac{1}{4} \sigma(S) \frac{1}{mkn^{\frac{1}{2}}}. \end{split}$$

Based on (3.2.21), we get

$$\begin{aligned} |\mathbf{s'}| &\leqslant mk\sqrt{n} \max\_{i,j} |\mathbf{x}\_{ij} - w\_{ij}| \cdot \max\_{i} |\mathbf{y}\_i - \hat{\mathbf{y}}\_i| \\\\ &\leqslant mk\sqrt{n} \cdot 2\sqrt{n} \max\_{i,j} |\mathbf{x}\_{ij} - w\_{ij}| \leqslant \frac{\sigma(S)}{2\sqrt{n}}.\end{aligned}$$

So we complete the proof of Lemma 3.2.3.

From the above lemma, the reduced algorithm required in Theorem3.2.1 is proved. However, we must prove that {*ai*} *m i*=1 ⊂ Z*n q* determined by (3.2.14) is uniformly distributed, so that the knapsack problem on *Rq* is solved in the average case. Next we prove that{*ai*} *m i*=1 is almost uniformly distributed in Z*n q* , that is, the statistical distance between the distribution of {*ai*} and the uniform distribution is sufficiently small. We first prove the following lemma.

**Lemma 3.2.4** *Let B* = *q*(*T* ∗(*c*))−1*B, then the covering radius* ρ(*B* ) *of L*(*B* ) *satisfies*

$$
\rho(B') \le \frac{1}{8n},
$$

*where L*(*B*) *is a full rank cyclic lattice, c* ∈ *L*(*B*) *is given by (3.2.12).*

*Proof* Based on the definition of covering radius,

$$\rho(B') = \max\_{\mathbf{x} \in \mathbb{R}^n} |\mathbf{x} - \boldsymbol{\mu}\_x| = \max\_{\mathbf{x} \in \mathbb{R}^n} |\mathbf{x} - L(B')|.$$

Let *t* ∈ R*n* be the vector achieving the maximum value above, i.e. |*t* − *L*(*B* )| ρ(*B* ), and

$$|t' - B'z| \geqslant \rho(B'), \ \forall \ z \in \mathbb{Z}^n.$$

Denote

$$t = \frac{1}{q} T^\*(c)t'.$$

Suppose *Bz*0 ∈ *L*(*B*) is the nearest lattice vector of *t*, then we have

$$\begin{split} \rho(B) &\geqslant \text{dist}(t, L(B)) = |t - Bz\_0| \\ &= |\frac{1}{q}T^\*(c)t' - Bz\_0| = |\frac{1}{q}T^\*(c)(t' - B'z\_0)| \\ &\geqslant \frac{1}{q}|t' - B'z\_0| \min\_d \frac{|c \otimes d|}{|d|} \\ &\geqslant \frac{1}{q}\rho(B') \min\_{d \in \mathbb{R}^n, d \neq 0} \frac{|c \otimes d|}{|d|}. \end{split} \tag{3.2.22}$$

For any *d* ∈ R*n*, *d* = 0, we estimate the value of *c* ⊗ *d*. Since *c* = β*e*0 + α, where |α| - 1 2σ (*S*), so

$$\begin{aligned} |c \otimes d| &= |(\beta e\_0 + \alpha) \otimes d| \\ &\ge |d|(\beta - \frac{1}{2}\sqrt{n}\sigma(S)) \\ &\ge \beta |d| - \sqrt{n}|\alpha||d| \\ &= |d|\frac{4nq}{\mathcal{Y}}\sigma(S). \end{aligned}$$

By (3.2.22), we have (see (3.2.11))

$$
\begin{aligned}
\rho(B) &\geqslant \frac{1}{q} \rho(B') \cdot \frac{4nq}{\nu} \sigma(S), \\
&\geqslant 8n\rho(B')\rho(B).
\end{aligned}
$$

This implies ρ(*B* ) - 1 8*n* . Lemma 3.2.4 holds.

**Lemma 3.2.5** *Let* = *L*(*B*) *be a lattice, Q* ⊂ R*n is convex and contains a ball with the radius r* ρ( )*. Then the number of lattice vectors of L*(*B*) *contained in Q satisfies*

$$\frac{\text{Vol}(\mathcal{Q})}{\det(\Lambda)}(1-\frac{\rho(\Lambda)n}{\chi}) \lesssim |L(\mathcal{B}) \cap \mathcal{Q}| \lesssim \frac{\text{Vol}(\mathcal{Q})}{\det(\Lambda)}(1+\frac{2\rho(\Lambda)n}{\chi}).$$

*Proof* See Lyubashevsky and Micciancio (2006) or Lyubashevsky (2010).

Based on the above lemma, let = *L*(*B* ), we estimate the distribution of vectors {*ai j*} in Z*n q* . From the definition

$$a\_{ij} \equiv w\_{ij}^{'} \pmod{q}, \ a\_i \equiv \sum\_{j=1}^{k} a\_{ij} \pmod{q},\tag{3.2.23}$$

where w *i j* is the rounding vector of *x i j* ∈ *G* = *L*(*B* )/*q*Z*n*. The ball taking w *i j* as the center with radius 1 2 is contained in the cube centered as w *i j* with the side length 1 2 . Since ρ(*L*(*B* )) - 1 8*n* < 1 2 , from lemma 3.2.4, the number *N* of lattice vectors of *L*(*B* ) in this cube satisfies

$$\frac{1}{\det(B')} \left(1 - \frac{1}{4}\right) \leqslant N \leqslant \frac{1}{\det(B')} (1 + \frac{1}{2}).$$

For any *a* ∈ *Rq* = Z*n q* , because *x i j* is uniformly selected in *L*(*B* )/*q*Z*n*, there are

$$|L(B')/q\mathbb{Z}^n|^{-1} = \frac{q^n}{\det(B')}$$

possible choices, therefore,

$$\left| \Pr\{a\_{ij} = a\} - \frac{1}{q^n} \right| \leqslant \frac{1}{2q^n}.\tag{3.2.24}$$

Now we estimate the probability distribution of {*ai*} *m i*=1.

**Lemma 3.2.6** *Let G be a finite Abel group, A*1, *A*2,..., *Ak be k independent random variables on G, such that for any element x* ∈ *G,*

$$\left| \Pr\{A\_i = x\} - \frac{1}{|G|} \right| \leqslant \frac{1}{2|G|}.$$

*Then the statistical distance between* ξ = *k i*=1 *Ai and the uniform distribution on G is*

$$
\Delta(\xi, U(G)) \lesssim 2^{-(k+1)}.
$$

*Proof* We use mathematical induction to prove that the following inequality holds for any positive integer *k*,

$$\left| \Pr\{\xi = x\} - \frac{1}{|G|} \right| \leqslant \frac{1}{2^k |G|}, \ \forall x \in G.$$

If *k* = 1, the inequality above holds. Assume it holds for *k* − 1, denote ξ = *k*−1 *i*=1 *Ai* , ξ = ξ + *Ak* , we have

$$\begin{split} \left| \Pr\{\xi = x\} - \frac{1}{|G|} \right| &= \left| \sum\_{a \in G} \Pr\{\xi' = a, A\_k = x - a\} - \frac{1}{|G|} \right| \\ &= \left| \sum\_{a \in G} \Pr\{\xi' = a\} \Pr\{A\_k = x - a\} - \frac{1}{|G|} \right| \\ &= \left| \sum\_{a \in G} \left( \Pr\{\xi' = a\} - \frac{1}{|G|} \right) \left( \Pr\{A\_k = x - a\} - \frac{1}{|G|} \right) \right| \\ &\leqslant \sum\_{a \in G} \frac{1}{2^{k-1}|G|} \cdot \frac{1}{2|G|} = \frac{1}{2^k|G|} . \end{split}$$

Thus,

$$\Delta(\xi, U(G)) = \frac{1}{2} \sum\_{x \in G} \left| \Pr\{\xi = x\} - \frac{1}{|G|} \right| \leqslant \frac{1}{2} \sum\_{x \in G} \frac{1}{2^k |G|} = 2^{-(k+1)}.$$

This lemma holds.

From (3.2.23), (3.2.24) and Lemma 3.2.5, we know that each *ai* = *k j*=1 *ai j* is almost uniformly distributed on Z*n q* , i.e. the statistical distance between *ai* and the uniform distribution is sufficiently small. Therefore, the knapsack problem on *Rq* sampled by *f A*(*z*) is in the average case. So far, we have completed the proof of Theorem 3.2.1.

#### **3.3 LWE Problem**

The LWE problem is to solve a kind of random linear equations under a given probability distribution. To better understand the LWE problem, let's start with the checking learning problem (LPE) with errors. Let Z2 = {0, 1} be a finite field with 2 elements, *n* 1 and ε 0 be a given parameter. The distribution of ξ with parameter ε on Z2 is

$$\Pr\{\xi=0\} = 1 - \varepsilon, \Pr\{\xi=1\} = \varepsilon.$$

If *a*, *b* ∈ Z2, the probability that *a* and *b* having the same parity is 1 − ε, i.e.

$$\Pr\{a \equiv b \pmod{2}\} = 1 - \varepsilon,$$

denoted as *a* ≡ε *b*. The checking learning problem with errors LPE is: given *m* independent vectors {*a*1, *a*2,..., *am*}, *ai* ∈ Z*n* 2 uniformly distributed on Z*n* 2, and *b* = ⎛ *b*1 ⎞

⎜ ⎝ . . . *bm* ⎟ ⎠ ∈ Z*m* 2 , to solve a vector*s* ∈ Z*n* 2, such that the following *m* random congruence

equations hold simultaneously

$$\begin{cases} b\_1 \equiv\_\ell  \pmod{2} \\ b\_2 \equiv\_\ell  \pmod{2} \\ \vdots \\ b\_m \equiv\_\ell  \pmod{2} \end{cases} \tag{3.3.1}$$

where < *ai*,*s* > is the inner product of two vectors in Z*n* 2. If ε = 0, then the distribution ξ becomes the trivial distribution, and (3.3.1) becomes *m* deterministic congruence equations. At this time, the LPE problem could be solved by Gauss elimination method with only *n* equations, and the computational complexity is a polynomial of *n*. If ε > 0, the LPE problem is nontrivial, and its computational complexity is exponential of *n*. For example, the likelihood algorithm requires *O*(*n*) random congruence equations with computational complexity 2*O*(*n*) . In 2003, Blum et al. (2003) proposed a subexponential algorithm whose computational complexity and the number of random congruence equations are both 2*O*(*n*/ log *n*) , which is the best result of the LPE question so far.

#### 3.3 LWE Problem 73

Generalizing the LPE problem from mod 2 to the general case mod *q*, it becomes the LWE problem. Due to the important role of the LWE problem in modern antiquantum computing cryptosystems, we will introduce the related concepts and results in detail in this section. First, we define the random congruence equation with error on the integer ring Z. Let *n* 1, *q* 2 be two positive integers, Z*q* be the residue class ring of mod *q*, and χ be a probability distribution on Z*q* .

**Definition 3.3.1** Let *a*, *b* ∈ Z, *e* ∈ Z*q* , if

$$\Pr\{a \equiv b + e \pmod{q}\} = \chi(e),\tag{3.3.2}$$

we call *a* and *b* are congruential mod *q* under the distribution χ, denoted as

$$a \equiv\_{\chi} b + e \pmod{q}, \text{ or } a =\_{\chi} b + e. \tag{3.3.3}$$

The above formula is called a random congruence equation with error under χ, and it is abbreviated as *a* = *b* + *e* sometimes.

Based on the above random congruence equation, we give the definition of the LWE distribution *As*,χ .

**Definition 3.3.2** Let *s* ∈ Z*n q* , χ be a given distribution on Z*q* , the LWE distribution *As*,χ = (*a*, *b*) ∈ Z*n q* × Z*q* generated by *s* and χ satisfies:

Under the LWE distribution *As*,χ = (*a*, *b*) ∈ Z*n q* × Z*q* , for a given error *e* ∈ Z*q* , the essence of finding the private key *s* = (*s*1,*s*2,...,*sn*) ∈ Z*n q* is solving the random knapsack problem on the ring Z*q* :

$$b \equiv a\_1 s\_1 + a\_2 s\_2 + \dots + a\_n s\_n \pmod{q},$$

solve *s* ∈ Z*n q* under the probability distribution χ (*e*). Next, we give the definition of LWE problem LWE*n*,*q*,χ ,*m* with the parameters *n* 1, *q* 2, *m* 1 and χ.

**Definition 3.3.3** For any *m* independent samples (*ai*, *bi*) ∈ Z*n q* × Z*q* (1 *i m*) of *As*,χ , and randomly selected samples of the error distribution *e* = ⎛ ⎜ ⎝ *e*1 . . . *em* ⎞ ⎟ ⎠, *ei* ∈ Z*q* , *ei* ← χ, the LWE*n*,*q*,χ ,*m* problem is to solve the private key *s* ∈ Z*n q* with high probability (larger than 1 − δ). In other words, solve *s* ∈ Z*n q* satisfying

$$\begin{cases} b\_1 =\_\chi  +e\_1 \\ b\_2 =\_\chi  +e\_2 \\ \vdots \\ b\_m =\_\chi  +e\_m \end{cases} \tag{3.3.4}$$

.

**Remark 3.3.1** If χ is the trivial distribution, i.e. χ (0) = 1, χ (*k*) = 0 for 1 *k* < *q*, then the samples of χ are *e* = ⎛ ⎜ ⎝ 0 . . . 0 ⎞ ⎟ ⎠, (3.4) becomes *m* deterministic congruence

equations

$$\begin{cases} b\_1 \equiv  \pmod{q} \\ b\_2 \equiv  \pmod{q} \\ \vdots \\ b\_m \equiv  \pmod{q} \end{cases}$$

Based on the Gauss elimination, we can calculate the only private key *s* ∈ Z*n q* from *n* congruence equations, and the computational complexity is polynomial.

**Remark 3.3.2** Let *q* = 2, χ be the two point distribution with parameter ε on Z2, then the LWE problem on Z2 is just the LPE problem. For any error distribution

$$e = \begin{pmatrix} e\_1 \\ \vdots \\ e\_m \end{pmatrix}, \text{ if } e\_i = 1 \text{, from } i$$

Pr{*bi* ≡< *ai*,*s* > +1 (mod 2)} = ε,

we can get

$$\Pr\{b\_i \equiv  \pmod{2}\} = 1 - \varepsilon.$$

**Matrix representation of the** LWE*n*,*q*,χ ,*m* **problem**

Let *A* = [*a*1, *a*2,..., *am*]*n*×*m* ∈ Z*n*×*m q* be a random matrix uniformly distributed, *b* = ⎛ ⎜ ⎜ ⎜ ⎝ *b*1 *b*2 . . . *bm* ⎞ ⎟ ⎟ ⎟ ⎠ ∈ Z*m q* , *e* = ⎛ ⎜ ⎜ ⎜ ⎝ *e*1 *e*2 . . . *em* ⎞ ⎟ ⎟ ⎟ ⎠ ∈ Z*m q* be the errors, and *e* ← χ*m*, solve the private key *s* ∈ Z*n q* , such that *b* ≡χ *A s* + *e* (mod *q*), (3.3.5)

where *A* is the transpose matrix of *A*, and (3.3.5) is a set of random congruence equations with errors. The probability that the *i*th congruence equation holds is χ (*ei*), so

$$\Pr\{b \equiv\_{\chi} A's + e \pmod{q}\} = \Pi\_{i=1}^{m} \chi(e\_i) = \chi(e). \tag{3.3.6}$$

Let *q* (*A*) and ⊥ *q* (*A*) be *q* ary integral lattices (see Sect. 7.3 of Chap. 7 in Zheng (2022)), defined by:

$$\begin{cases} \Lambda\_q(A) = \{A^\prime x \mid x \in \mathbb{Z}\_q^n\} + q\mathbb{Z}\_q^n\\ \Lambda\_q^\perp(A) = \{x \in \mathbb{Z}\_q^m \mid Ax \equiv 0 \pmod{q}\} \end{cases} \tag{3.3.7}$$

Since *q* (*A*) = *q* ⊥ *q* (*A*)∗, *A s* ∈ *q* (*A*), the geometric meaning of LWE*n*,*q*,χ ,*m* is to solve a lattice vector *A s* near from *b* for any *b* ∈ Z*m q* , such that the distance *b* − *A s* has the distribution χ*m*, which is dual to the SIS problem.

**Lemma 3.3.1** *Suppose A* ∈ Z*n*×*m q is a random matrix uniformly distributed, A* = [*A*1, *A*2]*, where A*1 ∈ Z*n*×*n q is an invertible matrix, let A* = *A*−1 1 *A* = [*In*, *A*−1 1 *A*2]*, then As*,χ *and As*,χ *have the same probability distribution.*

*Proof* From Lemma 2.1.1 in Chap. 2, if *A* is uniformly distributed, then *A* is also a uniform random matrix. Assume *b* = *b*1 *b*2 , *e* = *e*1 *e*2 , *s* ∈ Z*n q* satisfy

$$b \equiv\_{\chi} A's + e \pmod{q},$$

that is,

$$\begin{cases} b\_1 \equiv\_\chi A\_1^\prime s + e\_1 \pmod{q} \\ b\_2 \equiv\_\chi A\_2^\prime s + e\_2 \pmod{q} \end{cases} .$$

Let *A*∗ 1 = (*A* 1)−1, and

$$
\overline{b} = \begin{pmatrix} A\_1^\* b\_1 \\ A\_1^\* b\_2 \end{pmatrix}, \ \overline{e} = \begin{pmatrix} A\_1^\* e\_1 \\ A\_1^\* e\_2 \end{pmatrix}.
$$

Obviously, *b* and *b* have the same probability distribution, so are *e* and *e*,

$$\begin{aligned} \overline{b} &\equiv\_{\mathbb{X}} A\_1^\* \binom{b\_1}{b\_2} \pmod{q} \equiv\_{\mathbb{X}} A\_1^\* (A's + e) \pmod{q} \\\\ &\equiv\_{\mathbb{X}} A\_1^\* A's + A\_1^\* e \pmod{q} \equiv\_{\mathbb{X}} \overline{A'}s + e \pmod{q}. \end{aligned}$$

The lemma holds.

The above *A* = [*In*, *A*−1 1 *A*2] is called the normal form of the LWE problem.

**Lemma 3.3.2** *Let x*, *y*,*z be three random variables on* Z*q , x and y are independent, z* ≡ *x* + *y* (*mod q*)*. If x is uniformly distributed on* Z*q , so is z.*

*Proof* For any integer 0 *i q* − 1, we compute the probability that *z* takes the value *i*.

$$\begin{split} \Pr\{z=i\} &= \sum\_{j=0}^{q-1} \Pr\{\mathbf{x}=j, \mathbf{y}=i-j\} \\ &= \sum\_{j=0}^{q-1} \Pr\{\mathbf{x}=j\} \Pr\{\mathbf{y}=i-j\} \\ &= \frac{1}{q} \sum\_{j=0}^{q-1} \Pr\{\mathbf{y}=i-j\} = \frac{1}{q} .\end{split}$$

**Lemma 3.3.3** *In the LWE distribution As*,χ = (*a*, *b*)*, b is uniformly distributed if and only if b*− < *a*,*s* > *is uniformly distributed.*

*Proof* If *b*− < *a*,*s* > is uniformly distributed, from *b* = (*b*− < *a*,*s* >)+ < *a*,*s* > and Lemma 3.3.2, we get *b* is uniform. On the other hand, if *b* is uniform, from *b*− < *a*,*s* >= *b* + (− < *a*,*s* >) and Lemma 3.3.2 again, *b*− < *a*,*s* > is also uniformly distributed.

According to Definition 3.3.1, the above lemma gives an equivalent condition that *As*,χ is a uniform LWE distribution. An equivalent form of the LWE problem is the decision LWE problem, which we call the D-LWE problem.

**Definition 3.3.4** (D-LWE problem) Given *a* ∈ Z*n q* is uniformly distributed, *s* ∈ Z*n q* , *e* ∈ Z*q* with the distribution χ, decide whether < *a*,*s* > +*e* is uniform under positive probability of *s*.

The D-LWE problem seems easy, however, the difficulty of it is equivalent to that of the LWE problem. We will prove this equivalence in detail in Sect. 3.4. Here we focus on the probability distribution χ of the LWE problem. Usually, χ takes the discrete Gauss distribution on Z*q* . In Chapter 1, we discussed the discretization of continuous random variable with Gauss distribution in R*n* on lattice in detail. The discrete Gauss distribution on Z*q* is actually the discretization of Gauss distribution on Z*q* .

Recall the definition of Gauss function ρ*s*(*x*) in Chap. 1 (see (3.2.1),

$$\rho\_s(\mathbf{x}) = e^{-\frac{\pi}{r^2}|\mathbf{x}|^2}, \ \mathbf{x} \in \mathbb{R}^n. \tag{3.3.8}$$

If *n* = 1, ρ*s*(*x*) is a density function of continuous random variable on R. We convert the corresponding random variable of ρ*s*(*x*) to mod 1, which becomes a continuous random variable defined on T ≡ [0, 1) (mod 1) of length 1, with the density function

#### 3.3 LWE Problem 77

$$\psi\_{\beta}(\mathbf{x}) = \sum\_{k=-\infty}^{+\infty} \frac{1}{\beta} e^{-\frac{\pi}{\beta^2}(x-k)^2}, \ x \in \mathbb{T}. \tag{3.3.9}$$

It is easy to see that

$$\int\_{\mathbb{T}} \psi\_{\beta}(\mathbf{x}) \mathrm{d}x = \int\_{0}^{1} \psi\_{\beta}(\mathbf{x}) \mathrm{d}x = \int\_{\mathbb{R}} \frac{1}{\beta} \rho\_{\beta}(\mathbf{x}) \mathrm{d}x = 1.1$$

In order to estimate the statistical distance between random variables defined by different β, we first prove the following two lemmas.

**Lemma 3.3.4** *Let t and l be positive real numbers, x*, *y* ∈ R*n satisfy*

$$|x| \ll t, \text{ and } |x - y| \ll l.$$

*Then*

$$
\rho\_s(\mathbf{y}) \geqslant \left(1 - \frac{\pi}{s^2}(2tl + l^2)\right) \rho\_s(\mathbf{x}).\tag{3.3.10}
$$

*Proof* For any *z* ∈ R, we have

$$e^{-z} \gg 1 - z, \ z \in \mathbb{R}.$$

Therefore,

$$\begin{aligned} \rho\_s(\mathbf{y}) &= e^{-\frac{\pi}{r^2}|\mathbf{y}|^2} \ge e^{-\frac{\pi}{r^2}(|\mathbf{x}| + |\mathbf{y} - \mathbf{x}|)^2} \\ &\ge e^{-\frac{\pi}{r^2}(|\mathbf{x}|^2 + 2l|\mathbf{x}| + l^2)} \\ &\ge e^{-\frac{\pi}{r^2}(|\mathbf{x}|^2 + 2tl + l^2)} \\ &\ge (1 - \frac{\pi}{s^2}(2tl + l^2))\rho\_s(\mathbf{x}). \end{aligned}$$

**Lemma 3.3.5** *Let* 0 <α<β - 2α*, then the statistical distance between* ψα *and* ψβ *satisfies*

$$
\Delta(\psi\_a, \psi\_\beta) \lessapprox \frac{9}{2} (\frac{\beta}{\alpha} - 1). \tag{3.3.11}
$$

*Proof* Based on

$$\int\_0^1 \psi\_\beta(x) dx = 1,$$

it follows that

$$\begin{split} &\int\_{0}^{1} |\psi\_{\beta}(\mathbf{x}) - \psi\_{\alpha}(\mathbf{x})| \mathbf{dx} \\ &= \int\_{0}^{1} \left| \sum\_{k=-\infty}^{+\infty} \left( \frac{1}{\beta} e^{-\frac{\pi}{\beta^{\*}} |k-\mathbf{x}|^{2}} - \frac{1}{\alpha} e^{-\frac{\pi}{\alpha^{\*}} |k-\mathbf{x}|^{2}} \right) \right| \mathbf{dx} \\ &\leq \sum\_{k=-\infty}^{+\infty} \int\_{0}^{1} \left| \frac{1}{\beta} e^{-\frac{\pi}{\beta^{\*}} |\mathbf{x}-\mathbf{k}|^{2}} - \frac{1}{\alpha} e^{-\frac{\pi}{\alpha^{\*}} |\mathbf{x}-\mathbf{k}|^{2}} \right| \mathbf{dx} \\ &= \int\_{-\infty}^{+\infty} \left| \frac{1}{\beta} e^{-\frac{\pi}{\beta^{\*}} |\mathbf{x}|^{2}} - \frac{1}{\alpha} e^{-\frac{\pi}{\alpha^{\*}} |\mathbf{x}|^{2}} \right| \mathbf{dx} . \end{split}$$

Let *x* = α*y*, we get

$$\int\_0^1 |\psi\_\beta(\mathbf{x}) - \psi\_\alpha(\mathbf{x})| \mathrm{d}\mathbf{x} \lesssim \int\_{-\infty}^{+\infty} \left| \frac{1}{\beta/\alpha} e^{-\frac{\pi}{(\beta/\alpha)^2} |\mathbf{y}|^2} - e^{-\pi |\mathbf{y}|^2} \right| \mathrm{d}\mathbf{y}.\tag{3.3.12}$$

Without loss of generality, assume α = 1, β = 1 + ε, where 0 < ε - 1, we estimate the right hand of (3.3.12)

$$\begin{split} &\int\_{\mathbb{R}} \left| e^{-\pi |x|^{2}} - \frac{1}{1+\varepsilon} e^{-\frac{\pi}{(1+\varepsilon)^{2}} |x|^{2}} \right| \mathrm{d}x \\ &\leqslant \int\_{\mathbb{R}} \left| e^{-\pi |x|^{2}} - e^{-\frac{\pi}{(1+\varepsilon)^{2}} |x|^{2}} \right| \mathrm{d}x + \int\_{\mathbb{R}} (1 - \frac{1}{1+\varepsilon}) e^{-\frac{\pi}{(1+\varepsilon)^{2}} |x|^{2}} \mathrm{d}x \\ &= \int\_{\mathbb{R}} \left| e^{-\pi |x|^{2}} - e^{-\frac{\pi}{(1+\varepsilon)^{2}} |x|^{2}} \right| \mathrm{d}x + \varepsilon \\ &= \int\_{\mathbb{R}} \left| 1 - e^{-\pi (1 - \frac{1}{(1+\varepsilon)^{2}}) \mathbf{x}^{2}} \right| \cdot e^{-\frac{\pi}{(1+\varepsilon)^{2}} \mathbf{x}^{2}} \mathrm{d}x + \varepsilon. \end{split}$$

For ∀*z* 0, we have

$$1 - z \leqslant e^{-z} \leqslant 1 \Rightarrow 0 \leqslant 1 - e^{-z} \leqslant z,$$

and

$$\left| e^{-\pi (1 - \frac{1}{(1+\varepsilon)^2}) \mathbf{x}^2} - 1 \right| \leqslant \pi (1 - \frac{1}{(1+\varepsilon)^2}) \mathbf{x}^2$$

$$= \frac{\pi}{(1+\varepsilon)^2} (2\varepsilon + \varepsilon^2) \mathbf{x}^2 \leqslant 2\pi \varepsilon \mathbf{x}^2.$$

Finally,

$$\int\_0^1 |\psi\_\alpha(\mathbf{x}) - \psi\_\beta(\mathbf{x})| \mathbf{dx} \lesssim 2\pi\varepsilon \int\_{\mathbb{R}} \mathbf{x}^2 e^{-\frac{\pi}{(1+\varepsilon)^2} \mathbf{x}^2} \mathbf{dx} + \varepsilon = \varepsilon + \varepsilon(1+\varepsilon)^3 \lesssim 9\varepsilon.$$

Since ε = β α − 1, based on (3.3.12),

$$
\Delta(\psi\_{\alpha}, \psi\_{\beta}) = \frac{1}{2} \int\_0^1 |\psi\_{\alpha}(\mathbf{x}) - \psi\_{\beta}(\mathbf{x})| \mathrm{d}x \leqslant \frac{9}{2} (\frac{\beta}{\alpha} - 1).
$$

We complete the proof of this lemma.

In order to obtain the discrete Gauss distribution on Z*q* , we construct a discrete processing technique for continuous random variables. Let T be any interval with length 1 on R, denoted as

$$\mathbb{T} \equiv [0, 1) \pmod{1}.$$

If ϕ(*x*) is the density function of a continuous random variable ϕ on T, we define a discrete random variable ϕ on Z*q* by

$$\overline{\varphi} = \lfloor q\varphi \rceil,\tag{3.3.13}$$

that is, if ϕ takes a value *x* ∈ T, then ϕ takes the value *qx* mod *q*, where *x* is the closest integer to *x*. When *x* runs over [0, 1), obviously *qx* runs over Z*q* , so ϕ defined in (3.3.13) is indeed a discrete random variable on Z*q* . We call ϕ the discretization of ϕ.

**Lemma 3.3.6** *If* ϕ *is a continuous random variable on* T *with the density function* ϕ(*x*)*, then* ϕ *is a discrete random variable on* Z*q , and its probability distribution* ϕ(*k*) *is*

$$\Pr\{\overline{\varphi} = k\} = \overline{\varphi}(k) = \int\_{(k-\frac{1}{2})/q}^{(k+\frac{1}{2})/q} \varphi(\mathbf{x})d\mathbf{x}, \ k \in \mathbb{Z}\_q.$$

*Proof*

$$\Pr\{\overline{\varphi} = k\} = \Pr\{ |q\varphi\overline{\rho}| = k \} = \Pr\left\{ k - \frac{1}{2} \le q\varphi < k + \frac{1}{2} \right\}$$

$$= \Pr\left\{ \left( k - \frac{1}{2} \right) / q \le \varphi < \left( k + \frac{1}{2} \right) / q \right\} = \int\_{\frac{(k - \frac{1}{2}) / q}{(k - \frac{1}{2}) / q}}^{(k + \frac{1}{2}) / q} \varphi(\mathbf{x}) d\mathbf{x}.$$

**Definition 3.3.5** The discrete Gauss distribution ψβ on Z*q* is defined by

$$\overline{\psi}\_{\beta}(k) = \int\_{(k-\frac{1}{2})/q}^{(k+\frac{1}{2})/q} \psi\_{\beta}(\mathbf{x})d\mathbf{x},\tag{3.3.14}$$

where ψβ (*x*) is the continuous Gauss distribution on T in (3.3.9) and β is called the parameter of discrete Gauss distribution.

In the LWE problem, usually we suppose χ = ψβ is a discrete Gauss distribution. The main result in this chapter is the following theorem.

**Theorem 3.3.1** *Let m* = *Poly*(*n*)*, q* - 2*Poly*(*n*) *,* χ = ψα *be the discrete Gauss distribution with parameter* α*, where* 0 <α< 1*, and* α*q* 2 √*n. Then the difficulty of solving the D-LWEn*,*q*,χ ,*m problem is at least as hard as that of GapSVP*γ *or SIVP*γ *problem on any n dimensional full rank lattice L based on quantum algorithm, where* γ = *O*˜( *n* α )*.*

*The proof of Theorem 3.3.1will be given in the next section. Here we only introduce the idea of this proof. The proof of Theorem 3.3.1 is mainly divided into the following two steps:*

#### **3.4 Proof of the Main Theorem**

In this section, we mainly prove that the difficulty of solving D-LWE problem is not lower than that of the hard problem on lattice, that is, if there is a quantum algorithm for solving the D-LWE problem, then there exists a quantum algorithm to solve the hard problem on lattice. The whole proof could be divided into three parts. In order to better understand the three parts of proof, we first introduce the definition of the DGS problem.

**Fig. 3.1** The flowchart of the proof of Theorem 3.3.1

**Definition 3.4.1** DGSφ: given an *n* dimensional lattice *L* with generated matrix *B*, a real number *r* > φ(*B*), where φ is a real function of *B*. The goal is to output a sample from the discrete Gauss distribution *DL*,*r*.

The DGS problem is also called the discrete Gauss sampling problem. We will see that the difficulty of the DGS problem is polynomial equivalent to that of the hard problem on lattice after this proof. Next we introduce the idea of proving that the D-LWE problem is at least as difficult as the hard problem on lattice. This proof could be divided into three parts, which are given in Sects. 3.4.1, 3.4.2 and 3.4.3. In Sect. 3.4.1, we prove that if there is a quantum algorithm to solve the LWE problem, then there is also a quantum algorithm to solve the DGS√2*n*ηε (*L*)/α problem. In Sect. 3.4.2, we give a reduction algorithm from the GIVP2 √*n*φ problem to the DGSφ problem, so that we have completed the proof that the LWE problem is not less difficult than the hard problem on lattice. In Sect. 3.4.3, we further prove that the D-LWE problem D-LWE*n*,*q*,χ ,*m* can be reduced to the LWE*n*,*q*,χ ,*m* problem and complete the proof of Theorem 3.3.1. The flowchart of the whole proof is shown in Fig. 3.1.

#### *3.4.1 From LWE to DGS*

In this subsection, we will solve the DGS√2*n*ηε (*L*)/α problem by the algorithm of LWE*n*,*q*,ψα,*m* problem. The main conclusion is the following Lemma 3.4.1 , and its proof depends on Lemmas 3.4.2 and 3.4.3. We give these three lemmas first.

**Lemma 3.4.1** *Let m* = *Poly*(*n*)*,* ε = ε(*n*) *be a negligible function of n, q* = *q*(*n*) *be a positive integer,* α = α(*n*) ∈ (0, 1)*,* α*q* 2 √*n,* χ = ψα*. Assume that we have an algorithm W that solves the LWEn*,*q*,ψα,*m problem given a polynomial number of samples, then there exists an efficient quantum algorithm for the DGS*√2*n*ηε (*L*)/α *problem.*

**Lemma 3.4.2** *For any n dimensional lattice L and a real number r* > 22*n*λ*n*(*L*)*, there exists an efficient algorithm that outputs a sample from a distribution that is within statistical distance* 2−(*n*) *of the discrete Gauss distribution DL*,*r, where* (*n*) *is a polynomial function or exponential function of n.*

**Lemma 3.4.3** *Let m* = *Poly*(*n*)*,* ε = ε(*n*) *be a negligible function of n, q* = *q*(*n*) 2 *be a positive integer,* α = α(*n*) ∈ (0, 1)*. Assume that we have an algorithm W that solves the LWEn*,*q*,ψα,*m problem given a polynomial number of samples, then there exists a constant c* > 0 *and an efficient quantum algorithm that, given any n dimensional lattice L, a real number r* > √2*q*ηε(*L*) *and nc samples from DL*,*r, outputs a sample from DL*,*r* √*n*/(α*q*)*.*

**Proof of Lemma** √ 3.4.1: Given an *n* dimensional lattice *L* and a real number *r* > 2*n*ηε(*L*)/α, our goal is to output a sample from the discrete Gauss distribution *DL*,*r*. The idea of this proof is to use iteration steps. Let

$$r\_i = r(\alpha q / \sqrt{n})^i, \quad i = 1, 2, \dots, 3n.$$

Based on Lemma 1.3.6 in Chap. 1,

$$r\_{3n} > 2^{3n}r > 2^{3n} \sqrt{2n} \eta\_{\varepsilon}(L)/\alpha \\ \geqslant 2^{3n} \sqrt{2n} \sqrt{\frac{\ln 1/\varepsilon}{\pi}} \frac{\lambda\_n(L)}{n} \\ > 2^{2n} \lambda\_n(L).$$

By Lemma 3.4.2, we can produce samples from the discrete Gauss distribution *DL*,*r*3*n* . Suppose *c* is the constant from Lemma 3.4.3, we output *nc* samples from *DL*,*r*3*n* . According to Lemma 3.4.3, we can get samples from the distribution *DL*,*r*3*n* √*n*/(α*q*), i.e. *DL*,*r*3*n*−1 . Repeat this process, since

$$r\_1 = r\alpha q / \sqrt{n} > \sqrt{2n} \eta\_\ell(L) / \alpha \cdot \alpha q / \sqrt{n} = \sqrt{2} q \eta\_\ell(L),$$

which satisfies the condition of Lemma 3.4.3, finally we can output a sample from *DL*,*r*1 √*n*/(α*q*) = *DL*,*r*. The lemma holds.

**Proof of Lemma** 3.4.2: By the LLL algorithm (Lenstra et al. (1982)), we can choose the generated matrix *B* = [*b*1, *b*2,..., *bn*] of *L* satisfying *bi* - 2*n*λ*n*(*L*), 1 *i n*. Suppose *F*(*B*) is the basic neighborhood of lattice *L*. The algorithm in Lemma 3.4.2 can be achieved by the following steps. First we generate a sample *y* from the discrete Gauss distribution *Dr*, where

$$D\_r(\mathbf{x}) = \frac{\rho\_r(\mathbf{x})}{r^n}, \ \forall \mathbf{x} \in \mathbb{R}^n.$$

We get *y* = *y* mod *L* ∈ *F*(*B*), and *x* = *y* − *y* ∈ *L*. Denote the distribution of *x* as ξ , next we prove the statistical distance between ξ and *DL*,*r* is exponentially small. Note that

$$|y'| \lesssim \text{diam}(F(\mathcal{B})) \lesssim \sum\_{i=1}^n |b\_i| \lesssim n 2^n \lambda\_n(L),$$

where

$$\text{diam}(F(B)) = \max\{|\mu - v| \mid \mu, v \in F(B)\}.$$

Based on Lemma 1.3.4 in Chap. 1,

$$
\rho(L \backslash \sqrt{n} \, N) < (r \sqrt{2\pi e} e^{-\pi r^2})^n \rho(L),
$$

here *N* is the unit ball. This means ρ(*L*\ √*nr N*) is exponentially small, so we can always assume *x* - √*nr*. By Lemma 3.3.4, let *t* = √*nr*, *l* = *n*2*n*λ*n*(*L*), by some simple calculations we get

$$\begin{aligned} \Pr\{\xi = \mathbf{x}\} &= \int\_{\mathbf{x} + F(\mathcal{B})} D\_r(\mathbf{y}) d\mathbf{y} \geqslant \int\_{\mathbf{x} + F(\mathcal{B})} (1 - 2^{-\Omega(n)}) D\_r(\mathbf{x}) d\mathbf{y} \\ &= (1 - 2^{-\Omega(n)}) D\_r(\mathbf{x}) \det(L). \end{aligned}$$

On the other hand, from Lemma 1.3.2 in Chap. 1,

$$\Pr\{D\_{L,r} = \mathbf{x}\} = \frac{\rho\_r(\mathbf{x})}{\rho\_r(L)} = \frac{\rho\_r(\mathbf{x})}{\det(L^\*)r^n\rho\_{1/r}(L^\*)} \lessgtr \frac{\rho\_r(\mathbf{x})}{\det(L^\*)r^n} = D\_r(\mathbf{x})\det(L).$$

So we have

$$\Pr\{\xi = x\} \geqslant (1 - 2^{-\Omega(n)}) \Pr\{D\_{L,r} = x\}.$$

Summing *x* ∈ *L* on both sides, we get the statistical distance between ξ and *DL*,*r* is exponentially small. The lemma holds.

**Definition 3.4.2** (1) CVP*L*,*d* : given an *n* dimensional lattice *L*, a target vector*t* ∈ R*n*, a real number *d*, dist(*t*, *L*) *d*, find *u* ∈ *L* such that

$$|u - t| = \min\_{x \in L, |x - t| \lesssim d} |x - t|.$$

(2) CVP(*q*) *L*,*d* : given an *n* dimensional lattice *L* with generated matrix *B*, a target vector *t* ∈ R*n*, a real number *d*, dist(*t*, *L*) *d*, denote *KL* (*t*) = {*u* ∈ *L* | |*u* − *t*| = min *x*∈*L* |*x* − *t*|}, i.e. *KL* (*t*) is the closest vector to *t* in the lattice *L*, output *B*−1*KL* (*t*) mod *q* ∈ Z*n q* .

The CVP problem is also called the closest vector problem. In order to prove Lemma 3.4.3, we need the following two lemmas, Lemmas 3.4.4 and 3.4.14. In Lemma 3.4.4, we use the samples of *DL*,*r* to solve the CVP*L*∗,α*q*/(√2*r*) problem, and Lemma 3.4.14 shows that we can generate a sample of *DL*,*r* √*n*/α*q* from the algorithm of solving the CVP*L*∗,α*q*/(√2*r*) problem so that we complete the proof of Lemma 3.4.3. The following content is divided into two parts. In the first part, we use Lemmas 3.4.5 to 3.4.11 to prove Lemma 3.4.4, which is to solve the CVP*L*∗,α*q*/(√2*r*) problem based on the samples of *DL*,*r*. In the second part, we prove Lemma 3.4.14 according to Lemmas 3.4.12 and 3.4.13, and achieve the transition from solving CVP*L*∗,α*q*/(√2*r*) to *DL*,*r* √*n*/α*q* .

**Lemma 3.4.4** *Let m* = *Poly*(*n*)*,* ε = ε(*n*) *be a negligible function of n, q* = *q*(*n*) 2 *be a positive integer,* α = α(*n*) ∈ (0, 1)*. Assume that we have an algorithm W that solves LWEn*,*q*,ψα,*m given a polynomial number of samples, then there exists a constant c* > 0 *and an efficient algorithm that, given any n dimensional lattice L, a real number r* > √2*q*ηε(*L*)*, and nc samples from DL*,*r, solves the CVPL*∗,α*q*/(√2*r*) *problem.*

*Proof* This lemma is proved directly by the following Lemmas 3.4.5 to 3.4.11.

Lemma 3.4.5 shows the relationship of difficulty between the CVP and CVP(*q*) problems.

**Lemma 3.4.5** *Given an n dimensional lattice L, a real number d* < λ1(*L*)/2*, q* 2 *is a positive integer. There exists an efficient algorithm to solve the CVPL*,*d problem based on the algorithm for CVP*(*q*) *L*,*d .*

*Proof* Let *x* ∈ R*n* satisfying dist(*x*, *L*) *d* be the target vector, define vectors {*xn*} and {*an*} as follows: *x*1 = *x*,

$$a\_i = B^{-1} K\_L(\mathfrak{x}\_i) \in \mathbb{Z}^n, \ i \gg 1, 2$$

which is the coefficient vector of the closest vector to *xi* in lattice *L*,

$$
\alpha\_{i+1} = (\alpha\_i - B(a\_i \bmod q))/q, \ i \ge 1,
$$

it is easy to prove

$$a\_{i+1} = (a\_i - (a\_i \bmod q))/q, i$$

and

$$|x\_{i+1} - Ba\_{i+1}| \lesssim \frac{d}{q^i}.$$

That is, the distance from *xn*+1 to lattice *L* is no more than *d qn* . Note that *d qn* could be sufficiently small if *n* becomes lager enough. Based on the nearest plane algorithm by Babai (1985), we can find *y* ∈ *L* such that *y* is the closest vector to *xn*+1 in lattice *L*. Let *y* = *Ba*, then *an*+1 = *a*, combine with

$$a\_{i+1} = (a\_i - (a\_i \bmod q))/q,$$

we get *an*, *an*−1,..., *a*1, and complete the process of solving the CVP*L*,*d* problem. This lemma holds.

We introduce the definition of the LWE distribution *As*,χ in Definition 3.3.2, where χ is a distribution on Z*q* . If the value space of χ is changed to T = [0, 1), we can give another definition of LWE distribution.

**Definition 3.4.3** Let *s* ∈ Z*n q* , *e* be a random variable on T with density function φ. The LWE distribution *As*,φ = (*a*, *b*) ∈ Z*n q* × T generated by *s* and φ satisfies:

(1) *a* ∈ Z*n q* is uniformly distributed.

(2) *b* = *a* · *s*/*q* + *e* mod 1.

The LWE distribution we discuss later in this section is always *As*,φ.

**Lemma 3.4.6** *Let q* = *q*(*n*) 1 *be a positive integer, given s* ∈ Z*n q and samples from As*,ψα *for some unknown s* ∈ Z*n q ,* α < 1*. There exists an efficient algorithm that determines whether s* = *s with probability exponentially close to* 1*.*

*Proof* Let (*a*, *x*) be a sample from the LWE distribution *As*,ψα , T = [0, 1), ξ be a random variable on T with density function *p*(*y*) such that

$$
\xi = x - a \cdot s' / q = e + a \cdot (s - s') / q. \tag{3.4.1}
$$

The steps of the algorithm are as follows. Generate *n* samples *y*1, *y*2,..., *yn* of ξ and compute

$$z = \frac{1}{n} \sum\_{i=1}^{n} \cos(2\pi y\_i).$$

If *z* > 0.02, then we confirm *s* = *s* , otherwise, we decide *s* = *s* . Next we prove the correctness of this algorithm.

If*s* = *s* , by (3.4.1) we get ξ = *e* with the distribution ψα. On the other hand, if*s* = *s* , then there is 1 *j n*, such that *sj* = *s j* , where *sj* and *s j* are the *j*th coordinates of *s* and *s* , respectively. Let *g* = gcd(*q*,*sj* − *s j*), *k* = *q*/gcd(*q*,*sj* − *s j*), *aj* be the *j*th coordinate of *a*, it is not hard to see the distribution of *aj*(*sj* − *s j*) mod *q* has period *g*, i.e. the distribution of *aj*(*sj* − *s j*)/*q* mod 1 has period *g*/*q* = 1/*k*, *k* 2. Since ξ is regarded as the sum of *aj*(*sj* − *s j*)/*q* mod 1 and an independent random variable, therefore, the distribution of ξ also has period 1/*k*. Assume *z*˜ is the expectation of cos(2πξ),

86 3 Learning with Error

$$\tilde{z} = E[\cos(2\pi\xi)] = \int\_0^1 \cos(2\pi\chi) p(\mathbf{y}) d\mathbf{y} = \text{Re}\int\_0^1 e^{2\pi i \mathbf{y}} p(\mathbf{y}) d\mathbf{y}.$$

When *s* = *s* , the distribution of ξ is ψα, the right hand of the above formula could be computed as *z*˜ = *e*−πα2 . When *s* = *s* , the distribution of ξ is periodic with period 1/*k*, note that the integral of the periodic function *e*2π*iy p*(*y*) with period 1 is fixed in any interval of length 1, then

$$\begin{aligned} \int\_0^1 e^{2\pi i \mathbf{y}} p(\mathbf{y}) \mathrm{d}\mathbf{y} &= \int\_{\frac{1}{t}}^{1+\frac{1}{t}} e^{2\pi i \mathbf{y}} p(\mathbf{y}) \mathrm{d}\mathbf{y} \\ &= \int\_0^1 e^{2\pi i (\mathbf{y} + \frac{1}{t})} p(\mathbf{y}) \mathrm{d}\mathbf{y} \\ &= e^{\frac{2\pi i}{t}} \int\_0^1 e^{2\pi i \mathbf{y}} p(\mathbf{y}) \mathrm{d}\mathbf{y} .\end{aligned}$$

From *k* 2 we know *z*˜ = 0, by the Chebyshev inequality,

$$\Pr\{|z-\tilde{z}| \leqslant 0.01\} \geqslant 1 - \frac{\text{Var}[\cos(2\pi\xi)]}{0.01^2 n}.$$

The probability of |*z* − ˜*z*| - 0.01 is exponentially close to 1 when *n* is large enough. Thus, we confirm *s* = *s* with probability exponentially close to 1 if *z* - 0.02. We complete the proof.

Based on Lemma 3.4.6 and the algorithm for LWE*n*,*q*,ψα,*m*, for any β α and samples from *As*,ψβ , the following Lemma 3.4.7 gives an algorithm to solve *s* with probability close to 1.

**Lemma 3.4.7** *Let q* = *q*(*n*) 2 *be a positive integer,* α = α(*n*) ∈ (0, 1)*. Assume that we have an algorithm W that solves LWEn*,*q*,ψα,*m with a polynomial number of samples, then there exists an efficient algorithm W to solve s with probability exponentially close to* 1 *for some samples from As*,ψβ *, where* β α *and* β *is unknown.*

*Proof* Assume we need *nc* samples in the algorithm *W*, *c* > 0 is a constant. Let the set *Z* be

$$Z = \{ \boldsymbol{\gamma} \mid \boldsymbol{\gamma} = \delta \boldsymbol{n}^{-2c} \boldsymbol{\alpha}^2 \in [0, \boldsymbol{\alpha}^2], \ \delta \in \mathbb{Z} \}.$$

The steps of algorithm *W* are as follows. For each γ ∈ *Z*, we repeat the following process *n* times. Each time we get *nc* samples from *As*,ψβ and add samples from ψ√γ to the second component of each sample from *As*,ψβ , so we obtain *nc* samples from *As*,ψ√β2+γ . We solve *s* by algorithm *W* and determine whether *s* = *s*. If *s* = *s*, output *s* and we complete the algorithm. Next we prove that the above algorithm could achieve the goal of solving *s* with probability exponentially close to 1. Assume

$$
\Gamma = \min \{ \gamma \in Z, \,\,\chi \geqslant \alpha^2 - \beta^2 \}.
$$

From the definition of the set *Z*

$$
\Gamma \lesssim \alpha^2 - \beta^2 + n^{-2c} \alpha^2.
$$

Let α = β2 + , we have

$$
\alpha \leqslant \alpha' \leqslant \sqrt{\alpha^2 + n^{-2c}\alpha^2} \leqslant (1 + n^{-2c})\alpha.
$$

Based on lemma 3.3.5,

$$
\Delta(\psi\_{\alpha}, \psi\_{\alpha'}) \lesssim \frac{9}{2} \left( \frac{\alpha'}{\alpha} - 1 \right) \lesssim \frac{9}{2} n^{-2c}.
$$

Therefore, the statistical distance between the *nc* samples from ψα and *nc* samples from ψα is no more than 9*n*−*c*, which means the probability that the algorithm *W* solves *s* successfully is at least 1 − 9*n*−*c* 1 2 . It follows that the probability of solving *s* unsuccessfully *n* times is no more than 2−*n*. The lemma holds.

To prove our main result, we need two properties about the Gauss function and statistical distance.

**Lemma 3.4.8** *For any n dimensional lattice L, c* ∈ R*n,* ε > 0*, r* ηε(*L*)*, we have*

$$
\rho\_r(L+c) \in r^n \det(L^\*) (1 \pm \varepsilon). \tag{3.4.2}
$$

*Proof* Based on Lemma 1.3.2 in Chap. 1,

$$\begin{aligned} \rho\_r(L+c) &= \sum\_{x \in L} \rho\_{r, -c}(\mathbf{x}) = \det(L^\*) \sum\_{\mathbf{y} \in L^\*} \hat{\rho}\_{r, -c}(\mathbf{y}) \\ &= r^n \det(L^\*) \sum\_{\mathbf{y} \in L^\*} e^{2\pi i c \cdot \mathbf{y}} \rho\_{1/r}(\mathbf{y}) \\ &= r^n \det(L^\*) (1 + \sum\_{\mathbf{y} \in L^\* \backslash \{0\}} e^{2\pi i c \cdot \mathbf{y}} \rho\_{1/r}(\mathbf{y})). \end{aligned}$$

From *r* ηε(*L*), it follows that ρ1/*r*(*L*∗\{0}) ε, and

#### 88 3 Learning with Error

$$\left| \sum\_{\mathbf{y} \in L^\*\backslash\{0\}} e^{2\pi i c \cdot \mathbf{y}} \rho\_{1/r}(\mathbf{y}) \right| \leqslant \sum\_{\mathbf{y} \in L^\*\backslash\{0\}} \rho\_{1/r}(\mathbf{y}) \leqslant \varepsilon. \square$$

We get

$$\rho\_r(L+c) = r^n \det(L^\*) \left( \mathbf{l} + \sum\_{\mathbf{y} \in L^\* \backslash \{0\}} e^{2\pi i c \cdot \mathbf{y}} \rho\_{1/r}(\mathbf{y}) \right) \in r^n \det(L^\*) (\mathbf{l} \pm \varepsilon).$$

The proof is complete.

**Lemma 3.4.9** *For any n dimensional lattice L, u* ∈ R*n,* ε < 1 2 *, r*,*s are two positive real numbers, t* = √ *r* 2 + *s*2*, assume r s*/*t* = 1/ 1/*r* 2 + 1/*s*2 ηε(*L*)*, let* ξ *be the sum of a discrete Gauss distribution DL*+*u*,*r and a noise distribution Ds, then*

$$
\Delta(\xi, D\_t) \lessapprox 2\varepsilon. \tag{3.4.3}
$$

*Proof* Let the density function of ξ be *Y* (*x*), then

$$\begin{split} Y(\mathbf{x}) &= \frac{1}{s^n \rho\_r(L+u)} \sum\_{\mathbf{y} \in L+u} \rho\_r(\mathbf{y}) \rho\_s(\mathbf{x} - \mathbf{y}) \\ &= \frac{1}{s^n \rho\_r(L+u)} \sum\_{\mathbf{y} \in L+u} \exp\left(-\pi \left( \left| \frac{\mathbf{y}}{r} \right|^2 + \left| \frac{\mathbf{x} - \mathbf{y}}{s} \right|^2 \right) \right) \\ &= \frac{1}{s^n \rho\_r(L+u)} \sum\_{\mathbf{y} \in L+u} \exp\left(-\pi \left( \frac{r^2 + s^2}{r^2 s^2} \left| \mathbf{y} - \frac{r^2}{r^2 + s^2} \mathbf{x} \right|^2 + \frac{1}{r^2 + s^2} |\mathbf{x}|^2 \right) \right) \\ &= \exp\left(-\frac{\pi}{r^2 + s^2} |\mathbf{x}|^2 \right) \frac{1}{s^n \rho\_r(L+u)} \\ &\sum\_{\mathbf{y} \in L+u} \exp\left(-\pi \left( \frac{r^2 + s^2}{r^2 s^2} \left| \mathbf{y} - \frac{r^2}{r^2 + s^2} \mathbf{x} \right|^2 \right) \right) \\ &= \frac{\rho\_1(\mathbf{x})}{s^n} \frac{\rho\_{rJ\_1(\mathbf{y}) \hat{\rho}\_r^\* z - u}(L)}{\rho\_{r^n - u}(L)} \\ &= \frac{\rho\_1(\mathbf{x})}{s^n} \frac{\hat{\rho}\_{rJ\_1(\mathbf{y}) \hat{\rho}\_{rJ\_1}^\* z - u}(L^\*)}{\hat{\rho}\_{r^n - u}(L^\*)}. \end{split}$$

Based on the Fourier transform property of Gauss function in Lemma 1.2.1 in Chap. 1, we get

$$
\hat{\rho}\_{rs/t, (r/t)^2 \mathbf{x} - u}(w) = \exp(-2\pi i ((r/t)^2 \mathbf{x} - u) \cdot w) (rs/t)^n \rho\_{t/rs}(w),
$$

and

$$
\hat{\rho}\_{r,-u}(w) = \exp(2\pi i \boldsymbol{u} \cdot w) r^n \rho\_{1/r}(w).
$$

Since *r r s t* ηε(*L*),

$$|1 - (t/rs)^n \hat{\rho}\_{rs/t, (r/t)^2 x - u}(L^\*)| \leqslant \rho\_{t/rs}(L^\* \backslash \{0\}) \leqslant \varepsilon,$$

$$|1 - (1/r)^n \hat{\rho}\_{r, -u}(L^\*)| \leqslant \rho\_{1/r}(L^\* \backslash \{0\}) \leqslant \varepsilon.$$

It follows that

$$1 - 2\varepsilon \lesssim \frac{1 - \varepsilon}{1 + \varepsilon} \lesssim \frac{(t/rs)^n \widehat{\rho}\_{rs/t, (r/t)^2 x - u}(L^\*)}{(1/r)^n \widehat{\rho}\_{r, -u}(L^\*)} \lesssim \frac{1 + \varepsilon}{1 - \varepsilon} \lesssim 1 + 4\varepsilon.$$

By (3.4.4),

$$|Y(\mathbf{x}) - \frac{\rho\_t(\mathbf{x})}{t^n}| \le 4\varepsilon \frac{\rho\_t(\mathbf{x})}{t^n}.$$

Integrate for *x* ∈ R*n*,

$$\Delta(\xi, D\_t) = \frac{1}{2} \int\_{\mathbb{R}^n} |Y(\mathbf{x}) - \frac{\rho\_t(\mathbf{x})}{t^n}| \mathbf{dx} \lesssim 2\varepsilon.$$

We complete the proof.

**Lemma 3.4.10** *For any n dimensional lattice L, vectors z*, *u* ∈ R*n, real numbers r*,α > 0*,* ε < 1 2 *,* ηε(*L*) - 1/ 1/*r* 2 + (|*z*|/α)2*, let* v *be a random variable of the discrete Gauss distribution DL*+*u*,*r, e be a random variable of Gauss distribution with mean* 0 *and standard deviation* α/√2π*,* ξ *be a random variable of Gauss distribution with mean* 0 *and standard deviation* (*r*|*z*|)2 + α2/ √2π*, then*

$$
\Delta(z \cdot v + e, \xi) \lessapprox 2\varepsilon. \tag{3.4.5}
$$

*In particular,*

$$
\Delta(z \cdot v + e \mod 1, \psi \sqrt{\_{(r|z|)^2 + a^2}}) \lesssim 2\varepsilon. \tag{3.4.6}
$$

*Proof* Let the random variable *h* has distribution *D*α/|*z*|, then the standard deviation of *h* is α/(|*z*| √2π ), and the standard deviation of *z* · *h* is|*z*| · α/(|*z*| √2π ) = α/√2π which is the same as that of *e*. Since both of them have Gauss distributions, we get the distributions of *z* · *h* and *e* are the same, i.e. *z* · v + *e* and *z* · (v + *h*) have the same distribution. Based on Lemma 3.4.9, let *s* = α/|*z*|, it follows that the statistical distance between v + *h* and *D*√*r* 2+(α/|*z*|)2 is no more than 2ε,

$$\Delta(v+h, D\sqrt{r^2+(a/|z|)^2}) \lesssim 2\varepsilon.$$

By the property of statistical distance,

$$\Delta(z \cdot (v+h), z \cdot D\_{\sqrt{r^2 + (\alpha/|z|)^2}}) \lesssim 2\varepsilon.$$

Here the standard deviation of *z* · *D*√*r* 2+(α/|*z*|)2 is

$$|z| \cdot \sqrt{r^2 + (\alpha/|z|)^2} / \sqrt{2\pi} = \sqrt{(r|z|)^2 + \alpha^2} / \sqrt{2\pi},$$

which is the same as that of ξ . Note that both of the two random variables have Gauss distributions; therefore, *z* · *D*√*r* 2+(α/|*z*|)2 and ξ have the same distribution, i.e.

$$
\Delta(z \cdot v + e, \xi) \leqslant 2\varepsilon,
$$

mod 1 for both of the two random variables,

$$\Delta(z \cdot v + e \bmod 1, \psi \sqrt{(r|z|)^2 + a^2}) \lesssim 2\varepsilon.$$

The lemma holds.

**Lemma 3.4.11** *Let* ε = ε(*n*) *be a negligible function of n, q* = *q*(*n*) 2 *be a positive integer,* α = α(*n*) ∈ (0, 1)*. Assume we have an algorithm W to solve s given a polynomial number of samples from As*,ψβ *for any* β α *(*β *is unknown), then there exists an efficient algorithm that given an n dimensional lattice L, a real number r* > √2*q*ηε(*L*) *and a polynomial number of samples from DL*,*r, to solve the CVP*(*q*) *L*∗,α*q*/(√2*r*) *problem.*

*Proof* For a given *x* ∈ R*n*, dist(*x*, *L*∗) α*q*/(√2*r*), denote the generated matrix of *L* is *B*, and the generated matrix of *L*∗ is (*BT* )−1, our goal is to solve *s* = *BT KL*∗ (*x*) mod *q*. The idea of algorithm *W* is to generate a polynomial number of samples from *As*,ψβ , and solve *s* according to the algorithm *W*.

The steps of algorithm *W* are as follows: let v ∈ *L* be a sample from the discrete Gauss distribution *DL*,*r*, *a* = *B*−1v mod *q*, *e* be random variable of Gauss distribution with mean 0 and standard deviation α/(2 √π ), then there is β α such that the statistical distance between (*a*, *x* · v/*q* + *e* mod 1) and *As*,ψβ is negligible. Next we prove the correctness of this algorithm.

Firstly, note that the distribution of *a* is almost uniform, i.e. the statistical distance between *a* and the uniform distribution is negligible. This is because for any *a*0 ∈ Z*n q* , we have

$$\Pr\{a = a\_0\} = \rho\_r(qL + Ba\_0) = \rho\_{r/q}(L + Ba\_0/q).$$

Since *q*ηε(*L*) < *r*, based on Lemma 3.4.8,

$$\Pr\{a = a\_0\} = \rho\_{r/q}(L + Ba\_0/q) \in (r/q)^n \det(L^\*) (1 \pm \varepsilon), \ \forall a\_0 \in \mathbb{Z}\_q^n.$$

This implies *a* is almost uniformly distributed.

Secondly, we consider the distribution of *x* · v/*q* + *e* mod 1. Let *x* = *x* − *KL*∗ (*x*), from dist(*x*, *L*∗) α*q*/(√2*r*) we get |*x* | α*q*/(√2*r*) and

$$1\,\mathrm{x}\cdot\upsilon/q + e\bmod{1} = (\mathrm{x}'/q)\cdot\upsilon + e + K\_{L^\*}(\mathrm{x})\cdot\upsilon/q \text{ mod } 1. \tag{3.4.7}$$

We compute the distributions of *KL*∗ (*x*) · v/*q* mod 1 and (*x* /*q*) · v + *e* , respectively. It is easy to see

$$K\_{L^\ast}(\mathfrak{x}) \cdot v = (\boldsymbol{B}^\mathsf{T} K\_{L^\ast}(\mathfrak{x})) \cdot (\boldsymbol{B}^{-1} v),$$

therefore,

$$K\_{L^\ast}(\mathbf{x}) \cdot v \bmod q = (\boldsymbol{B}^T K\_{L^\ast}(\mathbf{x})) \cdot (\boldsymbol{B}^{-1} v) \bmod q = \boldsymbol{s} \cdot \boldsymbol{a} \bmod q.$$

This means *KL*∗ (*x*) · v/*q* mod 1 and *s* · *a*/*q* mod 1 have the same distribution. In order to get the distribution of (*x* /*q*) · v + *e*, note that v has discrete Gauss distribution *Dq L*+*Ba*,*r*, and *e* has Gauss distribution with mean 0 and standard deviation α/(2 √π ), let β = (*r*|*x* |/*q*)2 + α2/2 α,

$$1/\sqrt{1/r^2 + (\sqrt{2}|\mathbf{x'}|/aq)^2} \ge r/\sqrt{2} > q\eta\_\epsilon(L) = \eta\_\epsilon(qL)$$

satisfies the condition of Lemma 3.4.10. By Lemma 3.4.10,(*x* /*q*) · v + *e* almost has the distribution ψβ and the statistical distance of them is negligible. From (3.4.7), *x* · v/*q* + *e* mod 1 and ψβ + *s* · *a*/*q* mod 1 have the same distribution. Above all, we get the statistical distance between (*a*, *x* · v/*q* + *e* mod 1) and *As*,ψβ is negligible so that the algorithm *W* is correct. We complete the proof.

Combining the above Lemmas 3.4.5, 3.4.7 and 3.4.11, we obtain the conclusion of Lemma 3.4.4 immediately, which shows that we can solve the CVP*L*∗,α*q*/(√2*r*) problem by the samples of *DL*,*r*. In order to prove Lemma 3.4.3 completely, we introduce the technique of quantum computation to prove there is an efficient quantum algorithm to generate a sample from *DL*,*r* √*n*/α*q* based on the algorithm for the CVP*L*∗,α*q*/(√2*r*) problem.

**Definition 3.4.4** For a real number *a* ∈ R and a vector *x* ∈ R*n*, we define the Dirac notation *a*|*x* = *ax*. Let *A* be a finite or countable set in R*n*, *f* be a function from R*n* to R, a quantum state is defined by

$$\sum\_{\mathbf{x}\in A} f(\mathbf{x})|\mathbf{x}\rangle = \sum\_{\mathbf{x}\in A} f(\mathbf{x})\mathbf{x},\tag{3.4.8}$$

if *x*∈*A f* (*x*)*x* converges.

The knowledge about Dirac notation and quantum state is an important part of quantum physics. Since it involves too much content beyond the scope of this book, we will not introduce it in detail. We only provide the Lemmas 3.4.12, 3.4.13 and 3.4.14 here. The readers could refer to Nielsen and Chuang (2000), Shor (1997) for details. The following Lemma 3.4.12 gives the discrete Gauss quantum state on lattice, where the lattice *L* satisfies *L* ⊂ Z*n*.

**Lemma 3.4.12** *Given an n dimensional lattice L* ⊂ Z*n, r* > 22*n*λ*n*(*L*)*, there exists an efficient quantum algorithm to output a state within negligible l*2 *distance from the following state*

$$\sum\_{\mathbf{x}\in L} \sqrt{\rho\_r(\mathbf{x})} |\mathbf{x}\rangle = \sum\_{\mathbf{x}\in L} \rho\_{\sqrt{2}r}(\mathbf{x}) |\mathbf{x}\rangle. \tag{3.4.9}$$

*Let L be an n dimensional lattice, R be a positive number, L*/*R* = {*x*/*R* | *x* ∈ *L*} *be a lattice obtained by scaling down L by a factor of R. The following lemma 3.4.13 claims that the quantum state on lattice is on points of norm at most* √*n.*

**Lemma 3.4.13** *Let R be a positive integer, L be an n dimensional lattice such that* λ1(*L*) > 2 √*n, F be the basic neighborhood of L.* v1 *and* v2 *are defined by*

$$v\_1 = \sum\_{\mathbf{x} \in L/\mathbb{R}, |\mathbf{x}| < \sqrt{n}} \rho(\mathbf{x}) |\mathbf{x} \bmod L\rangle. \tag{3.4.10}$$

*and*

$$\begin{split} v\_2 &= \sum\_{\mathbf{x} \in L/\mathbb{R}} \rho(\mathbf{x}) |\mathbf{x} \bmod L\rangle \\ &= \sum\_{L/\mathbb{R} \cap F} \sum\_{\mathbf{y} \in L} \rho(\mathbf{x} - \mathbf{y}) |\mathbf{x}\rangle. \end{split} \tag{3.4.11}$$

*Then the l*2 *distance between* v1 |v1| *and* v2 |v2| *is negligible.*

The following Lemma 3.4.14 gives an algorithm to generate a sample from *DL*, √*n*/(√2*d*) based on the algorithm for the CVP*L*∗,*d* problem.

**Lemma 3.4.14** *Given an n dimensional lattice L, a real number d* < λ1(*L*∗)/2*, if there exists an algorithm to solve the CVPL*∗,*d problem, then there is an efficient quantum algorithm to generate a sample from the discrete Gauss distribution DL*, √*n*/(√2*d*)*.*

According to Lemma 1.3.6 in Chap. 1, when *r* > √2*q*ηε(*L*), we have

$$
\frac{\alpha q}{\sqrt{2}r} < \frac{\alpha}{2\eta\_\varepsilon(L)} \le \frac{\alpha}{2} \sqrt{\frac{\pi}{\ln(1/\varepsilon)}} \lambda\_1(L^\*) < \frac{\lambda\_1(L^\*)}{2},
$$

replace *d* in Lemma 3.4.14 with α*q*/(√2*r*), then there exists a quantum algorithm to generate a sample from the discrete Gauss distribution *DL*,*r* √*n*/α*q* given the algorithm for the CVP*L*∗,α*q*/(√2*r*) problem.

Combine Lemma 3.4.4 with Lemma 3.4.14, for *r* > √2*q*ηε(*L*), we have proved that one can solve the CVP*L*∗,α*q*/(√2*r*) problem given the algorithm for the LWE*n*,*q*,ψα,*m* problem and a polynomial number of samples from *DL*,*r*, and further to generate a sample from *DL*,*r* √*n*/α*q* , which is the whole proof of Lemma 3.4.3. So far, we get the main Lemma 3.4.1 in this subsection and finish the first part of proof for Theorem 3.3.1, i.e. from the algorithm for LWE*n*,*q*,ψα,*m* problem to solve the DGS√2*n*ηε (*L*)/α problem.

#### *3.4.2 From DGS to Hard Problems on Lattice*

In this subsection, we are to prove that if there is an algorithm to solve the DGS problem, then there exists a probabilistic polynomial algorithm to solve the hard problems on lattice. Take the GIVP problem as an example, that is, find a set *S* = {*si*} ⊂ *L* of *n* linearly independent vectors in *L*, such that

$$|S| = \max |s\_i| \leqslant \wp(n)\phi(B),$$

where γ (*n*) 1 is a function of *n*, *B* is the generated matrix of *L*, φ(*B*) is a real function of *B*. Specially, if φ = λ*n*, then the GIVP problem becomes the SIVP problem. In order to complete the proof of reduction algorithm from the hard problems on lattice to the DGS problem, we introduce the following two lemmas first. Lemma 3.4.15 shows that with a positive probability, the samples from discrete Gauss distribution are not all contained in a given plane with dimension no more than *n*.

**Lemma 3.4.15** *Given an n dimensional lattice L* ⊂ R*n,* ε - 1 10 *, r* √2ηε(*L*)*, let H be a plane in* R*n with dimension no more than n* − 1*, x be a sample from the discrete Gauss distribution DL*,*r, then*

$$\Pr\{\mathbf{x} \notin H\} \ge \frac{1}{10}.$$

*Proof h* = (*h*1, *h*2,..., *hn*) ∈ *H*, without loss of generality, we suppose that *H* is *h*1 = 0, i.e. the plane of all points with the first coordinate 0, let *x* = (*x*1, *x*2,..., *xn*). Consider the expectation *E*[*e*−π(*x*1/*r*)2 ], based on Lemma 1.3.2 in Chap. 1, we have

#### 94 3 Learning with Error

$$\begin{split} & \quad \underset{x \sim D\_{L,r}}{E} \left[ e^{-\pi \left(x\_{1}/r\right)^{2}} \right] \\ & = \frac{1}{\rho\_{r}(L)} \sum\_{x \in L} e^{-\pi \left(\sqrt{2}x\_{1}/r\right)^{2}} e^{-\pi \left(x\_{2}/r\right)^{2}} \dots e^{-\pi \left(x\_{n}/r\right)^{2}} \\ & = \frac{\det(L^{\*})r^{n}}{\sqrt{2}\rho\_{r}(L)} \sum\_{\mathbf{y} \in L^{\*}} e^{-\pi \left(r\mathbf{y}\_{1}/\sqrt{2}\right)^{2}} e^{-\pi \left(r\mathbf{y}\_{2}\right)^{2}} \dots e^{-\pi \left(r\mathbf{y}\_{n}\right)^{2}} \\ & \leq \frac{\det(L^{\*})r^{n}}{\sqrt{2}\rho\_{r}(L)} \rho\_{\sqrt{2}/r}(L^{\*}), \end{split}$$

where *y* = (*y*1, *y*2,..., *yn*) ∈ *L*∗. Since *r*/ √2 ηε(*L*), we get

$$
\rho\_{\sqrt{2}/r}(L^\*) = 1 + \rho\_{\sqrt{2}/r}(L^\*\backslash\{0\}) \lessapprox 1 + \varepsilon.
$$

It follows that

$$\lim\_{\chi \sim D\_{L,r}} [e^{-\pi (x\_{\mathbb{L}}/r)^2}] \lesssim \frac{\det(L^\*)r^n}{\sqrt{2}\rho\_r(L)}(1+\varepsilon).$$

By Lemma 1.3.2 in Chap. 1 again,

$$
\rho\_r(L) = \det(L^\*) r^n \rho\_{1/r}(L^\*) \geqslant \det(L^\*) r^n,
$$

therefore,

$$\,\_{x \sim D\_{L,r}} [e^{-\pi (x\_1/r)^2}] \ll \frac{1+\varepsilon}{\sqrt{2}} < \frac{9}{10}.$$

On the other hand,

$$\begin{aligned} \sideset{}{^{E}}{}{\mathop{E}}\_{D\_{L,r}}[e^{-\pi(\mathbf{x}\_{1}/r)^{2}}] & \geqslant \sum\_{\mathbf{x} \in H, \mathbf{x} \sim D\_{L,r}} \frac{\rho\_{r}(\mathbf{x})}{\rho\_{r}(L)} [e^{-\pi(\mathbf{x}\_{1}/r)^{2}}] \\ &= \sum\_{\mathbf{x} \in H, \mathbf{x} \sim D\_{L,r}} \frac{\rho\_{r}(\mathbf{x})}{\rho\_{r}(L)} = Pr\{\mathbf{x} \in H\}. \end{aligned}$$

According to the above two inequalities,

$$\Pr\{\mathbf{x} \in H\} \leqslant \frac{9}{10},$$

that is,

$$\Pr\{\mathbf{x} \notin H\} \gg \frac{1}{10}.$$

The lemma holds.

Based on Lemma 3.4.15, the following lemma shows that it is possible to find *n* linearly independent vectors from *n*2 independent samples of the discrete Gauss distribution *DL*,*r* with probability close to 1, which provides a guarantee for solving the GIVP problem later.

**Lemma 3.4.16** *Given an n dimensional lattice L* ⊂ R*n,* ε - 1 10 *, r* √2ηε(*L*)*, then the probability that a set of n*2 *vectors chosen independently from DL*,*r contain no n linearly independent vectors is exponentially small.*

*Proof* Let *x*1, *x*2,..., *xn*2 be *n*2 independent samples from *DL*,*r*, for *i* = 1, 2,..., *n* − 1, let *Bi* be the event that

$$\dim \text{span}(\mathbf{x}\_1, \mathbf{x}\_2, \dots, \mathbf{x}\_{in}) = \dim \text{span}(\mathbf{x}\_1, \mathbf{x}\_2, \dots, \mathbf{x}\_{(i+1)n}) < n\dots$$

If none of the events *B*1, *B*2,..., *Bn*−1 happens, then

$$\dim \text{span}(\mathfrak{x}\_1, \mathfrak{x}\_2, \dots, \mathfrak{x}\_{n^2}) = n,$$

i.e. there exists *n* linearly independent vectors in these *n*2 samples. Next we estimate the probability of *Bi* , by Lemma 3.4.15,

$$\Pr\{\mathbf{x}\_j \in \text{span}(\mathbf{x}\_1, \mathbf{x}\_2, \dots, \mathbf{x}\_{in})\} \leqslant \frac{9}{10}, \text{ } \forall in + 1 \leqslant j \leqslant (i+1)n.$$

Thus,

$$\Pr\{\mathbf{x}\_{in+1}, \mathbf{x}\_{in+2}, \dots, \mathbf{x}\_{(i+1)n} \in \text{span}(\mathbf{x}\_1, \mathbf{x}\_2, \dots, \mathbf{x}\_{in})\} \lesssim \left(\frac{9}{10}\right)^n,$$

that is,

$$\Pr\{B\_i\} \leqslant \left(\frac{9}{10}\right)^n, \forall i = 1, 2, \dots, n-1.$$

It follows that

$$\Pr\{\overline{B\_1} \cap \overline{B\_2} \cap \dots \cap \overline{B\_{n-1}}\} = 1 - \Pr\{B\_1 \cup \dots \cup B\_{n-1}\} \geqslant 1 - (n - 1)\left(\frac{9}{10}\right)^n,$$

this means the probability that none of *B*1, *B*2,..., *Bn*−1 happens is close to 1, i.e. the probability that there are *n* linearly independent vectors in these *n*2 independent samples from *DL*,*r* is close to 1. We complete the proof.

Based on the above preparations, let's prove the main conclusion in this subsection.

**Lemma 3.4.17** *Given an n dimensional lattice L,* ε = ε(*n*) - 1 10 *,*φ(*L*) √2ηε(*L*)*, if there exists an algorithm for the DGS*φ *problem, then there is a probabilistic polynomial algorithm to solve the GIVP*2 √*n*φ *problem.*

*Proof* By the LLL algorithm we choose the generated matrix *S* = [*s*1,*s*2,...,*sn*] of lattice *L* such that *si* - 2*n*λ*n*(*L*), 1 *i n*. Let

$$\lambda\_n = |\mathcal{S}| = \max\_{1 \le i \le n} |s\_i|$$

be the length of the longest column vector in *S*, then

$$
\lambda\_n(L) \lesssim \bar{\lambda}\_n \lesssim 2^n \lambda\_n(L).
$$

For each *i* ∈ {0, 1,..., 2*n*}, let *ri* = 2−*i* λ˜ *n*, we generate *n*2 independent samples from *DL*,*ri* based on the algorithm of the DGSφ problem, and the corresponding sets of *n*2 vectors are denoted as *S*0, *S*1,..., *S*2*n*. If λ˜ *n* φ(*L*), we have

$$
\tilde{\lambda}\_n = |\mathcal{S}| \le 2\sqrt{n}\phi(L),
$$

so *S* is a solution of the GIVP2 √*n*φ problem. If φ(*L*) < λ˜ *n*, then there exists *i* ∈ {0, 1,..., 2*n*} such that φ(*L*) *ri* -2φ(*L*) according to Lemma 1.3.6 in Chap. 1,

$$
\tilde{\lambda}\_n \lesssim \mathcal{Z}^n \lambda\_n(L) \lesssim \mathcal{Z}^n n \sqrt{\frac{\pi}{\ln(1/\varepsilon)}} \eta\_\varepsilon(L) \\
< \mathcal{Z}^{2n+1} \phi(L),
$$

combine *r*0 = λ˜ *n* > φ(*L*) with *r*2*n* = 2−2*n*λ˜ *n* < 2φ(*L*), we know there is*ri* satisfying φ(*L*) *ri* - 2φ(*L*). By Lemma 3.4.16, the probability that *Si* contains *n* linearly independent vectors v1, v2,...,v*n* is close to 1. Based on Lemma 1.3.4 in Chap. 1, the probability each v*i* no more than √*nri* - 2 √*n*φ(*L*) is close to 1. Let *V* = [v1, v2,...,v*n*], we get |*V*| - 2 √*n*φ(*L*), so we find a solution of the GIVP2 √*n*φ problem. This lemma holds.

In Chap. 2, we have proved that the hard problems on lattice such as the GIVP and GapSIVP problems can be reduced to the SIS problem, so the difficulties of solving the hard problems on lattice are the same. In Lemma 3.4.17, we prove that if there is an algorithm for the DGS problem, then there is a probabilistic polynomial algorithm to solve the GIVP problem with positive probability, which can also solve the other hard problems on lattice. So far we have completed the second part of the proof of Theorem 3.3.1. In the first part, we have proved that if there is an algorithm for the LWE problem, then there exists a quantum algorithm to solve the DGS problem. Combining the two parts of the proof, we get the feasibility to solve the hard problems on lattice based on the algorithm for solving the LWE problem, that is, the difficulty of solving the LWE problem is not lower than that of the hard problems on lattice.

#### *3.4.3 From D-LWE to LWE*

In this subsection, we will finish the third part of the proof for Theorem 3.3.1, i.e. the difficulty of the D-LWE problem is at least as high as that of the LWE problem, which is given in the following Theorem 3.4.1.

**Theorem 3.4.1** *Let n* 1 *be a positive integer,* 2 *q* - *Poly*(*n*) *be a prime number,* χ *be a distribution on* Z*q . Assume that we have an algorithm W to determine a sample from the LWE distribution As*,χ *or the uniform distribution U with probability close to* 1*, then there exists an algorithm W to solve s given some samples from the LWE distribution As*,χ *with probability close to* 1*.*

*Proof* Let *s* = (*s*1,*s*2,...,*sn*) ∈ Z*n q* , we give the steps for solving *s*1 of the algorithm *W* , and *s*2,...,*sn* could be solved in the same way. For *k* ∈ Z*q* , consider the following transformation of the LWE sample (*a*, *b*), where *a* is uniformly distributed on Z*n q* , *b* = *a* · *s* + *e*, *e* ← χ,

$$(a,b)\longrightarrow(a+(l,0,\ldots,0),b+lk),$$

here *l* ∈ Z*q* is uniformly distributed. If *k* = *s*1, then

$$b + lk = a \cdot s + e + ls\_1 = (a + (l, 0, \dots, 0)) \cdot s + e,$$

note that *a* + (*l*, 0,..., 0) is also uniform on Z*n q* , therefore, (*a* + (*l*, 0,..., 0), *b* + *lk*) has the LWE distribution *As*,χ .

On the other hand, if *k* = *s*1, at this time *lk* and *b* are independent, based on *l* is uniform on Z*q* , it follows that *lk* is also uniform on Z*q* . By Lemma 3.3.2, we get *b* + *lk* is uniform on Z*q* , so (*a* + (*l*, 0,..., 0), *b* + *lk*) is uniform. By the algorithm *W*, we determine (*a* + (*l*, 0,..., 0), *b* + *lk*)is from the LWE distribution *As*,χ or the uniform distribution, and check whether*s*1 is equal to *k*. Since the number of possible values of *k* is *q*, we can always find the solution of *s*1. After solving *s*2,*s*3,...,*sn* in the same way, we get the solution *s*. The lemma holds.

In Theorem 3.4.1, we prove that the difficulty of the D-LWE problem is not lower than that of the LWE problem and complete the whole proof of Theorem 3.3.1. The difficulty from solving the D-LWE problem to the LWE problem, then to the hard problems on lattice does not increase. We will further discuss the LWE cryptosystem with the probability of decryption error in the next chapter.

**Open Access** This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.

The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.

# **Chapter 4 LWE Public Key Cryptosystem**

In 2005, O.Regev proposed the first LWE public key cryptosystem at Tel Aviv University in Israel based on LWE distribution *As*,χ . Because of this paper, Regev won the highest award for theoretical computer science in 2018—the Godel Award. The size of public key is *O*˜(*n*2) bits, and the size of private key *s* and ciphertext is *O*˜(*n*) bits. The plaintext encrypted each time is 1 bit. In fact, the LWE public key cryptosystem is a probabilistic cryptosystem, which depends on a high probability algorithm. Since the security of LWE problem has been clearly proved (see Chap. 3), the LWE cryptosystem has received extensive attention as soon as it was proposed, and it becomes the most cutting-edge research topic in the lattice-based cryptosystem study.

#### **4.1 LWE Cryptosystem of Regev**

Let *n* - 1, *q* - 2 be positive integers, χ be a given probability distribution in Z*q* . By Definition 4.3.1 in Chap. 3, the LWE distribution *As*,χ is

$$\begin{cases} A\_{s,\chi} = (a,b) \in \mathbb{Z}\_q^n \times \mathbb{Z}\_q, \\ b \equiv\_{\chi}  +e \pmod{q}, \end{cases} \tag{4.1.1}$$

where *a* ∈ Z*n q* is uniformly distributed, *s* ∈ Z*n q* is the private key chosen at random, *e* ∈ Z*q* , *e* ← χ is called error distribution. LWE cryptosystem depends on LWE distribution *As*,χ , and its workflow has the following three steps:

(1) Public key.

First we choose *s* ∈ Z*n q* at random as the private key, let *m* = *O*(*n*log*q*). Then we choose *m* samples distributed from *As*,χ , (*ai*, *bi*) ∈ Z*n q* × Z*q* , *ei* ∈ Z*q* , *ei* ← χ, 1 *i m*. Let

$$\overline{A} = [a\_1, a\_2, \dots, a\_m]\_{n \times m} \in \mathbb{Z}\_q^{n \times m},$$

© The Author(s) 2023

Z. Zheng et al., *Modern Cryptography Volume 2*, Financial Mathematics and Fintech, https://doi.org/10.1007/978-981-19-7644-5\_4

99

$$b = \begin{pmatrix} b\_1 \\ b\_2 \\ \vdots \\ b\_m \end{pmatrix}, \ e = \begin{pmatrix} e\_1 \\ e\_2 \\ \vdots \\ e\_m \end{pmatrix}, \ e \leftarrow \chi^m, \ $$

where *A* is a matrix uniformly at random, *e* ← χ*m* indicates the *m* samples are independent. The public key of LWE cryptosystem is the following (*n* + 1) × *m* matrix

$$A = \begin{pmatrix} \overline{A} \\ b' \end{pmatrix} \in \mathbb{Z}\_q^{(n+1)\times m}.\tag{4.1.2}$$

If the uniformly random matrix *A* is given and saved for all the users of LWE

cryptosystem, then the true public key is *b* = ⎛ ⎜ ⎜ ⎜ ⎝ *b*1 *b*2 . . . *bm* ⎞ ⎟ ⎟ ⎟ ⎠ ∈ Z*m q* with size *O*(*m*) = *O*˜(*n*).

The public key and private key satisfy the following equation:

$$(-s', 1)A \equiv\_\chi e' \pmod{q}.\tag{4.1.3}$$

(2) Encryption.

In order to encrypt plaintext of 1 bit *u* ∈ Z2, let *x* ∈ {0, 1}*m* be an uniformly distributed *m* dimensional vector with each entry 0 or 1. The ciphertext *c* ∈ Z*n*+1 *q* is an (*n* + 1) dimensional vector in Z*q* , defined by

$$f\_A(\mu) = c = Ax + \begin{pmatrix} 0 \\ \mu \cdot \lfloor \frac{q}{2} \rceil \end{pmatrix} \in \mathbb{Z}\_q^{n+1},\tag{4.1.4}$$

where 0 = ⎛ ⎜ ⎜ ⎜ ⎝ 0 0 . . . 0 ⎞ ⎟ ⎟ ⎟ ⎠ ∈ Z*n q* , *u q* 2 ∈ Z*q* , *q* 2 is the nearest integer to *q* 2 . We call *f A* the

encryption algorithm of LWE. In order to understand the encryption algorithm better, we give another definition of *f A*.

The following set {1, 2,..., *m*} has 2*m* subsets. We choose a subset *S* ⊂ {1, 2,..., *m*} uniformly at random which is called the index set. Then the encryption algorithm *f A*(*u*) for plaintext *u* ∈ Z2 is

$$c = f\_A(u) = \begin{pmatrix} \sum\_{i \in S} a\_i \\ \sum\_{i \in S} b\_i + \mu \lfloor \frac{q}{2} \rfloor \end{pmatrix} \in \mathbb{Z}\_q^{n+1}.\tag{4.1.5}$$

In fact, the subset *S* is corresponding to the uniformly chosen vector *x* ∈ {0, 1}*m*. The above algorithm (4.1.5) was proposed by Regev originally.

#### (3) Decryption.

We use the private key *s* ∈ Z*n q* for decryption of the ciphertext *c*. Actually we only need to decrypt for the last entry of vector *c*. We have

$$\,\_1f\_A^{-1}(c) = (-s', 1)c = (-s', 1)Ax + \mu \lfloor \frac{q}{2} \rfloor \equiv\_\chi e'x + \mu \lfloor \frac{q}{2} \rfloor \pmod{q}.\tag{4.1.6}$$

The error samples are much smaller than *q*, namely

$$\sum\_{i \in S} e\_i = e' \ge \lnot \frac{q}{2} \mathbb{I}/2. \tag{4.1.7}$$

Therefore, by comparing the distances between the right side of (4.1.6) and 0 or *q* 2 , one can decrypt successfully:

$$f\_A^{-1}(c) = \begin{cases} 0, \text{ if } (-s', 1)c \text{ is closer to } 0, \\ 1, \text{ if } (-s', 1)c \text{ is closer to } \lfloor \frac{q}{2} \rfloor, \end{cases} \tag{4.1.8}$$

finally we have *f* −1 *A* (*c*) = *u* and finish the whole workflow of LWE cryptosystem.

Both of the encryption algorithm and decryption algorithm of LWE are probabilistic algorithms, so we should verify the correctness, namely

$$\Pr\{f\_A^{-1}(c) = \mu\} \geqslant 1 - \delta(n). \tag{4.1.9}$$

Here δ(*n*) is a negligible function of *n*, i.e. δ(*n*) = *o* 1 log*n* , ∀ > 0, more precisely:

$$\lim\_{n \to \infty} \delta(n) \log^{\epsilon} n = 0, \; \forall \epsilon > 0.$$

We prove (4.1.9) with given discrete Gauss distribution χ = ψα. For *a* ∈ Z*q* , Z*q* = {0, 1,..., *q* − 1},

$$|a| = \begin{cases} a, \text{ if } 0 < a \leqslant \lfloor \frac{q}{2} \rceil, \\ q - a, \text{ if } \lfloor \frac{q}{2} \rceil < a \leqslant q - 1. \end{cases} \tag{4.1.10}$$

For *x* ∈ T = [0, 1), we define

$$|\mathbf{x}| = \begin{cases} \mathbf{x}, & \text{if } 0 \le \mathbf{x} < \frac{1}{2}, \\ 1 - \mathbf{x}, & \text{if } \frac{1}{2} \le \mathbf{x} < 1. \end{cases} \tag{4.1.11}$$

**Lemma 4.1.1** *Let* δ > 0*,* 0 *k m, if the distribution* χ*k satisfies*

$$\Pr\_{e \sim \chi^k} \left\{ |e| < \lfloor \frac{q}{2} \rceil / 2 \right\} > 1 - \delta,\tag{4.1.12}$$

*then (4.1.9) holds, i.e.*

$$\Pr\left\{f\_A^{-1}(c) = \mu\right\} > 1 - \delta.$$

*Proof* When we choose the error samples *ei* ∈ Z*q* , *ei* ← χ, we can always guarantee *ei* = |*ei*| without changing the probability distribution. By (4.1.7), suppose that |*S*| = *k*, the corresponding sample

$$e = \begin{pmatrix} e\_1 \\ e\_2 \\ \vdots \\ e\_k \end{pmatrix}, \ |e| = \sum\_{i=1}^k |e\_i| = \sum\_{i=1}^k e\_i.$$

As long as (4.1.7) holds, i.e.

$$|e| < \lfloor \frac{q}{2} \rfloor / 2 \Rightarrow f\_A^{-1}(c) = \mu,$$

then

$$\Pr\left\{f\_A^{-1}(c) = u\right\} \geqslant \Pr\left\{|e| < \lfloor \frac{q}{2} \rceil/2\right\} \geqslant 1 - \delta.$$

Next we prove (4.1.12) holds for discrete Gauss distribution ψα in Z*q* . The following assumptions are made for the selection of parameters:

$$\begin{cases} n \geqslant 1, \ q \geqslant 2, \ n^2 \leqslant q \leqslant 2n^2, \\ m = (1+\epsilon)(n+1)\log q, \ \epsilon > 0 \text{ is any positive real number}, \\ \chi = \overline{\psi}\_{a(n)}, \ \alpha(n) = o(\frac{1}{\sqrt{n\log n}}), \end{cases} \tag{4.1.13}$$

where the symbol *o* indicates

$$\lim\_{n \to 0} \alpha(n)\sqrt{n}\log n = 0.$$

For example, we can choose α(*n*) = 1 √*n*log2*n* , or

$$\alpha(n) = \left(\sqrt{n}\log^{1+\epsilon}n\right)^{-1}, \ \forall \epsilon > 0.1$$

**Lemma 4.1.2** *Under the condition for parameters of (4.1.13), for any* 0 *k m, we have*

$$\Pr\_{e \sim \overline{\mathcal{V}}\_{a(n)}^k} \left\{ |e| < \lfloor \frac{q}{2} \rceil / 2 \right\} > 1 - \delta(n), \tag{4.1.14}$$

*where* δ(*n*) = *o* 1 *logn ,* ∀ > 0*, is a negligible function.* *Proof* Based on (4.1.13), when *n n*0, it is easy to see that

$$0 \le k \le m \le 4(1+\epsilon)(n+1)\log n < \frac{n^2}{32} \le \frac{q}{32}.$$

The *k* samples *e* = ⎛ ⎜ ⎝ *e*1 . . . *ek* ⎞ ⎟ ⎠ distributed as ψ*k* α could be obtained from the *k* samples

*x*1, *x*2,..., *xk* of distribution ψα, where

$$x\_i \in \left[0, \frac{1}{2}\right), \ e\_i = \lfloor qx\_i \rceil \bmod q, \ 1 \le i \le k.$$

Here the set of representative elements of Z*q* is

$$\mathbb{Z}\_q = \left\{ a \in \mathbb{Z} \mid -\frac{q}{2} \leqslant a < \frac{q}{2} \right\}.$$

So we have

$$|e| = \sum\_{i=1}^{k} |e\_i| = \sum\_{i=1}^{k} |qx\_i| \bmod q.$$

Note that

$$\sum\_{i=1}^k \left( \lfloor qx\_i \rceil - qx\_i \right) \bmod q \le k \le \frac{q}{32}.$$

Therefore,

$$\sum\_{i=1}^k q x\_i \bmod q \lessapprox \frac{q}{16} \Rightarrow \left(\sum\_{i=1}^k x\_i\right) \bmod 1 \lessapprox \frac{1}{16},$$

we have |*e*| < *q* 2 /2. Since *k i*=1 *xi* mod 1 distributed as ψ√*k*α, where √*k* · α = *o* √ 1 log*n* , so

$$\Pr\left\{\sum\_{i=1}^{k} x\_i \bmod 1 < \frac{1}{16}\right\} = 1 - \delta(n),$$

where δ(*n*) = √*k* · α = *o* √ 1 log*n* . We complete the proof.

#### **4.2 The Proof of Security**

To prove the security of Regev's cryptosystem, we first prove some general properties for the probability distribution of Abel group by Impagliazzo and Zurkerman Impagliazzo and Zuckerman (1989).

 For any *l* elements *g*1, *g*2,..., *gl* ∈ *G*, suppose *x* ∈ {0, 1} *l* , *g* = (*g*1, *g*2,..., *gl*), then

$$\lg x = \sum\_{i=1}^{l} x\_i g\_i, \ x\_i = 0 \text{ or } 1$$

is called a subsum of {*g*1, *g*2,..., *gl*}. Randomly choose *x* ∈ {0, 1} *l* , let *gx* denote the distribution of subsum, and let *U*(*G*) denote the uniformly distribution on *G*.

**Lemma 4.2.1** *For any l elements* {*g*1, *g*2,..., *gl*} *uniformly at random, the expectation of statistical distance between the distribution of subsum and the uniformly distribution on U*(*G*) *is*

$$E(\Delta(\mathbf{g}x, U(G))) \lesssim (|G|/2^l)^{\frac{1}{2}}.$$

*Specially, the probability that the statistical distance is larger than* (|*G*|/2*l* ) 1 4 *is no more than* (|*G*|/2*l* ) 1 4 *, i.e.*

$$\Pr\left\{\Delta(\text{gx}, U(G)) \geqslant (|G|/2^l)^{\frac{1}{4}}\right\} \leqslant (|G|/2^l)^{\frac{1}{4}}.$$

*Proof* Let *g* = (*g*1, *g*2,..., *gl*) be *l* group elements chosen at random, *h* ∈ *G* is a given group element. Define *Pg*(*h*)

$$P\_{\mathbf{g}}(h) = \frac{1}{2^l} \left| \left\{ \mathbf{x} \in \{0, 1\}^l \mid \mathbf{g}\mathbf{x} = \sum\_{i=1}^l \mathbf{x}\_i \mathbf{g}\_i = h \right\} \right|,$$

we call *Pg*(*h*) the distribution of subsum for *g*. In order to prove *Pg*(*h*) is close to uniformly distribution, we first prove the *l*2 norm between *Pg*(*h*) and the uniformly distribution is very small. In fact, we have:

$$\sum\_{h \in G} P\_{\mathbf{g}}(h)^2 = \Pr\_{\mathbf{x}, \mathbf{x}'} \{ \mathbf{g}\mathbf{x} = \mathbf{g}\mathbf{x}' \} = \frac{1}{2^l} + \Pr\_{\mathbf{x}, \mathbf{x}'} \{ \mathbf{g}\mathbf{x} = \mathbf{g}\mathbf{x}', \ \mathbf{x} \neq \mathbf{x}' \}.$$

Note that for any *x* = *x* ,

$$\Pr\_{\mathbf{g}}\{\mathbf{g}\mathbf{x}=\mathbf{g}\mathbf{x}'\}=\frac{1}{|G|}.$$

So the expectation of *l*2 norm for *g* satisfy

$$E\left[\sum\_{h\in G} P\_{\mathfrak{g}}(h)^2\right] \le \frac{1}{2^l} + \frac{1}{|G|}.$$

Finally, we have the following estimation

$$\begin{split} &E\left[\sum\_{h\in G} \left| P\_{\mathcal{S}}(h) - \frac{1}{|G|} \right|^{\frac{1}{2}} \right] \\ &\leqslant E\left[|G|^{\frac{1}{2}} \left(\sum\_{h\in G} \left(P\_{\mathcal{S}}(h) - \frac{1}{|G|}\right)^2\right)^{\frac{1}{2}}\right] \\ &= |G|^{\frac{1}{2}} \,\_{\mathcal{S}} E\left[\left(\sum\_{h\in G} P\_{\mathcal{S}}(h)^2 - \frac{1}{|G|}\right)^{\frac{1}{2}}\right] \\ &= |G|^{\frac{1}{2}} \left[E\left(\sum\_{\mathcal{S}} P\_{\mathcal{S}}(h)^2\right) - \frac{1}{|G|}\right]^{\frac{1}{2}} \\ &\leqslant (|G|/2^{l})^{\frac{1}{2}}. \end{split}$$

We complete the proof.

The security of LWE public key cryptosystem by Regev is ascribed to the following theorem, which is the most important result in this chapter.

**Theorem 4.2.1** *For any* > 0*, m* - (1 + )(*n* + 1)*logq, if there is a probabilistic polynomial time algorithm W which distinguishes the plaintext u* = 0 *or u* = 1 *from the ciphertext c, then there exists a polynomial time algorithm solving the D-LWEn*,*q*,χ ,*m problem.*

*Proof* The public key of LWE cryptosystem is *A* = *A b* , where *A* ∈ Z*n*×*m q* is a

matrix uniformly at random, *b* = ⎛ ⎜ ⎝ *b*1 . . . *bm* ⎞ ⎟ ⎠ ∈ Z*m q* is an *m* dimensional vector chosen

uniformly. The encryption function *f A*(*u*) is

$$c = f\_A(u) = Ax + \begin{pmatrix} 0 \\ u \lfloor \frac{q}{2} \rfloor \end{pmatrix} \in \mathbb{Z}\_q^{n+1}, \ x \in \{0, 1\}^m.$$

Since *W* is a probabilistic polynomial time algorithm, suppose *P*0(*W*) is the probability that decrypting *u* = 0 from *f A*(0) by *W*, and *P*1(*W*) is the probability that decrypting *u* = 1 from *f A*(1), i.e.

$$\begin{cases} P\_0(W) = \Pr\{W(f\_A(0)) = 0\}. \\ P\_1(W) = \Pr\{W(f\_A(1)) = 1\}. \end{cases} \tag{4.2.1}$$

If *b* ∈ Z*m q* is uniformly at random, then LWE distribution *As*,χ is uniformly LWE distribution. Let *Pu* (*W*) be the probability of decryption successfully by *W* under the condition of uniformly distribution *As*,χ . Suppose that

$$|P\_0(W) - P\_1(W)| \geqslant \frac{1}{n^{\delta}}, \ \delta \text{ > 0.}\tag{4.2.2}$$

Under the assumption of (4.2.2), we will construct a new algorithm *W* satisfying

$$|P\_0(W') - P\_u(W')| \gtrsim \frac{1}{2n^\delta}.\tag{4.2.3}$$

By (4.2.2), we have

$$|P\_0(W) - P\_u(W)| \geqslant \frac{1}{2n^\delta}, \text{ or } |P\_1(W) - P\_u(W)| \geqslant \frac{1}{2n^\delta}.$$

If the first inequality of the above formula holds, let *W* = *W*. If the second inequality of the above formula holds, then construct *W* as follows. Let the function σ be *f A*(*u*) → *f A*(*u*) + 0 *q*−1 2 .

Thus, σ maps the LWE distribution (*A*, *b*) to (*A*, *b* + *q*−1 2 ). If *b* is uniformly at random, so is *b* + *q*−1 2 . We define *W* to be the decryption on LWE distribution (*A*, *b* + *q*−1 2 ) by *W*. According to (4.1.5),

$$P\_0(W) = P\_1(W'), \ P\_1(W) = P\_0(W'),$$

so *W* is the algorithm which satisfies (4.2.3).

Let *s* ∈ Z*n q* , the public key sample satisfies distribution of (*A*, *b*) ∈ Z*n*×*m q* × Z*m q* = *As*,χ . Let *P*0(*s*) be the probability of decryption *u* = 0 successfully by *W* , i.e.

$$P\_0(\mathbf{s}) = \Pr\{W'(f\_A(\mathbf{0})) = 0\}.$$

Similarly, let *Pu*(*s*) be the probability of decryption successfully by *W* if (*A*, *b*) is uniformly at random. Suppose

$$|\, \_E[P\_0(s)] - \, \_E[P\_u(s)]| \geqslant \frac{1}{2n^\delta},\tag{4.2.4}$$

we define

$$Y = \left\{ \mathbf{s} \in \mathbb{Z}\_q^n \mid \left| P\_0(\mathbf{s}) - P\_u(\mathbf{s}) \right| \geqslant \frac{1}{4n^\delta} \right\}.\tag{4.2.5}$$

It's easy to prove: if *s* ∈ Z*n q* is uniformly distributed, then we have

$$|Y|/q^n \geqslant \frac{1}{4n^\delta}.$$

Therefore, in order to prove Theorem 4.2.1, we need to find an algorithm *Z* to determine whether the LWE distribution *As*,χ is uniformly at random for any *s* ∈ *Y* . The construction of algorithm *Z*: let *R* be a probability distribution on Z*n q* which is uniform LWE distribution or general LWE distribution when *s* ∈ *Y* , i.e.

*R* = uniform LWE distribution, or *R* = *As*,χ , *s* ∈ *Y*.

$$\text{Let } \overline{A} = [a\_1, \dots, a\_m] \in \mathbb{Z}\_q^{n \times m}, \, b = \begin{pmatrix} b\_1 \\ \vdots \\ b\_m \end{pmatrix} \in \mathbb{Z}\_q^m \text{ be } m \text{ random samples from disjunction.} $$

tribution *R*. Let *P*0(*R*) be the probability of decryption *u* = 0 successfully by *W* , where (*a*, *b*) = *As*,χ , *s* ∈ *Y* . In the same way, suppose *Pu* (*R*) is the probability of decryption *u* = 0 successfully by *W* if *R* is uniform LWE distribution. We estimate *P*0(*R*) and *Pu* (*R*) by using the algorithm *W* polynomial times so that the error could be controlled within 1 64*n*δ . If |*P*0(*R*) − *Pu* (*R*)| - 1 16*n*δ , then the algorithm *Z* is effective, otherwise it is noneffective.

We first confirm: if *R* is uniform LWE distribution, then *Z* is noneffective with high probability. Because in this case,(*A*, *b*) ∈ Z*n*×*m q* × Z*m q* , *b* is uniformly at random. According to Lemma 4.2.1, the Abel group *G* = Z*n q* × Z*q* , we have

$$|P\_0(R) - P\_\mathfrak{u}(R)| \leqslant 2^{-\Omega(n)},$$

In this case, *Z* is noneffective.

If *R* = *As*,χ , where *s* ∈ *Y* , we are to prove the algorithm *Z* is effective with probability 1 Poly(*n*); i.e. one can distinguish *s* ∈ *Y* from uniform distribution. Since |*P*0(*R*) − *Pu*(*R*)| - 1 4*n*δ , in the average sense we get

$$\Pr\left\{|P\_0(R) - P\_u(R)| \geqslant \frac{1}{8n^\delta}\right\} \geqslant \frac{1}{8n^\delta}.$$

Thus, the algorithm *Z* is effective for *As*,χ , *s* ∈ *Y* with positive probability. We complete the proof of Theorem 4.2.1.

#### **4.3 Properties of Rounding Function**

The public key of LWE cryptosystem by Regev is *A* = *A b* ∈ Z(*n*+1)×*m q* , where ⎛ ⎞

*A* ∈ Z*n*×*m q* is a matrix uniformly at random, *b* = ⎜ ⎝ *b*1 . . . *bm* ⎟ ⎠ ∈ Z*m q* is a uniform sample

vector (see 4.1.2). In this section we will discuss the sampling technique of public key *A* based on rounding function.

For ∀*x* ∈ R, let {*x*} be the fractional part of *x*, *x* be the closest integer to *x*, i.e.

$$\mathbb{I}\left[x\right] = \begin{cases} x - \{x\}, \text{ if } 0 \leqslant \{x\} \leqslant \frac{1}{2}.\\ x + 1 - \{x\}, \text{ if } \frac{1}{2} < \{x\} < 1. \end{cases} \tag{4.3.1}$$

In fact, *x* is the only integer satisfying

$$\{x = \lfloor x \rfloor + r, \ -\frac{1}{2} < r \leqslant \frac{1}{2}, \text{ if } r = \frac{1}{2} \Leftrightarrow \{x\} = \frac{1}{2}.\tag{4.3.2}$$

We call *x* rounding function, and its properties could be summarized as the following two lemmas.

$$\begin{array}{ll}\textbf{Lemma 4.3.1} & (i)\ \lfloor x+n \rfloor = n+\lfloor x \rceil, n \in \mathbb{Z}, x \in \mathbb{R}.\\ & (ii)\ \lfloor -x \rfloor = \begin{cases} -\lfloor x \rfloor, \text{ if } \{x\} \neq \frac{1}{2}.\\ -1-\lfloor x \rfloor, \text{ if } \{x\} = \frac{1}{2}.\\ \text{(iii)} \text{ For any integers } a, b \in \mathbb{Z}, \ b \neq 0, \text{ we have the following division:}\\ a = \lfloor \frac{a}{n} \rfloor b+r, \text{ where } -\frac{b}{2} < r \le \frac{b}{2}.\\ & (iv)\ \lfloor x \rfloor + \lfloor y \rfloor - 1 \leqslant \lfloor x+y \rfloor \leqslant \lfloor x \rfloor + \lfloor y \rfloor + 1, \forall x, y \in \mathbb{R}.\\ & (v)\ \lfloor \frac{\lfloor x \rfloor}{n} \rfloor = \lfloor \frac{x}{n} \rfloor, \forall n \in \mathbb{Z}, n \geqslant 1, x \in \mathbb{R}.\end{array}$$

*Proof* By (4.3.2),

$$
\lfloor x+n \rceil = \lfloor \lfloor x \rceil + r + n \rfloor = n + \lfloor x \rfloor,
$$

so (i) holds. If {*x*} = 1 2 , then *r* = 1 2 , and −1 2 < *r* < 1 2 , we have

$$
\lfloor -x \rceil = \lfloor -\lfloor x \rceil - r \rceil = -\lfloor x \rfloor.
$$

If *r* = 1 , then {*x*} = 1 , and 1 − *r* = 1 , so that

$$
\lfloor -x \rceil = \lfloor -\lfloor x \rceil - 1 + 1 - r \rceil = -1 - \lfloor x \rceil,
$$

we have (ii). Property (iii) and (iv) can be proved similarly. To prove (v), let *x* = *x* + *r*, then − 1 2*n* < *r n* 1 2*n* , thus,

$$\lfloor \frac{x}{n} \rceil = \lfloor \frac{\lfloor x \rceil}{n} + \frac{r}{n} \rceil = \frac{\lfloor x \rfloor}{n}.$$

Lemma 4.3.1 holds.

**Definition 4.3.1** Let *t* and *q* be two positive integers, we define function *f* : Z → Z as

$$f(a) = \lfloor \frac{q}{t} a \rfloor, \ \forall a \in \mathbb{Z}. \tag{4.3.3}$$

**Lemma 4.3.2** *Let a*, *b* ∈ Z*, then*

$$a \equiv b \pmod{t} \Rightarrow f(a) \equiv f(b) \pmod{q} .$$

*Proof* Since *a* ≡ *b* (mod *t*), we write *a* = *st* + *b*, therefore

$$\mathbb{E}[f(a) = \lfloor \frac{q}{t}(st + b) \rceil] = \lfloor sq + \frac{q}{t}b \rceil = sq + \lfloor \frac{q}{t}b \rceil = sq + f(b).$$

So we have *f* (*a*) ≡ *f* (*b*) (mod *q*).