خرید و دانلود نسخه کامل کتاب Modern Cryptography Volume 2 A Classical Introduction to Informational and Mathematical Principle – Original PDF

1.3 Smoothing Parameter 13 1.3 Smoothing Parameter For a given full-rank lattice L ⊂ Rn , in the previous section we defined the dis- crete Gauss measure g L ,s,c(x), and the corresponding continuous random variable D s,c mod L on the basic neighborhood F(B) of L. In this section, we discuss an important parameter on Gauss lattice—the smoothing parameter. The concept of smooth parameters was introduced by Micciancio and Regev in 2007 Micciancio and Regev (2004). For a given vector x ∈ Rn , we have the following lemma. Lemma 1.3.1 For a given lattice L ⊂ Rn , we have lim s→∞ ∑ x∈L ρ1/s (x) = 1 or equally lim s→∞ ∑ x∈L{0} ρ1/s (x) = 0. Proof By the property of the exponential function, when |x| > M0 (M0 is a positive constant) then e−πs2 |x|2 1 πs2|x|2 . So ∑ x∈L ρ1/s (x) = ∑ x∈L e−πs2 |x|2 ∑ |x|M0 ,x∈L e−πs2 |x|2 + 1 πs2 ∑ |x|>M0 ,x∈L 1 |x|2 . The first part of the equation above only has a finite number of terms, so lim s→∞ ∑ |x|M0 ,x∈L e−πs2 |x|2 = 1. The second part of the above equation is a convergent series, therefore, lim s→∞ 1 πs2 ∑ |x|>M0 ,x∈L 1 |x|2 = 0. Here, we get the proof. By Definition 1.2.3, we have ρ1/s (L) = ∑ x∈L ρ1/s (x), then ρ1/s (L) is a monotone decreasing function of s. When s → ∞, ρ1/s (L) monotonically decreasing to 1. So we give the definition of smoothing parameter. 14 1 Random Lattice Theory Definition 1.3.1 Let L ⊂ Rn be a lattice with full rank, L∗ is the dual lattice of L, define the smoothing parameter η (L) of L: For any > 0, define η (L) = min{s | s > 0, ρ1/s (L∗) < 1 + }. (1.3.1) Equally, η (L) = min{s | s > 0, ρ1/s (L∗ {0}) < }. (1.3.2) By definition, the smoothing parameter η (L) of L is a monotone decreasing function of , namely η 1 (L) η 2 (L), if 0 < 2 < 1. Definition 1.3.2 Let A ⊂ Rn be a finite or countable set, X and Y are two discrete random variables on A, the statistical distance between X and Y is defined as (X, Y ) = 1 2 ∑ a∈A |Pr{X = a} − Pr{Y = a}|. (1.3.3) If A is a continuous region in Rn , X and Y are continuous random variables on A, T1(x) and T2(x) are the density functions of X and Y , respectively, then the statistical distance between X and Y is defined as (X, Y ) = 1 2 ∫ A |T1(x) − T2(x)|dx. (1.3.4) It can be proved that for any function f defined on A, we have ( f (X), f (Y )) (X, Y ). From (1.2.17) in the last section, D s,c mod L is a continuous random variable defined on the basic neighborhood F(B) of the lattice L with the density function g L ,s,c(x). Let U (F(B)) be a uniform random variable defined on F(B) with the density function d(x) = 1 det(L) . The main result of this section is that the statistical distance between D s,c mod L and the uniform distribution U (F(B)) can be arbitrar- ily small. Theorem 1.1 For any s > 0, given a lattice with full rank L = L(B) ⊂ Rn , L∗ is the dual lattice of L, then the statistical distance between the discrete Gauss distribution and the uniform distribution on the basic neighborhood F(B) satisfies (D s,c mod L , U (F(B))) 1 2 ρ1/s (L∗ {0}). (1.3.5) Particularly, for any > 0, and any s η (L), we have 1.3 Smoothing Parameter 15 (D s,c mod L , U (F(B))) 1 2 . (1.3.6) To prove Theorem 1.1, we first introduce the following lemma. Lemma 1.3.2 Suppose f (x) ∈ L1(Rn ) and satisfies the following two conditions: (i) ∑ x∈L | f (x + u)| uniformly converges in any bounded closed region of Rn (about u); (ii) ∑ y∈L∗ | ˆf (y)| converges. Then ∑ x∈L f (x) = 1 det(L) ∑ y∈L∗ ˆf (y), where L = L(B) ⊂ Rn is a full-rank lattice, L∗ is the dual lattice, det(L) = |det(B)| is the determinant of the lattice L. Proof We first consider the case of B = I n , here L = Zn , L∗ = Zn . By condition (i), let F(u) be F(u) = ∑ x∈Zn f (x + u), u ∈ Rn . Since F(u) is a periodic function of the lattice Zn , namely F(u + x) = F(u), for ∀x ∈ Zn , we have the following Fourier expansion F(u) = ∑ y∈Zn a(y)e 2πiu·y . (1.3.7) Integrating F(u)e−2πiu·x for u ∈ [0, 1]n : ∫ [0,1]n F(u)e−2πiu·x du = ∑ y∈Zn ∫ [0,1]n a(y)e 2πiu·(y−x)du = a(x), ∀x ∈ Zn . Hence, we have the following Fourier inversion formula: a(y) = ∫ [0,1]n F(u)e−2πiu·y du = ∑ x∈Zn ∫ [0,1]n f (x + u)e−2πi(u+x)·y du = ∑ x∈Zn ∫ x+[0,1]n f (z)e−2πi z·y dz = ∫ Rn f (z)e−2πi z·y dz = ˆf (y)