TheNth-degree truncated polynomial ring units (NTRUs)-based postquantum cryptography (PQC) has drawn significant attention from the research communities, e.g., the National Institute of Standards and Technology (NIST) PQC standardization process selected algorithm Fast Fourier lattice-based compact (Falcon). Following the research trend, efficient hardware accelerator design for polynomial multiplication (an important component of the NTRU-based PQC) is crucial. Unlike the commonly used number theoretic transform (NTT) method, in this article, we have presented a novel SChoolbook-Originated Polynomial multiplication accElerators (SCOPE) design framework. Overall, we have proposed the schoolbook-based method in an innovative format to implement the targeted polynomial multiplication, first through a schoolbook-variant version and then through a Toeplitz matrix-vector product (TMVP)-based approach. Four layers of coherent and interdependent efforts have been carried out: 1) a novel lookup table (LUT)-based point-wise multiplier is proposed along with a related modular reduction technique to obtain optimal implementation; 2) a new hardware accelerator is introduced for the targeted polynomial multiplication, deploying the proposed point-wise multiplier; 3) the proposed architecture is extended to a TMVP-based polynomial multiplication accelerator; and 4) the efficiency of the proposed accelerators is demonstrated through implementation and comparison. Finally, the proposed design strategy is also extended to another NTRU-based scheme and other schoolbook- and toom-cook-based polynomial multiplications (used in other PQC), and obtains the same superior performance. We hope that the outcome of this research can impact the ongoing NIST PQC standardization process and related full-hardware implementation work for schemes like Falcon.

Postquantum cryptography (PQC) has recently garnered significant attention across various communities. Alongside the ongoing standardization process for general-purpose PQC algorithms by the National Institute of Standards and Technology (NIST), the research community is actively exploring the realm of lightweight PQC schemes. A ring-binary-learning-with-error (RBLWE)-based encryption scheme (RBLWE-ENC) is a promising lightweight PQC candidate suitable for Internet-of-Things (IoT) and edge computing applications. The parameters of the RBLWE-ENC, however, do not favor deploying typical fast algorithms, such as number-theoretic transform (NTT). In this article, therefore, we propose to design aToeplitz matrix-vector product (TMVP)-initiatednovelaccelerator (TINA) for RBLWE-ENC. We innovatively used TMVP (a subquadratic-complexity fast algorithm for polynomial multiplication) to derive the significant arithmetic operation of RBLWE-ENC into a new form for high-performance operation. This novel formulation culminates in the development of a comprehensive accelerator known as TINA. Through implementation and comparative analysis, we demonstrate the efficiency gains achieved by our proposed accelerator. To the authors’ best knowledge, this is the first report on the TMVP strategy-initiated RBLWE-ENC accelerator. The findings of this work are expected to provide valuable references in the ongoing advancement of lightweight PQC development.

We present a probabilistic polynomial-time reduction from the lattice Bounded Distance Decoding (BDD) problem with parameter 1/( sqrt(2) * gamma) to the unique Shortest Vector Problem (uSVP) with parameter gamma for any gamma > 1 that is polynomial in the lattice dimension n. It improves the BDD to uSVP reductions of [Lyubashevsky and Micciancio, CRYPTO, 2009] and [Liu, Wang, Xu and Zheng, Inf. Process. Lett., 2014], which rely on Kannan's embedding technique. The main ingredient to the improvement is the use of Khot's lattice sparsification [Khot, FOCS, 2003] before resorting to Kannan's embedding, in order to boost the uSVP parameter.