了解 LWE(Learning With Error) 可忽略的錯誤機率

根據Regev 的論文，p15

正確性。請注意，如果不是因為 LWE 樣本中的錯誤， $ b-⟨a, s⟩ $ 將是 0 或 ⌊ q ⌋ 取決於加密的位，並且解密總是正確的。因此，我們看到只有當所有 S 上的錯誤項之和大於 q/4 時才會發生解密錯誤。由於我們最多對 m 個正態誤差項求和，每個項的標準差為 αq，因此和的標準差最多為 $ \sqrt{m}\alpha q < q \log{n} $ ; 標準計算表明，這樣的正態變數大於 q/4 的機率可以忽略不計。

我用mathematica做了一個小實驗，得到的解密錯誤機率約為0.28。你能指出我錯在哪裡嗎？

首先，我在論文中建構了以下變數：

In[1]:= n=10
       q=RandomPrime[{n^2,2n^2}]
       m=1.1*n*Log[q]
       α=1/(Sqrt[n]*Log[n]^2)
       σ=α * q
       Floor[q/2]
       q/4
Out[1]= 10
Out[2]= 131
Out[3]= 53.6272
Out[4]= 1/(Sqrt[10]*Log[10]^2)
Out[5]= 131/(Sqrt[10]*Log[10]^2)
Out[6]= 65
Out[7]= 131/4

然後我通過計算 x 為 -q/4 時的 Cumulative Probability 函式的值來計算誤差項總和大於 q/4 的最大機率：

In[323]:= (*Probability that sum is greater than q/4*)
         CDF[NormalDistribution[0,Sqrt[m]*α*q],-q/4]
Out[323]= 0.279785

正如你所看到的，它對於“可以忽略不計”來說太大了，所以我認為我的計算有問題。

這是單個錯誤的 PDF $ e $ 和錯誤的總和：

單一錯誤

錯誤總和

表示為 $ X $ 隨機變數，它是所有的總和 $ S $ . 如前所述，這最多是標準差的高斯 $ \sqrt{m}r $ 和 $ r = \alpha q $ . 因此，通過（子）高斯分佈的性質，你有

$$ \operatorname{Pr}\left[|X| > t\right]\leq 2\exp\left(\frac{-\pi t^2}{r^2m}\right) $$ 因此對於 $ t = \frac{q}{2} $ 你有

$$ \operatorname{Pr}\left[|X| > \frac{q}{2}\right]\leq 2\underbrace{\exp\left(\frac{-\pi \left(\frac{q}{2}\right)^2}{r^2m}\right)}_{\varepsilon(n)} $$ 從那裡你可以看到，通過選擇 $ q(n) $ 適當地（例如使用論文中提出的參數），您可以 $ \varepsilon(n) $ 一個可以忽略的函式。這並不一定意味著，一旦你修復了一個特定的 $ n $ ，這個機率是“小”的。直覺的意思是 $ n $ 在保持參數“實用”（即多項式）的同時，這種機率會以良好的速度越來越小。

引用自：https://crypto.stackexchange.com/questions/45022