關於基於格的密碼學最具影響力/啟發性的論文/書籍/課程？
我對基於格的加密的某種“綱要”感興趣。FALCON 和其他東西背後有一堆數學。很多文章都致力於點陣加密，但沒有一篇文章是最重要的。另一個問題是，有些論文顯然有影響力，但很難“從頭開始”理解。
首先，我可能會注意到其中一些：
GPV 框架：
- “如何使用短基：硬格的活板門和新的密碼結構”。
密碼分析：
- “學習平行六面體：GGH 和 NTRU 簽名的密碼分析”
基礎課程：
- 基於格子加密的冬季學校（https://cyber.biu.ac.il/event/the-2nd-biu-winter-school）
- 關於 CS 格的 Regev 課程 ( https://cims.nyu.edu/~regev/teaching/lattices_fall_2004/ )
- Vinod 的課程 ( http://people.csail.mit.edu/vinodv/6876-Fall2015/index.html )
調查：
- “基於格的密碼學”部分來自“後量子密碼學”一書。
- “格密碼學的十年”，Peikert。
不幸的是，我沒有找到任何關於離散高斯分佈和連續高斯屬性的任何內容（為什麼它在任何“小”平行六面體上“不遠”均勻），如何生成它們；關於平滑參數及其“直覺”含義。此外，從平均情況到最壞情況的減少有點棘手，並且從 Ajtai 論文中難以理解。還有一個理想格的研究方向，它在某種程度上與數域的整數環有關（ $ \mathbb{Z}_K $ )，這是完全模糊的。
你似乎有幾個問題：
當您對晶格進行建模時，為什麼離散高斯與均勻分佈“不遠”？
這在他們介紹的論文中得到了解決（Miccancio Regev 2004）。尤其參見引理 4.1。
如何生成它們？
這取決於您是否關心恆定時間生成。無論哪種方式，都有一些技巧。這些包括使用“通用採樣器”（適用於任何離散機率分佈），包括：
- 逆 CDT（累積密度表）— 如果 $ F_X(x) $ 是的累積密度函式 $ X $ ， 和 $ U\sim \mathcal{U}([0,1]) $ ， 然後 $ F_X^{-1}(U)\sim X $ . 這可用於從任何分佈生成樣本。
- Knuth-Yao 採樣 — 您創建一個特定的二叉樹，然後在其上執行無偏遍歷，並根據您最終進入的葉子返回一個樣本。非常有效的熵（並且“熵等於您需要從分佈中採樣的硬幣翻轉）來自，但很難在不破壞熵效率的情況下保持恆定時間。
- 別名抽樣。有點難以解釋，但是您可以將任何分佈的採樣減少為均勻分佈的採樣，然後根據採樣的均勻值對（預先計算的）有偏差的硬幣進行採樣。
還有一種稱為 Karney 方法的非通用採樣器。此外，還有一種稱為“卷積採樣”的採樣技術，它允許從小參數的離散高斯生成較大參數的離散高斯，因此可以限制在小參數的情況下。
最近的工作可以在這裡看到，參考文獻可以作為其他文獻的有用指針（它錯過了一些最近試圖使 KY 採樣恆定時間的工作，但僅此而已）。
平滑參數的直覺含義
直覺地說，它是一個必須放置在每個晶格點上的高斯質量的數量，以使其在整個空間中“模糊”。可以想到格子 $ \Lambda $ 作為最初的一組點（具有離散高斯參數 $ \sigma $ 每個點上的“0”）。當你增加 $ \sigma $ ，這些點“模糊”了。如果你增加 $ \sigma $ 足夠了，它們將“覆蓋”整個空間（然後，在對晶格進行建模時，將接近均勻分佈）。平滑參數測量何時發生這種形式的“相變”，在非常接近均勻和不均勻之間。
如果您更熟悉晶格的幾何概念，可以考慮圍繞晶格點（而不是高斯）不斷增加球，直到最終覆蓋某個球中環境空間的所有點。這有另一個與其相變相關的量，稱為“覆蓋半徑”。