FHEW方案中高斯雜訊的標準差
關於論文FHEW：Bootstrapping Homomorphic Encryption in less than a second，我有兩個問題。
首先，刷新過程後密文的最終誤差表示為遵循標準差的高斯：
$ \beta = \sqrt{\dfrac{q^2}{Q^2}\left( \zeta^2 \cdot \dfrac{B_{r}^2}{12} \cdot nd_r\cdot \dfrac{q}{2} \cdot 2Nd’ + \sigma^2Nd_{ks}\right) + \dfrac{|\mathbf{s}|^2+1}{12}} $
然後，在給出他們選擇的參數後，他們得出結論： $ \beta = 6.94 $ . 我不明白這個結果來自哪裡。即使我們忽略平方根中的（正）第一項，如 $ |s| \leq n/2 $ （和 $ n=500 $ 在參數中），標準偏差 $ \beta $ 應該比 $ 6.94 $ …這個結果從何而來？
其次，他們接著說每個同態 NAND 的錯誤機率是 $ p = 1 - erf(r/\sqrt{2}) $ 在哪裡 $ r = \dfrac{q/8}{\sqrt{2}\beta} $ . 我知道 $ p $ 是在區間之外獲得樣本的機率 $ [-r;r] $ ，但我不明白他們為什麼設置 $ r $ 那樣。它代表什麼？
抱歉剛剛看到這個問題。對於你的第一個問題，好吧，似乎有一個錯字：我應該寫 $ |s|^2 \leq n/2 $ ，然後我們有 $ \sqrt{(|s|^2 +1) /12 } = \sqrt{251/12} \approx 4.57 $ .
現在，我們取 2 個帶有 LWE 標準偏差錯誤的密文 $ \beta $ ，並對它們求和。假設獨立性，錯誤總和的標准開發是 $ \sqrt 2 \beta $ . 為了正確性，我們需要這個錯誤總和小於 $ q/8 $ （在這裡，為了節省最後一點，我們放寬引理 7 中所述的幼稚條件，並直接綁定總和 $ q/8 + |e_0 + e_1| $ 經過 $ q/4 $ 而不是邊界 $ e_0 $ 和 $ e_1 $ ).
回答通過交換 KeySwitch 減少錯誤的評論和 $ \textsf{HomNAND} $
只是為了這個解釋，讓我對實際的雜訊傳播撒謊，並假設每個操作 HN 和 KS 只是在雜訊量上添加一個常數，表示為 $ h $ 和 $ k $ .
``易於描述的方案’‘確實 $ \textsf{HomNAND}(KS(X_1), KS(X_2)) $ ，這會導致表單錯誤 $ (x_1 + k) + (x_2 + k) + h = x_1 + x_2 + h + 2k $ .
“更好但不太容易描述的方案”確實 $ KS(\textsf{HomNAND}(X1, X_2)) $ 這導致錯誤 $ (x_1+x_2+h) + k $ . 那是少一ks。
事實證明，即使使用實際公式，我們也可以通過這個技巧獲得一點最終錯誤。