Cryptology ePrint Archive: Report 2020/1303

Post-Quantum Cryptography with Contemporary Co-Processors: Beyond Kronecker, Schönhage-Strassen & Nussbaumer

Joppe W. Bos and Joost Renes and Christine van Vredendaal

Abstract: There are currently over 30 billion IoT (Internet of Things) devices installed worldwide. To secure these devices from various threats one often relies on public-key cryptographic primitives whose operations can be costly to compute on resource-constrained IoT devices. To support such operations these devices often include a dedicated co-processor for cryptographic procedures, typically in the form of a big integer arithmetic unit. Such existing arithmetic co-processors do not offer the functionality that is expected by upcoming post-quantum cryptographic primitives. Regardless, contemporary systems may exist in the field for many years to come. In this paper we propose the Kronecker+ algorithm for polynomial multiplication in rings of the form Z[X]/(X^n+1): the arithmetic foundation of many lattice-based cryptographic schemes. We discuss how Kronecker+ allows for re-use of existing co-processors for post-quantum cryptography, and in particular directly applies to the various finalists in the post-quantum standardization effort led by NIST. We provide a detailed implementation analysis which highlights the potential of the Kronecker+ technique for commonly available multiplier lengths on contemporary co-processors. We validate this approach with an implementation of the algorithm running on an ARM Cortex-M4 core: the recommended embedded target platform by NIST.

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

Date: received 19 Oct 2020, last revised 26 Jan 2021

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

Available format(s): PDF | BibTeX Citation

Version: 20210126:164840 (All versions of this report)

Short URL: ia.cr/2020/1303


[ Cryptology ePrint archive ]