Paper 2021/711

The Matrix Reloaded: Multiplication Strategies in FrodoKEM

Joppe W. Bos, Maximilian Ofner, Joost Renes, Tobias Schneider, and Christine van Vredendaal

Abstract

Lattice-based schemes are promising candidates to replace the current public-key cryptographic infrastructure in wake of the looming threat of quantum computers. One of the Round 3 candidates of the ongoing NIST post-quantum standardization effort is FrodoKEM. It was designed to provide conservative security, which comes with the caveat that implementations are often bigger and slower compared to alternative schemes. In particular, the most time-consuming arithmetic operation of FrodoKEM is the multiplication of matrices with entries in Z_q. In this work, we investigate the performance of different matrix multiplication approaches in the specific setting of FrodoKEM. We consider both optimized “naïve” matrix multiplication with cubic complexity, as well as the Strassen multiplication algorithm which has a lower asymptotic run-time complexity. Our results show that for the proposed parameter sets of FrodoKEM we can improve over the state-of-the-art implementation with a row-wise blocking and packing approach, denoted as RWCF in the following. For the matrix multiplication in FrodoKEM, this results in a factor two speed-up. The impact of these improvements on the full decapsulation operation is up to 22 percent. We additionally show that for batching use-cases, where many inputs are processed at once, the Strassen approach can be the best choice from batch size 8 upwards. For a practically-relevant batch size of 128 inputs the observed speed-up is in the range of 5 to 11 percent over using the efficient RWCF approach and this speed-up grows with the batch size.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. Minor revision.
Keywords
Post-Quantum CryptographyMatrix MultiplicationSoftware ImplementationStrassen
Contact author(s)
joost renes @ nxp com
joppe bos @ nxp com
christine van vredendaal @ nxp com
tobias schneider @ nxp com
m ofner @ student tugraz at
History
2021-05-28: received
Short URL
https://ia.cr/2021/711
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/711,
      author = {Joppe W.  Bos and Maximilian Ofner and Joost Renes and Tobias Schneider and Christine van Vredendaal},
      title = {The Matrix Reloaded: Multiplication Strategies in FrodoKEM},
      howpublished = {Cryptology ePrint Archive, Paper 2021/711},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/711}},
      url = {https://eprint.iacr.org/2021/711}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.