NTRU 沒有以前想像的那麼安全？

一篇新論文（https://eprint.iacr.org/2015/552.pdf）說：

這使得在次指數時間內漸近和啟發式地破解 NTRU 密碼系統成為可能（不違背其安全假設）。

這是否意味著 NTRU 現在不那麼安全了？多少？

不，這個結果（就目前而言）對於通常使用的 NTRU 沒有實際用途。引用論文：

請注意，o(1) 項中隱藏了一個很大的值，因此我們的算法不會對推薦的 NTRU 參數產生實際攻擊。

此外，雖然它是次指數的，但幾乎沒有。他們估計時間為 $ 2^{ (\ln 2/2+o(1))n/ \log \log n} $ ; 即使我們忽略 $ o(1) $ 術語，這比指數函式的增長速度稍慢。

另一方面，這種攻擊可能對將 NTRU 用作某種同態密碼（這要求誤差項要小得多）有用。此外，也許這個結果可以被銳化到足以對抗 NTRU。所以，雖然這對 NTRU 來說不是致命的，但這本書也沒有關閉。

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