لایب سان

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)

چکیده فارسی

1.3 پارامتر هموارسازی 13 1.3 پارامتر هموارسازی برای یک شبکه با رتبه کامل L ⊂ Rn، در بخش قبل، اندازه گاوس گسسته g L,s,c(x) و متغیر تصادفی پیوسته متناظر D را تعریف کردیم. s,c mod L در محله اصلی F(B) L. در این بخش، یک پارامتر مهم در شبکه گاوس - پارامتر هموارسازی را مورد بحث قرار می دهیم. مفهوم پارامترهای صاف توسط Micciancio و Regev در سال 2007 Micciancio و Regev (2004) معرفی شد. برای یک بردار داده شده x ∈ Rn، لم زیر را داریم. لم 1.3.1 برای یک شبکه معین L ⊂ Rn، lim s∞∞ ∑ x∈L ρ1/s (x) = 1 یا به همان اندازه lim s→∞ ∑ x∈L\{0} ρ1/s (x) داریم. = 0. اثبات با خاصیت تابع نمایی، وقتی |x| > M0 (M0 یک ثابت مثبت است) سپس e−πs2 |x|2 1 πs2|x|2 . بنابراین ∑ 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 . قسمت اول معادله بالا فقط دارای تعداد متناهی جمله است، بنابراین lim s→∞ ∑ |x| M0 ,x∈L e−πs2 |x|2 = 1. قسمت دوم معادله فوق یک همگرا است. سری، بنابراین، lim s→∞ 1 πs2 ∑ |x|>M0 ,x∈L 1 |x|2 = 0. در اینجا، ما اثبات را دریافت می کنیم. طبق تعریف 1.2.3، ρ1/s (L) = ∑ x∈L ρ1/s (x) داریم، سپس ρ1/s (L) یک تابع کاهشی یکنواخت s است. هنگامی که s → ∞، ρ1/s (L) به طور یکنواخت به 1 کاهش می یابد. بنابراین ما تعریف پارامتر هموارسازی را ارائه می دهیم. 14 1 تعریف تئوری شبکه تصادفی 1.3.1 اجازه دهید L ⊂ Rn یک شبکه با رتبه کامل باشد، L∗ شبکه دوگانه L است، پارامتر هموارسازی η (L) L را تعریف کنید: برای هر > 0، η (L) را تعریف کنید. = دقیقه | s > 0، ρ1/s (L∗) < 1 + }. (1.3.1) به طور مساوی، η (L) = min{s | s > 0، ρ1/s (L∗ \{0}) < }. (1.3.2) طبق تعریف، پارامتر هموارسازی η (L) از L یک تابع کاهشی یکنواخت است، یعنی η1 (L) η2 (L)، اگر 0 <2 < 1. تعریف 1.3.2 اجازه دهید A ⊂ Rn یک مجموعه محدود یا قابل شمارش باشد، X و Y دو متغیر تصادفی گسسته در A هستند، فاصله آماری بین X و Y به صورت (X, Y ) = 1 2 ∑ a∈A |Pr{X = a} - تعریف می شود. Pr{Y = a}|. (1.3.3) اگر A یک ناحیه پیوسته در Rn باشد، X و Y متغیرهای تصادفی پیوسته روی A هستند، T1(x) و T2(x) به ترتیب توابع چگالی X و Y هستند، پس فاصله آماری بین X و Y به صورت (X, Y ) = 1 2 ∫ A |T1(x) - T2(x)|dx تعریف می شود. (1.3.4) می توان ثابت کرد که برای هر تابع f که روی A تعریف شده است، (f (X)، f (Y )) (X, Y) داریم. از (1.2.17) در بخش آخر، Ds,c mod L یک متغیر تصادفی پیوسته است که روی همسایگی اصلی F(B) شبکه L با تابع چگالی gL,s,c(x) تعریف شده است. فرض کنید U (F(B)) یک متغیر تصادفی یکنواخت تعریف شده در F(B) با تابع چگالی d(x) = 1 det(L) باشد. نتیجه اصلی این بخش این است که فاصله آماری بین Ds,c mod L و توزیع یکنواخت U (F(B)) می تواند به طور دلخواه کوچک باشد. قضیه 1.1 برای هر s > 0، با توجه به یک شبکه با رتبه کامل L = L(B) ⊂ Rn، L∗ شبکه دوگانه L است، سپس فاصله آماری بین توزیع گسسته گاوس و توزیع یکنواخت در محله اصلی F است. (B) برآورده می کند (D s,c mod L , U (F(B))) 1 2 ρ1/s (L∗ \{0}). (1.3.5) به ویژه، برای هر > 0، و هر s η (L)، ما 1.3 پارامتر هموارسازی 15 داریم (D s,c mod L , U (F(B))) 1 2 . (1.3.6) برای اثبات قضیه 1.1، ابتدا لم زیر را معرفی می کنیم. لم 1.3.2 فرض کنید f (x) ∈ L1(Rn ) و دو شرط زیر را برآورده می کند: (i) ∑ x∈L | f (x + u)| به طور یکنواخت در هر ناحیه بسته محدود Rn (در مورد u) همگرا می شود. (ii) ∑ y∈L∗ | ˆf (y)| همگرا می شود. سپس ∑ x∈L f (x) = 1 det(L) ∑ y∈L∗ ˆf (y)، که در آن L = L(B) ⊂ Rn یک شبکه با رتبه کامل است، L∗ شبکه دوگانه است، det( L) = |det(B)| تعیین کننده شبکه L است. اثبات ما ابتدا مورد B = I n را در نظر می گیریم، در اینجا L = Zn، L∗ = Zn. با شرط (i)، فرض کنید F(u) F(u) = ∑ x∈Zn f (x + u)، u ∈ Rn باشد. از آنجایی که F(u) تابع تناوبی از شبکه Zn است، یعنی F(u + x) = F(u)، برای ∀x ∈ Zn، بسط فوریه زیر را داریم F(u) = ∑ y∈Zn a( y)e 2πiu·y . (1.3.7) ادغام F(u)e−2πiu·x برای 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. بنابراین، فرمول وارونگی فوریه زیر را داریم: 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)