Cryptology ePrint Archive: Report 2020/268

Time-memory trade-off in Toom-Cook multiplication: an application to module-lattice based cryptography

Jose Maria Bermudo Mera and Angshuman Karmakar and Ingrid Verbauwhede

Abstract: Since the introduction of the ring-learning with errors problem, the number theoretic transform (NTT) based polynomial multiplication algorithm has been studied extensively. Due to its faster quasilinear time complexity, it has been the preferred choice of cryptographers to realize ring-learning with errors cryptographic schemes. Compared to NTT, Toom-Cook or Karatsuba based polynomial multiplication algorithms, though being known for a long time, still have a fledgling presence in the context of post-quantum cryptography. In this work, we observe that the pre- and post-processing steps in Toom-Cook based multiplications can be expressed as linear transformations. Based on this observation we propose two novel techniques that can increase the efficiency of Toom-Cook based polynomial multiplications. Evaluation is reduced by a factor of 2, and we call this method precomputation, and interpolation is reduced from quadratic to linear, and we call this method lazy interpolation. As a practical application, we applied our algorithms to the Saber post-quantum key-encapsulation mechanism. We discuss in detail the various implementation aspects of applying our algorithms to Saber. We show that our algorithm can improve the efficiency of the computationally costly matrix-vector multiplication by12−37%compared to previous methods on their respective platforms. Secondly, we propose different methods to reduce the memory footprint of Saber for Cortex-M4microcontrollers. Our implementation shows between2.6 and 5.7KB reduction in memory usage with respect to the smallest implementation in the literature.

Category / Keywords: public-key cryptography / Toom-Cook multiplication, key encapsulation mechanism, post-quantum cryptography, lattice-based cryptography, efficient software, Saber

Original Publication (with minor differences): IACR-CHES-2020

Date: received 27 Feb 2020

Contact author: angshuman karmakar at esat kuleuven be,Jose Bermudo@esat kuleuven be

Available format(s): PDF | BibTeX Citation

Version: 20200304:080735 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]