R-LWE 密鑰交換為什麼使用 FFT 而不是 Karatsuba
在論文Post-quantum key exchange for the TLS protocol from the ring learning with errors problem中，作者之一 Douglas Stebila 使用FFT 算法進行多項式乘法，但他從未解釋為什麼他不使用更簡單的算法，例如Karatsuba用於多項式乘法。
Ring-LWE (RLWE) 參數選擇是（根據 Singh，Vikram）：
For 128 bits of security, n = 512, q = 25601, and Φ(x) = x^512 + 1 For 256 bits of security, n = 1024, q = 40961, and Φ(x) = x^1024 + 1所以在最壞的情況下：我們將兩個 1024 次多項式與最多 40961 的係數相乘。考慮到 FFT 方法應僅用於將具有大係數的多項式相乘，這是沒有意義的：
在實踐中，Schönhage-Strassen 算法開始優於舊方法，例如 Karatsuba 和 Toom-Cook 乘法[ Math Processing Error ] $ 2^{2^{15}} $ 至[Math Processing Error] $ 2^{2^{17}} $ （10,000 到 40,000 位十進制數字）。
問題：背後的原因是什麼？考慮到 R-LWE 密鑰交換的參數選擇，我是否說 Karatsuba 會優於 FFT，這是否是一個錯誤？還是作者使用這種方法讓 R-LWE 密鑰交換過程看起來過於復雜？
首先，正如“希望這是一個開始”所提到的，您的引文是關於乘以整數的算法，而不是多項式。對於多項式，FFT 開始比 Karatsuba 和 Toom-Cook 方法更早，對於（非常粗略地）幾百到幾千次的多項式。
但是，對於具有整數係數的多項式，通常最好採用 NTT（數論變換）而不是 FFT，特別是如果這些係數被認為是模數[Math Processing Error] $ q $ . 首先，您不會遇到精度問題。其次，它要快得多。我不知道為什麼在你提到的文章中，作者使用 FFT 而不是 NTT，所以問他們可能是個好主意。
現在，為了回答您的問題，NTT 和 Toom-Cook/Karatsuba 方法的效率與您提到的參數相當。我見過的大多數基於格的加密實現論文都使用 NTT（例如New Hope），因為底層的環通常是 NTT 友好的形式[Math Processing Error] $ \mathbb Z_q[x]/(x^{2^k}+1) $ ，而同態加密等應用需要更大的 $ n $ ‘s，在這種情況下，NTT 顯然更快。話雖如此，我已經在基於格的加密中看到了 Karatsuba、Toom-Cook 和教科書乘法（例如NTRU Prime ）的有效組合。