International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Jose Maria Bermudo Mera , imec-COSIC, KU Leuven, Kasteelpark Arenberg 10, Bus 2452, B-3001 Leuven-Heverlee, Belgium
Angshuman Karmakar , imec-COSIC, KU Leuven, Kasteelpark Arenberg 10, Bus 2452, B-3001 Leuven-Heverlee, Belgium
Ingrid Verbauwhede , imec-COSIC, KU Leuven, Kasteelpark Arenberg 10, Bus 2452, B-3001 Leuven-Heverlee, Belgium
Download:
DOI: 10.13154/tches.v2020.i2.222-244
URL: https://tches.iacr.org/index.php/TCHES/article/view/8550
Search ePrint
Search Google
Presentation: Slides
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 by 12−37% compared to previous methods on their respective platforms. Secondly, we propose different methods to reduce the memory footprint of Saber for Cortex-M4 microcontrollers. Our implementation shows between 2.6 and 5.7 KB reduction in the memory usage with respect to the smallest implementation in the literature.
Video from TCHES 2020
BibTeX
@article{tches-2020-30160,
  title={Time-memory trade-off in Toom-Cook multiplication: an application to module-lattice based cryptography},
  journal={IACR Transactions on Cryptographic Hardware and Embedded Systems},
  publisher={Ruhr-Universität Bochum},
  volume={2020, Issue 2},
  pages={222-244},
  url={https://tches.iacr.org/index.php/TCHES/article/view/8550},
  doi={10.13154/tches.v2020.i2.222-244},
  author={Jose Maria Bermudo Mera and Angshuman Karmakar and Ingrid Verbauwhede},
  year=2020
}