Cryptology ePrint Archive: Report 2021/711

The Matrix Reloaded: Multiplication Strategies in FrodoKEM

Joppe W. Bos and Maximilian Ofner and Joost Renes and 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 nave 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.

Category / Keywords: public-key cryptography / Post-Quantum Cryptography, Matrix Multiplication, Software Implementation, Strassen

Date: received 28 May 2021

Contact author: joost renes at nxp com, joppe bos@nxp com, christine van vredendaal@nxp com, tobias schneider@nxp com, m ofner@student tugraz at

Available format(s): PDF | BibTeX Citation

Version: 20210528:092403 (All versions of this report)

Short URL: ia.cr/2021/711


[ Cryptology ePrint archive ]