Cryptology ePrint Archive: Report 2020/1303

Polynomial Multiplication with Contemporary Co-Processors: Beyond Kronecker, Schönhage-Strassen & Nussbaumer

Joppe W. Bos and Joost Renes and Christine van Vredendaal

Abstract: We discuss how to efficiently utilize contemporary co-processors used for public-key cryptography for polynomial multiplication in lattice-based cryptography. More precisely, we focus on polynomial multiplication in rings of the form $Z[X]/(X^n + 1)$. We make use of the roots of unity in this ring and construct the Kronecker+ algorithm, a variant of Nussbaumer designed to combine especially well with the Kronecker substitution method, This is a symbolic NTT of variable depth that can be considered a generalization of Harvey’s multipoint Kronecker substitution. Compared to straightforwardly combining Kronecker substitution with the state-ofthe- art symbolic NTT algorithms Nussbaumer or Schönhage-Strassen, we halve the number or the bit size of the multiplied integers, respectively. Kronecker+ directly applies to the polynomial multiplication operations in the lattice-based cryptographic schemes Kyber and Saber, and we provide a detailed implementation analysis for the latter. This analysis highlights the potential of the Kronecker+ technique for commonly available multiplier lengths on contemporary co-processors.

Category / Keywords: public-key cryptography / Polynomial multiplication, Kronecker substitution, Schönhage-Strassen, Nussbaumer, Co-processors

Date: received 19 Oct 2020

Contact author: joost renes at nxp com, joppe bos@nxp com, christine van vredendaal@nxp com

Available format(s): PDF | BibTeX Citation

Version: 20201019:074332 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]