R-LWE key exchange why using FFT instead of Karatsuba In the paper Post-quantum key exchange for the TLS protocol from the ring learning with errors problem one of the authors, Douglas Stebila, uses the FFT algorithm for polynomial multiplication but he never explains why he did not use a much simpler algorithm such as Karatsuba for polynomial multiplication.

The Ring-LWE (RLWE) parameters choices are (according to 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


So in the worst case: we are multiplying two polynomials of degree 1024 with coefficients at most 40961 with each other. This does not make sense considering that FFT method should be used only for multiplying polynomials with large coefficient:


  In practice the Schönhage–Strassen algorithm starts to outperform
  older methods such as Karatsuba and Toom–Cook multiplication for
  numbers beyond $2^{2^{15}}$ to $2^{2^{17}}$ (10,000 to 40,000 decimal digits).


Question: what was the reason behind it? Am I making a mistake by saying that Karatsuba would outperform FFT considering parameter choices for R-LWE key exchange? Or did the author use this method to make R-LWE key exchange process look overly complicated?
First, as "Hope that's a start" mentioned, your citation is about the algorithms for multiplying integers, not polynomials. For polynomials, the FFT starts to be more efficient than Karatsuba and Toom-Cook methods much earlier, for polynomials of degree between (very roughly) a few hundreds and a few thousands.

However, for polynomials with integer coefficients, it is usually better to take the NTT (number theoretic transform) rather than the FFT, especially if those coefficients are considered modulo a certain $q$. First, you get no precision issues. Second, it is much faster. I have no idea why in the article you mentioned, the authors use FFT and not NTT, so it might be a good idea to ask them.

Now, to answer your question, the efficiency of NTT and Toom-Cook/Karatsuba methods are comparable for parameters equal to those you mentioned. Most lattice-based crypto implementation papers I have seen use the NTT (eg. New Hope), since the underlying rings are usually of the NTT-friendly form $\mathbb Z_q[x]/(x^{2^k}+1)$, and applications such as homomorphic encryption require bigger $n$'s, in which case NTT is clearly faster. That being said, I have seen efficients combinations of Karatsuba, Toom-Cook and schoolbook multiplication (eg. NTRU Prime) in lattice-based crypto.