Facing the threat of large-scale quantum computers to traditional public-key cryptography, the National Institute of Standards and Technology has conducted Post-Quantum Cryptography algorithms evaluation for a long time, and CRYSTALS-Kyber has been selected to enter the standardization process. In the previous literature, hardware designs can significantly improve the performance of CRYSTALS-Kyber, and the most time-consuming operations are Number Theoretic Transform (NTT) and point-wise multiplication (PWM). However, the split-radix algorithm, which has a lower theoretical complexity in the FFT, has rarely been studied in the NTT. In this paper, we studied whether there are advantages of introducing split-radix algorithms into the NTT defined by CRYSTALS-Kyber and detailed derived the split-radix algorithms for the forward and inverse NTT without pre- or post-processing. By further optimizing the split-radix algorithm for the forward NTT, one of the three modular multipliers in the$\boldsymbol{L}$-shaped butterfly unit is replaced by shifting-and-addition, which will reduce the hardware resource consumption. Besides, we proposed a recombined formula for PWM, which reduces the capacity of the intermediate data RAM for PWM by 25%. Together with the proposed hardware scheduling method, the above algorithms can improve performance and save hardware resources.

The attack on quantum computers is an enormous threat to conventional public-key cryptography. Hence, it is crucial to study quantum-resistant cryptosystems. After four rounds of evaluation, the National Institute of Standards and Technology (NIST) has decided to standardize CRYSTALS-Kyber as one of the public-key post-quantum cryptography (PQC) algorithms. In the hardware design of CRYSTALS-Kyber, the polynomial-related calculations are the most time-consuming. In this paper, we present a highly-efficient hardware architecture for CRYSTALS-Kyber. Firstly, we propose the CRYSTALS-Kyber-oriented conflict-free memory mapping scheme with two modes. Based on this scheme, we construct the mixed radix-2/4 NTT/INTT algorithm, which has no pre- or post-processing, for the first time. By using the “lazy-last-layer” trick, the available memory bandwidth of NTT is temporarily increased, and the average performance of NTT is improved. Besides, the point-wise-multiplication (PWM) is performed in a single memory bank by cooperating with the two modes of our memory mapping scheme. This avoids the waste of memory bandwidth, thus avoiding the usage of large FIFOs for the sampled data. Last, we propose an efficient modular multiplier for CRYSTALS-Kyber, and we merge the divide-by-2 operations in the finite field into modular adders and subtractors to reduce resource consumption. This design, which supports all three security levels, is implemented on Xilinx Artix-7 FPGA with 7.3k LUTs, 3.2k FFs, 2.2k Slices, 5 BRAMs, and 4 DSPs. It performs 12% better in area-time-product than other leading designs in the literature.

Number theoretic transform based multiplication is commonly used in Post-quantum cryptography, which is the most resource-consuming operation. In this paper, we propose an area-efficient modular reduction structure for generalized Mersenne primes with interval prediction, and a novel memory access scheme which fetches two data at the same side of a butterfly unit simultaneously. By the interval prediction structure, some adders are eliminated in a modular multiplication. When implement it in 3-stage pipeline mode and synthesize it with TSMC 90nm process, this structure achieves approximate 14.9% less area compared with other designs. The proposed memory access scheme is an in-place scheme. It is more regular than other designs and the two pieces of memory share the same address. Based on this characteristic, we construct an address generator which consumes 40% less area.

The summation of multiple operands in parallel forms part of the critical path in various digital signal processing units. To speedup the summation, high compression ratio counters and compressors are necessary. In this article, we present a novel method of fast saturated binary counters and exact/approximate (4:2) compressors based on the sorting network. The inputs of the counter are asymmetrically divided into two groups and fed into sorting networks to generate reordered sequences, which can be solely represented by one-hot code sequences. Between the reordered sequence and the one-hot code sequence, three special Boolean equations are established, which can significantly simplify the output Boolean expressions of the counter. Using the above method, we construct and further optimize the (7,3) counter that can perform 27.0%, 26.2%, and 52.0% better in maximum than other designs in delay, area-delay product, and power-delay product, respectively. Similarly, the (15,4) counter is constructed, and it achieves approximately 35.3% shorter delay, while it significantly consumes less power and area. The constructed (31,5) counter has approximately 26.7% higher performance with the area increasing instead. When the counters are embedded in a 16×16 bit multiplier, the performance of the multiplier in area delay product and power delay product is 31.8% and 32.1% higher than that embedded in other counter designs, respectively. Besides, we also construct exact/approximate (4:2) compressors based on sorting network, and they are 10.2%-37.4% better in the area-delay product and 22.3%-48.0% better in power-delay product when they are embedded in an 8×8 bit approximate multiplier.