Paper 2020/268

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

Jose Maria Bermudo Mera, 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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A minor revision of an IACR publication in TCHES 2020
Keywords
Toom-Cook multiplicationkey encapsulation mechanismpost-quantum cryptographylattice-based cryptographyefficient softwareSaber
Contact author(s)
angshuman karmakar @ esat kuleuven be
Jose Bermudo @ esat kuleuven be
History
2020-03-04: received
Short URL
https://ia.cr/2020/268
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/268,
      author = {Jose Maria Bermudo Mera and Angshuman Karmakar and Ingrid Verbauwhede},
      title = {Time-memory trade-off in Toom-Cook multiplication: an application to module-lattice based cryptography},
      howpublished = {Cryptology ePrint Archive, Paper 2020/268},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/268}},
      url = {https://eprint.iacr.org/2020/268}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.