離散高斯採樣在基於格的加密中的作用？
我正在閱讀後量子密碼學的工作原理，並偶然發現了離散高斯採樣的概念。但是，我無法理解它在更大的圖景中的位置——目前在我看來，它就像是解決沒有人提出的問題的解決方案。
在 SVP 問題（或任何其他常用的格問題）中，離散高斯採樣究竟會在哪裡提供好處？
我還是 PQ 的新手，所以請原諒這個問題很可能是平庸的
高斯分佈滿足以下理想性質：
- 它可以以座標方式實現：如果 $ x_1, x_2, \ldots , x_n $ 每個都從一個單變數高斯分佈中採樣，然後 $ (x_1,x_2,\ldots,x_n) $ 從多變數高斯分佈中採樣。
- *無論晶格是什麼，*它都能以指數方式很好地逼近一個以晶格為模的均勻誤差分佈。
第一個屬性使實現變得容易，第二個屬性使安全證明變得容易，因為基於格的加密中的許多安全證明涉及多次切換格，直到你得到你想要的。
為了說明我所說的第二個屬性是什麼意思，讓我們考慮一個一維晶格 $ \mathbb{Z} = {\ldots, -2, -1, 0, 1, 2, \ldots} \subset \mathbb{R}^1 $ . 採用具有標準差的正態分佈 $ 1/2 $ . 換句話說，只是你的平均正態分佈：
假設我從這個分佈中採樣實數並取結果實數的小數部分。（取小數部分對應於取關於晶格的誤差向量 $ \mathbb{Z} $ .) 由此產生的分佈相當於採用原始正態分佈，將其分割成單位間隔 $ \ldots, [-2,-1], [-1,0], [0,1], [1,2], \ldots $ , 並將它們相加。當我們這樣做時，我們會得到一些非常神奇的東西：
注意這個分佈是多麼接近均勻！此分佈的“半徑”或標準差僅 $ 1/2 $ ，不比單位區間的大小大多少；事實上它更小。即使半徑如此之小，我們也能得到一個非常好的均勻分佈近似值。您可以證明（並且您應該證明，作為練習）近似值的質量與原始正態分佈居中位置的選擇無關。
假設我們採用稍大的正態分佈，比如標準偏差 $ 2/3 $ :
如果我們繪製這個分佈的小數部分，我們得到：
這真的很好！你甚至不能說它偏離了製服。用數學術語來說，我們說分佈呈指數接近均勻。即使是分佈寬度的小幅增加（從 $ 1/2 $ 至 $ 2/3 $ ) 顯著提高了近似的質量。
你可能會說，有什麼大不了的？我們可以很容易地得到任何區間的均勻分佈。但這不是重點。在基於格的密碼學中，您通常不知道格是什麼。（它是某人的密鑰的一部分。）假設作為一個練習，我們不知道這個格子是什麼，並且我們嘗試通過從一個區間中均勻地獲取誤差向量來採樣它們 $ [0,n] $ 對於一些 $ n $ . 我們不能只選擇完美的 $ n=1 $ . 這是作弊，因為我們假設我們不知道格子是什麼。在這種情況下，任何一個小數的選擇 $ n $ 會導致分佈嚴重錯誤；例如，如果我們選擇 $ n=2/3 $ 在這種情況下，我們所有的錯誤向量都將位於 $ [0,2/3] $ ，這遠非統一 $ [0,1] $ . 甚至稍微大一點 $ n $ 不好；例如，如果 $ n=3/2 $ 然後從 $ [0,3/2] $ 將更有可能有小數部分（即誤差向量）位於 $ [0,1/2] $ 比在 $ [1/2,1] $ . 當然，一個非常大的 $ n $ （說 $ n \approx 10^9 $ ) 可以完成這項工作，但這正是問題所在：因為我們在 $ [0,n] $ 不收斂到均勻分佈 $ [0,1] $ 指數級的快（除非我們通過採取 $ n \in \mathbb{Z} $ ，這是不允許的），我們最終需要取非常大的值 $ n $ ，這不僅難以實現，而且是需要理論分析的安全證明中的噩夢。
您需要的是一種以指數方式很好地逼近均勻誤差向量的方法，而不依賴於先驗知識點陣是什麼。高斯分佈可以完成這項工作。
