較小的模噪比意味著 LWE 的安全性更高
讓 $ \text{Adv}^{\text{DLWE}}_{n,m,q,\sigma} $ 是攻擊者區分 LWE 樣本和統一樣本的優勢，其中 $ m $ 是樣本數， $ q $ 模量和 $ \sigma $ 誤差分佈的標準差。
我找不到這個優勢的明確表達。
是否減少 $ q $ 並增加 $ \sigma $ 意味著較小的優勢（因此更好的安全性？）
我找不到這個優勢的明確表達。
沒有一個。這是因為它與復雜性理論的最新技術相一致，即 $ \mathsf{P} = \mathsf{NP} $ ，因此 $ \mathsf{Adv}{n,m,q,\sigma}^{\mathsf{DLWE}} $ 是相關參數大小的一些多項式。這也與目前的密碼學思想一致，事實並非如此，更具侵略性的事情是真實的，即 $ \mathsf{Adv}^{\mathsf{DLWE}}{n,m,q,\sigma} $ 幾乎完全由 $ n\log q $ ，特別是：
- $ m $ 在不影響安全性的情況下可以很大，並且
- $ \sigma $ 可以很小（理論上 $ \sigma = \Omega(\sqrt{n}) $ 通常是必需的，儘管實際上 $ \sigma = O(1) \approx 8 $ 常見）。
那麼如何具體評價這一優勢呢？通常通過（具體）評估已知攻擊的最新技術。為此，有兩個主要資源：
- Albrecth 等人的“LWE 估計器”。非常受歡迎。您可以在此處查看最初的論文，並在此處查看（更新的）sage 模組。
- 現有的基於格的基元的具體建議。例如，NIST PQC 決賽選手 Kyber、Sabre 和 NTRUPrime 都包含（具體）分析來證明他們的參數選擇是正確的。對於較重的原語，同態加密標準包含建議參數表，以及指導這些表的構造的攻擊摘要。
都說了這麼多…
是否減少 $ q $ 並增加 $ \sigma $ 意味著較小的優勢（因此更好的安全性？）
在其他條件相同的情況下，答案是肯定的。給定一個 LWE 實例 $ (\mathbf{A}, \vec b) $ ，一個可以從模數切換 $ q\mapsto q’ $ （為了 $ q’ < q $ ，分析更清晰，如果 $ q’ \mid q $ 儘管）。這大致映射了誤差的標準偏差 $ \sigma \mapsto \frac{q’}{q}\sigma < \sigma $ . 然後可以將此誤差增加到某個標準偏差 $ \sigma’ > \sigma > \frac{q’}{q}\sigma $ 通過添加適當的高斯。
這就是說有一個比較簡單的從 $ \mathsf{DLWE}{n, m, q, \sigma}\leq \mathsf{DLWE}{n, m, q’, \sigma’} $ 為了 $ \sigma’ > \sigma $ 和 $ q’ \mid q $ （的情況下 $ q’ < q $ 難度不大，但你必須處理一些“舍入誤差”），所以優勢會更小。