姓名：厲偉 學(xué)號：21011210604? 學(xué)院：通信工程學(xué)院
【嵌牛導(dǎo)讀】高斯采樣
【嵌牛鼻子】基于格
【嵌牛提問】如何有效的采樣娄徊？
【嵌牛正文】
一.高斯函數(shù)
?對于任何 s > 0，使用參數(shù) s 定義以 c 為中心的 Rn 上的高斯函數(shù)：
二.背景
作為第一次嘗試，考慮這樣一種算法:首先從一個參數(shù)為s的連續(xù)高斯函數(shù)中采樣锐峭，然后使用B將采樣點“四舍五入”到一個相對鄰近的格點可婶。事實上，Regev在他的規(guī)約“bootstrapping”步驟中應(yīng)用了這個確切的策略矛渴，使用了一個LLL縮減基和一個高斯參數(shù)s, s是一個比基長度‖B‖大的指數(shù)因子具温。
不幸的是，當s是基長的小倍數(shù)時铣猩，這種策略就不能很好地工作了。即使 Λ 是一維晶格天吓，也可以看出這個問題峦椰，例如，整數(shù)集Z?R1汤功。考慮由舍入格式引起的分布D拂封，使用一個以0為中心的連續(xù)高斯函數(shù)，參數(shù)s = nc為常數(shù)c > 0在抛。常規(guī)計算表明萧恕，通過誤差函數(shù)erf的麥克勞林級數(shù)展開，D賦值為0的概率為erf(√π/2s) = 1/s?Ω(1/s3)票唆。另一方面，可以表明衅金，期望分布DZ,s賦值為0的概率接近于1/s簿煌，可以忽略。因此惩琉，兩個分布之間的統(tǒng)計距離至少是Ω(1/s3)夺荒，這是不可忽略的。對于n維格技扼，由于采樣點與其舍入格點之間的距離隨著n的增長，舍入格式導(dǎo)致的分布更加偏置私沮。
我們不使用連續(xù)分布和橙，而是展示如何“直接”從所需的離散高斯分布下的格中采樣。即使在一維情況下魔招，這也需要一些注意:分布是無限的办斑，即使接近它也可能沒有一個簡潔的表示(例如杆逗，當參數(shù)s很大時)鳞疲。我們首先定義一個從整數(shù)點陣z中采樣的核心子程序，然后使用這個子程序定義Babai的最近平面算法[Bab86]的隨機變體尚洽，它本質(zhì)上等價于Klein在另一種情況下提出的算法。這里的新奇之處在于對其輸出分布進行了近乎精確的分析癣疟，以便選擇合適的參數(shù)潮酒。
三.整數(shù)格抽樣
? 讓t (n)≥ω(√log n)是一些固定的函數(shù),比如說,t (n) = log n。SampleZ使用拒絕抽樣,工作如下:在輸入(s扎狱、c)和(隱式地)的安全參數(shù)n, 隨機均勻選擇一個整數(shù)x←Z = Z ∩(c?s·t(n), c + s·t (n))勃教。然后概率ρs(x?c)∈(0,1)，輸出x荣回，否則重復(fù)戈咳。
四.任意格中抽樣
?
