A Survey of Polynomial Multiplication With RSA-ECC Coprocessors and Implementations of NIST PQC Round3 KEM Algorithms in Exynos2100

Abstract

Polynomial multiplication is one of the heaviest operations for a lattice-based public key algorithm in Post-Quantum Cryptography (PQC). Many studies have been done to accelerate polynomial multiplication with newly developed hardware accelerators or special CPU instructions. However, another method utilizes previously implemented and commercial hardware accelerators for RSA/elliptic curve cryptography (ECC). Reusing an existing hardware accelerator is advantageous, not only for the cost benefit but also for the improvement in performance. In this case, the developer should adopt the most efficient implementation method for the functions provided by a given legacy hardware accelerator. It is difficult to find an optimized implementation for a given hardware accelerator because there are a variety of methods, and each method depends on the functions provided by the given accelerator. In order to solve the problem, we survey methods for polynomial multiplication using RSA/ECC coprocessors and their application for Learning With Error (LWE)-based KEM algorithms of National Institute of Standards and Technology (NIST) PQC round 3 candidates. We implement all known methods for polynomial multiplication with RSA/ECC coprocessors in a platform, commercial mobile system-on-chip (SoC), the Exynos2100 Smart Secure Platform (SSP). We present and analyze the simulation results for various legacy hardware accelerators and give guidance for optimized implementation.

Keywords

• Polynomial multiplication
• RSA/ECC coprocessor
• Kronecker substitution
• PQC
• post-quantum cryptography
• Lattice-based cryptosystem