Compact Instruction Set Extensions for Kyber
Lu Li, Guofeng Qin, Yang Yu, Weijia Wang
Abstract
Kyber is the only post-quantum cryptography (PQC) key encapsulation mechanism in the National Institute of Standards and Technology PQC project. This brief investigates the design of compact instruction set extensions (ISEs) for Kyber. We focus on implementing number-theoretic transform (NTT) and propose a hardware design of the modular multiplication based on an optimized <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$k^{2}$ </tex-math></inline-formula> -reduction. Compared to other works, our design is more compact since the optimized <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$k^{2}$ </tex-math></inline-formula> -reduction comprises multiplications with significantly smaller multipliers than Montgomery reduction and Barrett reduction. Then, we integrate the <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$k^{2}$ </tex-math></inline-formula> -reduction into an instruction for the butterfly transformation. We also propose auxiliary instructions that can switch the half words between two registers to facilitate the rearranging coefficients in NTT. To showcase the advantage of the instructions, we implement the ISEs in a chip design for the Hummingbird E203 core. Compared to the software implementation on RISC-V with assembly code, our co-design implementations for NTT show a speedup by a factor of 2.6. Besides, the area overhead is 93 LUTs and 1 DSP without any additional resources of FFs and RAMs using Artix-7 FPGA, which is more compact than previous software–hardware co-designs of Kyber.