使用“關於對小秘密 LWE 的雙格攻擊和 HElib 和 SEAL 中的參數選擇”進行 LWE 的安全性估計

我最近發現了這篇論文eprint，它使用改進的雙重攻擊來估計 LWE 實例化的安全性。但是，我在這個網站上看到他們的例子時感到困惑。例如，在 NewHope 的情況下，他們的範例給出了使用雙重攻擊的最小操作（rop）是 $ 2^{371} $ ，而最小值 $ \beta $ 是 $ 1168 $ . 因此，在 NewHope 論文之後，NewHope 的安全性應該是 $ 2^{.2075*1168}\ =\ 2^{242} $ . 這確實增加了 NewHope 的安全性。我想知道我應該將哪個作為位安全？

另一個問題是定義 $ \alpha $ , 在他們的論文中他們定義 $ \alpha=\sigma*\sqrt{2\cdot \pi}/q $ 而在他們採取的例子中 $ \alpha=\sigma^2/q $ （NewHope 參數）。

我直接向作者提出了這個問題。為了回答第一個問題，NewHope 的作者非常保守地估計了他們的安全性，而估計器考慮了許多其他因素。具體來說，這是我從作者那裡得到的答案。

嗨，我建議使用他們聲稱的安全性。解釋差異：

• 您引用的估計是偏執估計，它與 BKZ.sieve 的指數中的前導常數不同
• New Hope 保守地假設一個 SVP 呼叫就足夠了（我們使用 8n ，這是不那麼保守的）
• 新希望使用不同的技術來擴大雙重攻擊的成功率。對於這裡考慮的參數集，它們的估計意味著放大基本上是免費的，而估計器假設放大具有相當大的成本。

第二部分，計算 $ \alpha $ 錯了。它應該是 $ \sigma\cdot\sqrt{2\cdot\pi}/q $

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