This is a fast implementation of NTT for Ring-LWE homomorphic encryption, FasterNTT, which is almost twice faster than NFLlib. FasterNTT employs

• Shoup's trick (for NTT), Montgomery multiplication (for point-wise mult.),
• and Scott's slothful NTT instead of Longa-Naehrig's NTT, which is employed in most of all (open-sourced) implementations.

• OpenSSL

This is a header only library, so just include and enjoy!

For benchmarks and tests, install following libraries:

• GMP (for test)
• NTL (for test)
• google/benchmark (for benchmark)
• NFLlib (if you want to compare)
• YELL (if you want to compare)

then build as usual cmake projects:

mkdir build && cd build
cmake .. -DCMAKE_BUILD_TYPE=Release

Polynomial multiplication is the main bottleneck in Ring-LWE Cryptography, and most of all implementation researches focus on the Number-theoretic Transform (NTT) for efficient polynomial multiplications. The NTT consists of:

• modular arithmetic and
• butterfly computation.

Their performance has much influence on the performance of polynomial multiplication and so Ring-LWE (homomorphic) encryptions.

In this work, we comprehensively implemented efficient algorithms of modular arithmetic and NTTs in the Ring-LWE homomorphic encryptions case, and we found the combination of Shoup's trick (for NTT) and Montgomery multiplication (for point-wise multiplication) is the fastest way to compute Ring-LWE polynomial multiplication. Also, we found the Scott's slothful NTT is quite faster than the Longa-Naehrig's NTT, which most of all (open-sourced) implementations employ. Our experiment shows that our NTT implementation, which combines (modified) Scott's NTT, Shoup's trick, and Montgomery multiplication, is almost x2 faster than NFLlib, and x1.8 faster than YELL.

[Har14] D. Harvey, "Faster arithmetic for number-theoretic transforms," Journal of Symbolic Computations, Vol.60, pp.113-119, 2014.
[LN16] P. Longa and M. Naehrig, "Speeding up the Number Theoretic Transform for Faster Ideal Lattice-Based Cryptography," CANS 2016, LNCS 10052, pp.124-139, 2016.
[Sco17] M. Scott, "A Note on the Implementation of the Number Theoretic Transform," IMACC 2017, LNCS 10655, pp.247-258, 2017.

On Core i9-9980XE (3.00 GHz), turbo boost disabled, single thread, compiled by gcc 8.3.0:

On MacBook Pro 2017 (Core i7, 3.50 GHz), turbo boost enabled, single thread, compiled by gcc 9.2.0:

Note:

• NFLlib is compiled with -DCMAKE_BUILD_TYPE=Release -DNFL_OPTIMIZED=ON.
• YELL is compiled with -DCMAKE_BUILD_TYPE=Release.
• FasterNTT uses 59-bit q, whereas NFLlib and YELL use 62-bit q, which means FasterNTT naturally loses around 5% performance compared to NFLlib and YELL, but considering the fact ours is still about twice faster.

We implemented

• Longa-Naehrig's NTT (Longa-Naehrig's NTT + Shoup's trick + NFLlib reduction)
• Scott's slothful NTT (Scott's NTT + Shoup's trick + NFLlib reduction)
• FasterNTT ((modified) Scott's NTT + Shoup's trick + Montgomery multiplication)

using several optimized levels:

• Generic: using c++ (+ GCC extensions) only,
• x86_64: using inline assembler for x86_64 arch.,
• SSE: using SSE instructions,
• AVX2: using AVX2 instructions.

Note: SSE and AVX2 are implemented on FasterNTT only since it is the fastest. Also, point-wise multiplication using SIMD (SSE or AVX2) is not available because of their slowness (we implemented but significantly slower than x86_64 ver.).

The benchmark below is measured on Core i9-9980XE (3.00 GHz), turbo boost disabled, single thread, compiled by gcc 8.3.0.

Takuya HAYASHI (t-hayashi@nict.go.jp)