In a typical Ring-LWE-based public-key encryption scheme, Alice publishes
(with a power of two) as the public key, where are both “small” and secret. To encrypt, Bob computes
where are small, is the message and some encoding function, e.g. . To decrypt, Alice computes
which is equal to . Finally, Alice recovers from the noisy encoding of where is the noise. In the Module-LWE variant the elements essentially live in , e.g. is not a polynomial but a vector of polynomials.
Thus, both encryption and decryption involve polynomial multiplication modulo . Using schoolbook multiplication this costs operations. However, when selecting parameters for Ring-LWE, we can choose which permits to use an NTT to realise this multiplication (we require to use the negacyclic NTT which has modular reductions modulo baked in). Then, using the NTT we can implement multiplication by
- evaluation (perform NTT),
- pointwise multiplication,
- interpolation (perform inverse NTT).
Steps (1) and (3) take operations by using specially chosen evaluation points (roots of one). Step (2) costs operations.
This is trick is very popular. For example, many (but not all!) Ring-LWE based schemes submitted to the NIST PQC
competition process use it, namely NewHope, LIMA (go LIMA!), LAC, KCL, HILA5, R.EMBLEM, Ding Key-Exchange, CRYSTALS-KYBER, CRYSTALS-DILITHIUM (sorry, if I forgot one). Note that since steps (1) and (3) are the expensive steps, it makes sense to remain in the NTT domain (i.e. after applying the NTT) and only to convert back at the very end. For example, it is faster for Alice to store in NTT domain and, since the NTT maps uniform to uniform, to sample in NTT domain directly, i.e. to just assume that a random vector is already the output of an NTT on some other random vector.
This post is about two recent results I was involved in suggesting that this is not necessarily always the best choice (depending on your priorities.)
Warning: This is going to be one of those clickbait-y pieces where the article doesn’t live up to the promise in the headline. The NTT is fine. Some of my best friends use the NTT. In fact I’ve implemented and used the NTT myself.
Continue reading “NTT Considered Harmful?”