## CryptoDB

### Paper: 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 DOI: 10.13154/tches.v2020.i2.222-244 URL: https://tches.iacr.org/index.php/TCHES/article/view/8550 Search ePrint Search Google Slides 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.
##### 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
}