剪尾和離散高斯採樣精度對 LWE / Ring-LWE 安全性的影響
離散高斯採樣實現的尾部切割和精度如何影響 LWE / Ring-LWE 安全性？是否有經驗法則或指南來選擇尾部切割和給定標準偏差的精度？
剪尾是指砍掉分佈的“尾部”部分（ $ |x| > \beta \sigma $ )，其總質量可忽略不計。
在 2015 年的這篇論文中，作者推薦 tail-cut at $ |x| > 9.2\sigma $ 和 128 位安全性的 64 位精度。然而，這似乎太保守了，因為許多 NIST PQCrypto 送出的文件都使用更小的尾部切割和更低的精度。例如，FrodoKEM在 $ \approx 4\sigma $ 和 16 位精度。此外，FrodoKEM使用理論分佈和量化分佈之間的 Renyi 散度而不是統計距離來衡量採樣的準確性。
剪尾和精度是指區分方案中使用的實際分佈和方案證明中使用的分佈的問題。您想以某種方式爭辯說，對手無法從這兩個略有不同的分佈中獲得任何優勢。
正如您已經提到的，目前在點陣加密中有兩種或多或少廣泛使用的方法。傳統的方法是限制統計距離（SD）。這確實計算了兩個分佈之間的差異。第二種方法是 Renyi 散度 (RD)。Renyi 散度計算類似於加權差異的東西（取決於您採用的差異）。最好的辦法是真正閱讀提出這一點的論文。他們還討論了仁義分歧的不同順序。現在有幾篇後續論文改進了這種方法。只需詢問您最喜歡的搜尋引擎即可。
一般來說，使用 SD 或 RD 估計此類分析的結果並沒有真正的經驗法則。
然而，當涉及到尾部切割時，它相對容易，因為這兩種分佈之間的差異通常是已知的。如果尾部的總機率質量類似於 $ p = 2^{-k} $ 對於安全參數 $ k $ , 那麼有尾分佈和無尾分佈之間的統計距離就是 $ p $ 因此可以忽略不計。這意味著對手無法比機率限制為更好地區分這兩個分佈 $ p $ . 因此，任何對手以一種或另一種分佈攻擊該方案的成功機率的差異也必須由 $ p $ .
當談到浮點精度問題時，一切都變得更加棘手。在這裡，差異取決於所使用的算法及其實現方式。因此，您需要對每個實現進行新的分析。