5
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Why don't you ask the author directly? We cannot read his mind... $\endgroup$ – fkraiem Nov 15 '16 at 5:05
  • $\begingroup$ @fkraiem I asked this question because I thought it is an obvious fact. Maybe I didn't read the paper carefully or I am missing something. Asking the author is a last option. $\endgroup$ – Node.JS Nov 15 '16 at 5:34
  • 4
    $\begingroup$ "Asking the author is a last option." Why? Authors are always happy to discuss their work, if your question is sensible (as yours is). $\endgroup$ – fkraiem Nov 15 '16 at 5:36
  • $\begingroup$ @fkraiem Thank you. I understand. I will ask the author now. $\endgroup$ – Node.JS Nov 15 '16 at 5:38
6
+25
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

Your citation about when to use Schönhage–Strassen instead of Karatsuba or Toom-Cook multplication refers to multiplication of long integers not to multiplication of integer polynomials.

All these methods can be interpreted as using multiplication of integer polynomials to speed up the multiplication of integers, whereas here one is already given polynomials directly.

The main reason for Schönhage–Strassen being more efficient than usual is the special choice of the polynomials $\Phi$: Their zeros are exactly the 512th rsp. 1024th roots of unity that are used during the FFT, which helps to make things faster here.

$\endgroup$
2
$\begingroup$

In addition to the answers above, an efficient polynomial multiplication for R-LWE is more than using FFT (as a matter of fact, it should be NTT, the finite field version of FFT). Nowadays people usually use NTT with NWC (negative wrapped convolution) to achieve more efficient multiplications.

As we know that FFT requires you to firstly extend the two polynomials to double of their length, and then dot-multiplication. Finally you need to reduce the result back to the original length. However, with NWC, this length extension and reduction can be spared.

Assume you have two polynomials $a$, $b$ of length $n$ and want to compute $c = a \odot b$ where $\odot$ is polynomial convolution.

  1. $\bar{a} \leftarrow NWC(a); \bar{b} \leftarrow NWC(b)$;
  2. $\bar{A} \leftarrow NTT(\bar{a}); \bar{B} \leftarrow NTT(\bar{b})$;
  3. $\bar{C} = \bar{A}\cdot \bar{B}$, where $\cdot$ is dot product;
  4. $\bar{c} \leftarrow inverse\_NTT(\bar{C})$;
  5. $c \leftarrow inverse\_NWC(\bar{c})$.

Each NWC takes $n$ multiplications and the NTT takes $n\log{n}$. So the total complexity is $O(n\log{n})$, comparing with the straightforward polynomial convolution with $O(n^2)$ multiplications.

$\endgroup$
1
$\begingroup$

They use a specific FFT algorithm for cyclotomic rings:

Multiplying two elements in $R_q$ can be achieved by computing the discrete Fourier transform via fast Fourier transform (FFT) [CT65] algorithms. More specifically, we use the approach from Nussbaumer [Nus80] based on recursive negacyclic convolutions (see [Knu97, Exercise 4.6.4.59] for more details) since this naturally applies to cyclotomic rings where the degree is a power of 2. (...)  Investigation of other asymptotically efficient polynomial multiplication algorithms, such as Schönhage-Strassen multiplication [SS71], is left as future research.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.