KINA: Karatsuba Initiated Novel Accelerator for Ring-Binary-LWE (RBLWE)-Based Post-Quantum Cryptography

• Published in: IEEE transactions on very large scale integration (VLSI) systems 2023-10, Vol.31 (10), p.1-14
• Main Authors: He, Pengzhou, Tu, Yazheng, Xie, Jiafeng, Jacinto, H. S.
• Format: Article
• Language: English
• Subjects: Algorithms; Complexity theory; Computer architecture; Cryptography; Edge computing; Encryption; Hardware acceleration; Internet of Things; Karatsuba initiated novel accelerator (KINA); Lightweight; NIST; Optimization; Optimization techniques; polynomial multiplication; post-quantum cryptography (PQC); Quantum cryptography; ring-binary-learning-with-errors (RBLWE); Transforms; Very large scale integration
• ISSN: 1063-8210; 1557-9999
• DOI: 10.1109/TVLSI.2023.3302289

Along with the National Institute of Standards and Technology (NIST) post-quantum cryptography (PQC) standardization process, lightweight PQC-related research, and development have also gained substantial attention from the research community. Ring-binary-learning-with-errors (RBLWE), a ring variant of binary-LWE (BLWE), has been used to build a promising lightweight PQC scheme for emerging Internet-of-Things (IoT) and edge computing applications, namely the RBLWE-based encryption scheme (RBLWE-ENC). The parameter settings of RBLWE-ENC, however, are not in favor of deploying typical fast algorithms like number theoretic transform (NTT). Following this direction, in this work, we propose a Karatsuba initiated novel accelerator (KINA) for efficient implementation of RBLWE-ENC. Overall, we have made several coherent interdependent stages of efforts to carry out the proposed work: 1) we have innovatively used the Karatsuba algorithm (KA) to derive the major arithmetic operation of RBLWE-ENC into a new form for high-performance operation; 2) we have then effectively mapped the proposed algorithm into an efficient hardware accelerator with the help of a number of optimization techniques; and 3) we have also provided detailed complexity analysis and implementation comparison to demonstrate the superior performance of the proposed KINA, e.g., the proposed design with u=2 involves 64.71% higher throughput and 15.37% less area-delay product (ADP) than the state-of-the-art design for n=512 (Virtex-7). The proposed KINA offers flexible processing speed and is suitable for high-performance applications like IoT servers. This work is expected to be useful for lightweight PQC development.