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.

Fully Homomorphic Encryption (FHE) allows direct computation on ciphertext without decryption which provides an effectual approach for privacy-preserving computation. Bootstrapping is an useful feature to have in FHE scheme. However, limited by substantial memory requirements and costly computations, it is difficult to put bootstrapping into practice. It’s necessary to implement hardware acceleration for bootstrapping. In this paper, we proposed the first FPGA implementation of TFHE bootstrapping with 128-bit security to our acknowledgement. We designed a fixed distribution access pattern to accelerate polynomial multiplication and the simplified modular reduction circuit is designed to optimize the computations. The high-level pipelines are utilized to reduce the clock cycle consumption. We proposed multiple parallelism-matching architecture to further speed up the bootstrapping procedure. We implement entire bootstrapping scheme with various key unrolling factors on FPGA platform and synthesis an individual computational core in TSMC 28nm for performance evaluation. The experimental results indicate that our bootstrapping scheme can achieve$5.5\times -34 \times $speed up compared with the state-of-art CPU baselines. Compared with previous FPGA design, our acceleration achieves a latency improvement of$6\%-65\%$with higher security.

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.

In this paper, we presented a method of minimizing the number of overlapped partial products in the accumulation of four-term Karatsuba multiplication. This method reduced the summation of 13 overlapped partial products to 9 and the summation of 40 overlapped partial products to 24 in the case of four-term Karatsuba multiplication and eight-term Karatsuba multiplication, respectively. Moreover, to deal with the problem of negative multiplicands introduced by the choice in the evaluation of four-term Karatsuba multiplication, we further presented a method of converting negative multiplicands to non-negative multiplicands. In this way, our method would lead to the reduction of summation complexity and not using signed multipliers. Compared to the original Karatsuba multiplication designs, our proposed Karatsuba-like multiplication with optimal interpolation would lead to up to 7.7% reduction in ADP (area-delay-product) in ASIC implementations, and up to 20.2% reduction in ADP compared with built-in designs of Synopsys Design Compiler.

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.

Modular inverse calculation has critical influence on the efficiency of public-key cryptographic algorithms such as RSA and elliptic curve cryptography. In this work, based on the original single bit left-shift modular inverse algorithm, a multibit left-shift modular inverse hardware algorithm and its implementation are proposed. Our proposed algorithm makes the operands able to be left-shifted by at most 8 bits within one clock cycle as depending on the output bits of the leading zero counting module. This can produce a reduction on the average computation cycles and absolute execution time. Simulations show that the proposed algorithm can reduces to 0.8n cycles from original 2n cycles for two n-bit operands and gains a 40% decrease in execution time, compared with the original algorithm.

Discrete Gaussian distribution plays an essential role in lattice cryptography whereas naive implementations suffer from timing attacks. Unfortunately, conversion to secure constant-time variant incurs severe deterioration in performance. In Knuth-Yao sampling, we demonstrate several properties of the discrete distribution generation tree involving structural features and finite node height. Accordingly we propose a generic method independent of standard deviations, which focuses on minimizing the Boolean expressions for the mapping from input bit strings to output sample values, along with an in-depth efficiency analysis. Two optimization techniques are devised to further propel the minimization by replacing and adjusting nodes. To strike the balance of computational overhead and closeness to optimum, heuristic strategies are introduced. Finally, performance evaluation is conducted both in software and hardware. Running on a 3.4GHz Intel Core i7-6700 processor, our method improves sampling rate by up to 29.5 percent compared to the latest technique. Targeting hardware FPGA devices, our approach can be 2.7 times faster and achieves 57.3 percent resource reduction than the original constant-time Knuth-Yao sampling. Compared to the Cumulative Distribution Table algorithm with fixed step binary search, our sampler can be at least 12.6 times faster and gains 79/61 percent better area-time product than its counterpart without/with BRAM.

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.

Approximate multipliers are applicable in error-resilient applications with relaxed precision constraints, including image processing, multimedia, and data recognition. Such multipliers that sacrifice some accuracy can gain a corresponding increase in electrical performance. This article presents an analysis of the architectures of previously proposed compressors to investigate their performance and accuracy. In this article, we propose five high-accuracy approximate 4–2 compressors with better delay, area, power, and better performance–accuracy tradeoff. Pro1–Pro4 rely on the critical path optimization, while Pro5 derives from the modified sorting technique. This article implements$8 \times 8$and$16 \times 16$multipliers by employing the proposed approximate compressors in TSMC 28 nm. The experimental results indicate that our designs have about 18% delay, 43%–52% area-delay product (ADP) reduction compared to the exact multiplier, and 20%–55% ADP optimization compared to compressors with the same accuracy. This article further verifies the efficacy of the proposed compressors through image blending and matrix multiplication applications.

In this paper, we propose a novel method of modular multiplication which embeds the modular reduction in the evaluation and interpolation parts of the Karatsuba-like multiplication. Before, the modular reduction can only be performed independently between multiplication. However, applying our method, the interpolation of the previous multiplication, modular reduction and evaluation of the next multiplication are merged as a whole step, which leads to the simplification of computations and improvement of parallelism. This method can be applied to the modular multiplication with simple moduli like NIST primes, and for general moduli, we can apply this method by using Montgomery modular multiplication instead.

The SHA-256 algorithm is widely used in the field of security. In this paper, we propose a rescheduling method for the SHA-256 round computation. Based on the proposed rescheduling, we propose a design for SHA-256, in which the critical path is reduced. Our design is implemented on the Xilinx Virtex-4 FPGA. It achieves the throughput of 1984 Mbps with the area of 979 slices. Compared with other designs on FPGA, our design shows a better performance in terms of the throughput.

Large integer multiplication is the critical operation to design a modular multiplier. Karatsuba algorithm(KO algorithm) to split the operands into two parts is generally used to design a large integer multiplier. In this paper, we firstly propose a design of 258-bit multiplier based on KO-3 algorithm deduced by KO algorithm, with which hardware resources can be reduced than KO algorithm. Then we construct a 256-bit four-stage pipelined Montgomery modular multiplier on the base of proposed multiplier. Finally, we implement the design of modular multiplier on Virtex-6 FPGA platform. This design can run at the clock rate of 68 MHz with 187.9k LUTs approximately. In addition, our design can obtain the result of Montgomery modular multiplier for every clock. Compared with other designs on FPGA, our design shows a better performance in term of area-time product.

In this paper, we construct a generalized RNS McLaughlin modular multiplication with non-coprime moduli sets. We use a set of moduli that are non-coprime for RNS in the algorithm to take both the advantage of the fewer multiplications required for a modular multiplication in McLaughlin modular multiplication and the advantage of the moduli sets of similar sizes in classic Montgomery modular multiplication in RNS. This algorithm turns out to be scalable and simple for implementation. Formulas of parameters used for the construction of this algorithm are also presented in this paper.

Karatsuba Multiplication constructs the product of two integers using half-size multiplications along with full-size and double-size additions. The propagation delay in full-size and double-size additions becomes an essential problem when the multiplication is iterated like in Montgomery Modular Multiplication. In this paper, we propose a method using only half-size additions to accelerate Karatsuba-based Montgomery Modular Multiplication. As a result, our implementations based on SMIC-65nm show that our method is efficient and has advantages in delay over normal implementations with similar area and power.

Unpredictable value of carry bit in the summation of carry-sum is an annoying issue preventing carry-sum from being applied to designs with sign extension. In this paper, we propose a methodology to determine the carry bit of the carry-sum form output generated by Booth encoded multiplier without final addition. We discover that this carry bit is a constant "1" in traditional unsigned Modified Booth Encoded (MBE) multiplier, which makes carry-sum form applicable to hierarchy multiplier. Detailed proofs and gate level verification of our discovery is given, and experimental results show more than 20% shorter delay and up to 36% improvement in area-time product compared with non-carry-sum designs.

Large number multiplication has always been an essential operation in cryptographic algorithms. In this paper, we propose Broken-Karatsuba multiplication by applying the non-least-positive form to represent large numbers and dig the parallelism hidden in conventional Karatsuba multiplication. Further, we modify Montgomery modular multiplication algorithm with Broken-Karatsuba multiplication to make it suitable for pipeline implementation with fewer hardware resources. Based on this modified algorithm, a 256-bit two-stage modular multiplier is constructed. There is no stall in the pipeline when performing consecutive modular multiplications and the delay of a modular multiplication is reduced significantly. Implemented on Virtex-6 FPGA platforms, our design outperforms most previous works in terms of modular multiplication latency and area-time product, which makes it suitable for server-side applications.

This paper proposes a high throughput architecture for AES encryption/decryption targeting on the recent FPGAs with 6-input LUTs. Unlike previous works which share multiplicative inverse logics to realize SubBytes and InvSubBytes, the proposed architecture directly employs the look-up-table based Sbox for both SubBytes and InvSubBytes. Efficient reordering and merging techniques are applied to achieve a highly integrated encryption/decryption datapath with reduced area and delay. By sharing Sbox instead of inversion, the encryption datapath remains simple with unchanged MixColumns. For decryption, the linear operations including two inverse Affine functions and InvMixColumns between SubBytes are merged into a new InvMixColumns (NIMC-I) transformation. The NIMC-I is further optimized to reduce resources and share logics with MixColumns. Through loop-unrolling and fair pipelining, the proposed 3-stage subpipelined design achieves 68.82 Gbps on XC7VX330T using 3930 slices and the 5-stage deep-pipelined one achieves 76.19 Gbps on XC6VLX240T using 4426 slices, which outperform previous equivalent designs in terms of throughput per area.

Implementing elliptic curve point multiplication (ECPM) based on residue number system (RNS) can efficiently use FPGA resources. In this paper, we propose a modular reduction method, where a kind of RNS pair is selected to achieve fast reduction. Our reduction method mainly needs several parallel additions while the reduction unit of previous designs require two multiplications which are computed serially. We also present a novel multiplier-and-accumulator (MAC) with modular reduction unit (MAAU), whose reduction unit employs our fast reduction method, and MAC is based on Karatsuba-Ofman method. Compared with the previous classic designs based on Cox-Rower architecture, our reduction method allows our MAAU to take much larger radix r = 66 without increasing the number of the pipeline stages of MAAU while clock frequency keeps relatively high and no more resources are consumed. Taking larger radix leads to reducing the number of modulo, thus reducing the number of the required cycles and accelerating ECPM. Experimental results obtained on FPGA Stratix II show that the point multiplication for any curves of the size 256, 384 and 521 can be accomplished in 0.42, 0.87 and 1.53 ms respectively, which outperform the previous designs.

CBC mode of 3DES encryption has a wider application and higher security than ECB mode. However, there is a bottleneck of 3DES with CBC mode due to an inherent feedback loop from output to input. In this paper, we propose a method to move XOR gates out of the critical path where two XORs in the junction between two adjacent rounds can be merged into a new XOR gate which then can be absorbed into the precomputation of S-box, thus all the XOR gates are eliminated from the critical path. Our ASIC implementation can achieve a throughput of 2.84Gbps at the cost of 5.84K gates which is superior to others.

Inversion over GF(2m) is crucial for cryptographic applications such as elliptic curve cryptography. The commonly used Itoh-Tsujii algorithm (ITA) computes the inversion by an entirely sequential process consisting of multiplications and squarings. In this paper, we first propose a modified ITA algorithm (MITA) for inversion with polynomial basis (PB). The MITA reduces the required clock cycles of ITA inversion by enabling the parallel computation between part of multiplications and squarings. Furthermore, we generalize the MITA to inversion with arbitrary addition chains. Several criteria are proposed to find the optimal addition chains (OACs) leading to the fastest inverters with given hardware resources. Implemented on Xilinx Virtex-4 FPGA, the proposed inversion architecture with a digit-serial multiplier achieves averagely 61% faster speed with 69% less resources than previous designs with normal basis. Using a fully combinational multiplier, the OAC inverters outperform existing PB-based designs by at least 60.9%, 35.1%, 94.9% for m = 163, 233, 283 respectively in terms of area-time product.

In this work, we propose a novel basic element called delay chain feedback loop (DCFL) to generate metastability. Using 16 DCFLs with different delay chains, a new digital true random number generator (TRNG) is constructed. The new TRNG has been implemented on Altera Cyclone II and Altera Cyclone IV FPGAs. The experimental results show that the TRNG is true random which can pass both the NIST and Diehard test after post-processing. The throughput of the new digital TRNG is up to 150 Mbit/s consuming only 298 LUTs which is superior to others.

This brief proposes a double modulus number theoretical transform (NTT) method for million-bit integer multiplication in fully homomorphic encryption. In our method, each NTT point is processed simultaneously under two moduli, and the final result is generated through the Chinese reminder theorem. The employment of double modulus enlarges the permitted NTT sample size from 24 to 32 bits and thus improves the transform efficiency. Based on the proposed double modulus method, we accomplish a VLSI design of million-bit integer multiplier with the Schönhage-Strassen algorithm. Implementation results on Altera Stratix-V FPGA show that this brief is able to compute a product of two 1024k-bit integers every 4.9 ms at the cost of only 7.9k ALUTs and 3.6k registers, which is more area-efficient when compared with the current competitors.

This paper proposes an efficient pipelined architecture of elliptic curve scalar multiplication (ECSM) over GF(2m). The architecture uses a bit-parallel finite field (FF) multiplier accumulator (MAC) based on the Karatsuba-Ofman algorithm. The Montgomery ladder algorithm is modified for better sharing of execution paths. The data path in the architecture is well designed, so that the critical path contains few extra logic primitives apart from the FF MAC. In order to find the optimal number of pipeline stages, scheduling schemes with different pipeline stages are proposed and the ideal placement of pipeline registers is thoroughly analyzed. We implement ECSM over the five binary fields recommended by the National Institute of Standard and Technology on Xilinx Virtex-4 and Virtex-5 field-programmable gate arrays. The three-stage pipelined architecture is shown to have the best performance, which achieves a scalar multiplication over GF(2163) in 6.1 μs using 7354 Slices on Virtex-4. Using Virtex-5, the scalar multiplication for m = 163, 233, 283, 409, and 571 can be achieved in 4.6, 7.9, 10.9, 19.4, and 36.5 μs, respectively, which are faster than previous results.