Extended Number Theoretic Transform for Lightweight Post-Quantum Cryptosystems in IoT

The primary computational complexity of the lattice-based post-quantum cryptosystems (PQCs), aside from hashing, comes from the polynomial multiplication. Especially, the multiplication efficiency of large-degree polynomials becomes increasingly important for current applications. Therefore, in this article, we propose efficient polynomial multiplication methods, termed as the extended number theoretic transform (NTT), eventually aimed at developing efficient lightweight PQCs suitable for the Internet of Things. The proposed methods utilize the extension of finite fields and an early termination technique to enable efficient NTT implementation using better parameter values. The adoption of arithmetic in the extension field <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathbb {F}_{q^{m}}$ </tex-math></inline-formula> provides more efficient NTT computation, even when a primitive <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$2n$ </tex-math></inline-formula>th root of unity, required for NTT, does not exist in the base field <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathbb {Z}_{q}$ </tex-math></inline-formula>. More importantly, the proposed methods allow for more flexible selection of PQC parameters. Moreover, by using early termination of NTT over the extension field, we further enhance the efficiency of polynomial multiplication. As a result, the proposed methods flexibly select suitable (or smaller) modulus q by optimizing the extension degree m and the incomplete degree l. Finally, we validate the effectiveness of our methods by demonstrating their capability to offer a wide range of parameter values and significantly reduce the size of modulus q. It is confirmed through simulation that the communication efficiency and security are improved by up to 21.43% and 9.09%, respectively. Finally, it is shown that lightweight Crystals-Kyber can be easily constructed by using the proposed methods.