SMALL: Scalable Matrix OriginAted Large Integer PoLynomial Multiplication Accelerator for Lattice-Based Post-Quantum Cryptography

Along with the rapid development in quantum computing, more attention has been switched to post-quantum cryptography (PQC) and related research including their hardware implementations. Following this trend, this paper presents a novel strategy to implement a special type of polynomial multiplication used in lattice-based PQC, where the coefficients of two input polynomials are unequal, and modulus and polynomial size are power-of-two numbers (not in favor of deploying number theoretic transform). In particular, we have proposed a Scalable Matrix originAted Large integer poLynomial multiplication Accelerator (SMALL) for flexible and compact implementation of the targeted polynomial multiplication that is constant-time. In total, our efforts include: (i) we have formulated and derived a scalable matrix originated computation strategy for the targeted polynomial multiplication in a general format; (ii) we have then presented the detailed internal structures for the proposed polynomial multiplication accelerator based on novel algorithm-to-architecture design techniques; (iii) we have implemented the proposed accelerator based on two case study PQC schemes to demonstrate the superior efficiency of the proposed design over the state-of-the-art solutions. We hope the outcome of this work will be useful for further PQC development.