TMVP-based Multiplication for Polynomial Quotient Rings and Application to Saber on ARM Cortex-M4
İrem Keskinkurt Paksoy, Middle East Technical University
Murat Cenk, Middle East Technical University
Abstract
Lattice-based NIST PQC finalists need efficient multiplication in . Multiplication in this ring can be performed very efficiently via number theoretic transform (NTT) as done in CRYSTALS-Kyber if the parameters of the scheme allow it. If NTT is not supported, other multiplication algorithms must be employed. For example, if the modulus of the scheme is a power of two, as in Saber and NTRU, then NTT can not be used directly. In this case, Karatsuba and Toom-Cook methods together with modular reduction, are commonly used for multiplication in this ring. In this paper, we show that the Toeplitz matrix-vector product (TMVP) representation of modular polynomial multiplication yields better results than Karatsuba and Toom-Cook methods. We present three- and four-way TMVP formulas derived from three- and four-way Toom-Cook algorithms, respectively. We use the four-way TMVP formula to develop an algorithm for multiplication in the ring . We implement the proposed algorithm on the ARM Cortex-M4 microcontroller and apply it to Saber, one of the lattice-based finalists of the NIST PQC competition. We compare the results to previous implementations. The TMVP-based multiplication algorithm we propose is faster than the previous algorithm that uses a combination of Toom-Cook, Karatsuba, and schoolbook methods. Our algorithm also speeds up key generation, encapsulation, and decapsulation algorithms of all variants of Saber. The speedups vary between . Moreover, our algorithm requires less memory than the others, except for the memory-optimized implementation of Saber.
Note: This is the extended version of the 2020 paper.
@misc{cryptoeprint:2020/1302,
author = {İrem Keskinkurt Paksoy and Murat Cenk},
title = {{TMVP}-based Multiplication for Polynomial Quotient Rings and Application to Saber on {ARM} Cortex-M4},
howpublished = {Cryptology {ePrint} Archive, Paper 2020/1302},
year = {2020},
url = {https://eprint.iacr.org/2020/1302}
}
Note: In order to protect the privacy of readers, eprint.iacr.org
does not use cookies or embedded third party content.