1. NTT Polynomial Multiplication

Lattice-based cryptosystems carry out the encryption and decryption of problems such as Ring-Learning with Error (Ring-LWE) ^[30,31] and Module Learning with Error (Module-LWE) ^[32] by performing polynomial addition, multiplication, and modulo operations on a finite ring. Because polynomial multiplication has higher complexity compared to other arithmetic operations, it is essential to implement efficient polynomial multiplication for lattice-based cryptographic hardware. The finite ring is defined as $R_q=Z_q[x] / f(x)$, where $q \equiv 1(\bmod 2 N)$ is a prime number and $f(x)=x^N+1$ is an irreducible polynomial of degree $N$ [33]. Any two polynomials $a(x), b(x)$ on the finite ring $R_q$ can be expressed as

A polynomial $c(x)$ of length $2 N-1$ can be obtained by multiplying two polynomials of length $N$, and the coefficient of $c(x)$ can be calculated with (2).

Since (2) representing polynomial multiplication is the same as the operation to obtain the discrete convolution c(x)=a(x)*b(x), polynomial multiplication can be calculated with discrete convolution. However, the convolution operation in (2) has a large operation quantity of O(N$^{2}$), so it is generally processed as multiplication through domain transformation. The coefficient of the polynomial can be changed into the frequency domain using Discrete Fourier Transform (DFT). Instead of the time domain convolution operation, pointwise multiplications for coefficients of a(x) and b(x) are carried out, in the frequency domain. Finally, inverse DFT (IDFT) of c(x) in the frequency domain is performed to obtain the c(x) of the time domain.

In this case, the lengths of a(x) adn b(x) must be adjusted to 2N-1, which is the length of c(x), for DFT and IDFT, and zero-padding is necessary ^[23].

However, the DFT and IDFT also have an operation quantity of O(N$^{2}$). The FFT algorithm, well known as a method to transform the domain quickly by reducing the operation quantity, is applied. The DFT of (4) can reduce the operation quantity to O(N log N) as shown in (5) through the divide-and-conquer method by using the periodic and conjugate properties of $W_N^{i j}$.

Furthermore, a complex number-based operation for FFT can be replaced with a integer number-based operation by employing NTT while maintaining the properties of FFT ^[22,23]. As shown in Fig. 1(a), in FFT, $W_N=e^{j 2 \pi / N}$ is defined as a primitive root, and as shown in Fig. 1(b), in NTT, $W_{N}$modq=1 is defined as a primitive root ^[34]. NTT and inverse NTT (INTT) are expressed with the following (6) and (7).

Accordingly, (3) representing the DFT-based polynomial multiplication operation ^[35] can be expressed as (8) representing NTT-based polynomial multiplication.

Finally, a negative wrapped convolution that efficiently removes the zero-padding that occurs in the NTT and INTT processes of (8) was proposed ^[36]. According to ^[36], the zero-padding process that may occur during NTT-based polynomial multiplication can be omitted by multiplying the coefficients of the two polynomials by ψ that satisfies ψ ≡ W mod q. The two polynomial coefficients multiplied by ψ are expressed as $a'(x)=a_{0}+\psi a_{1}x+\cdots +\psi ^{n-1}a_{n-1}x^{n-1}$ and$b'(x)=b_{0}+$ $\psi b_{1}x+\cdots +\psi ^{n-1}b_{n-1}x^{n-1}$. As a result, (8) can be expressed

In conclusion, polynomial multiplication using NTT can be performed reducing the computational complexity from O(N$^{2}$) to O(N log N) through integer operation instead of complex numbers.

Fig. 1. Primitive root for N = 16.

2. General NTT Processor

Fig. 2 shows a typical polynomial multiplier architecture that implements (9), where DIF and DIT represent decimation-in-frequency (DIF) and decimation-in-time (DIT), respectively ^[35]. If the same decimation is used for all NTTs and INTTs, it is inevitable to add a bit-reversal circuit to every NTT or INTT ^[35]. In order to completely remove the added bit-reversal circuit, the DIF structure, in which the output is bit-reversal converted when the inputs are sequential, is generally applied to the front NTT, and the DIT structure, in which bit-reversal inputs are sequentially converted and output, is applied to the rear INTT as shown in Fig. 2. Since the DIT and DIF algorithms are structurally symmetric ^[35], and one of the NTT and INTT structures can be easily derived by applying the other structure, this paper will mainly explain the structure of the DIF NTT processor.

Fig. 2. Overall structure for NTT polynomial multiplication.

A. Fully-parallel Architecture

Fig. 3 shows the DIF NTT processor of a fully-parallel architecture with N=16, q=17, and W$_{N}$=3. NTT for N=16 points is performed over n steps, and N/2 processing elements (PEs) are required for each step, where n is log$_{2}$N. In order to perform the NTT operation in (6), PE consists of one radix-2 butterfly unit, three modular reduction units (MR), and one multiplier. The basic PE is similar to the structure of the FFT, but in accordance with the characteristics of the lattice-based cryptoprocessor that must be operated on R$_{q}$, modular reduction is additionally required in the transformation process over n steps. In this paper, among various implementations including Barrett and Montgomery modular reduction ^[37-39], ^[39] is used to limit the result of each operation to log$_{2}$N=4bits.

Fig. 3. Fully-parallel architecture for N = 16.}

As shown in Fig. 3, PE operation is performed at every s stage (1 ${\leq}$ s ${\leq}$ n) and the PE of the next stage is performed after rearranging the data. According to ^[24], data reordering performs rearrangement while satisfying the following properties.

NTT pair property: pairs of data processed simultaneously in the PEs at stage s differ in b$_{n-s}$ for any N-point NTT with n=log$_{2}$N stages.

For instance, the PEs begin by operating on pairs of data with indexes (0,8), (1,9), (2,10), (3,11), and so forth after the first stage. By converting these indices to binary, we obtain (0000,1000), (0001,1001), (0010,1010), and (0011,1011). Comparing the indices in each pair reveals that they are identical except for the most significant bit, b$_{3}$=b$_{4-1}$. This is true for all the pairs of indices at stage 1. By repeating the analysis for stage 2 and 3, it is clear that the indices of pairs of data processed by the PEs differ only in b$_{2}$ and b$_{1}$, respectively. As a result, we can conclude that the NTT architecture is correct only when the data pairs input during the same clock period in all PEs differ in the index bits b$_{n-s}$. This will serve as the foundation for the following explanations of the other structures.

B. Partially-parallel Architecture

As can be observed in Fig. 3, since the fully-parallel architecture simultaneously computes N data through a total of (N/2)log$_{2}$N PEs and reordering networks by stage, it has high throughput of N points per clock cycle. However, in terms of hardware complexity, it has a severe disadvantage that the required number of PEs increases linearly as N increases. To alleviate the high hardware complexity of the fully-parallel architecture, a partially- parallel architecture that simultaneously processes P=2$^{p}$ data according to parallel factor P has emerged. Fig. 4 shows the general structure of the partially-parallel NTT. The partially-parallel structure is composed of n stages connected in series with data flowing from stage 1 to stage n. Since each stage contains P inputs and P outputs, N data points are subdivided into N / P number of P points and thus the throughput becomes P data per clock cycle. Note that each stage s of the architecture performs all calculations associated with one stage of the NTT algorithm.

To convert the fully-parallel architecture shown in Fig. 3 to the partially-parallel architecture shown in Fig. 4, data rearrangement must be considered. The output pair with the natural order of s stage is rearranged while satisfying the pair property in the next s + 1 stage. The partially-parallel architecture is largely divided into a feedback type ^[26,27] and a feedforward type ^[28,29] according to the data rearrangement processing method. First, the feedback type shown in Fig. 5(a) proceeds with data reordering using a feedback loop. In this case, some output of butterfly unit (BF) is fed back as the delay element at the same stage through the feedback loop, so the operation of the input pair where a difference of b$_{n-s}$ occurs in the next stage. On the other hand, in the feedforward type shown in Fig. 5(b), the data processed from the PE of each stage uses a separate reordering circuit to match the input pair with a difference of b$_{n-s}$ in the next stage.

Fig. 4. General partially-parallel architecture.}

Fig. 5. Feedback and feedforward architecture.

1. Single-path Delay Feedback (SDF) Design

Fig. 6 shows the $N=16$ point SDF design, which is a representative design based on feedback. The SDF design has serial data flow because it uses a single path and satisfies the NTT pair property using the delay element of the feedback loop ^[26]. SDF receives data at each stage in the natural order of the index from 0 to 15. For serial data flow, pairs of data that differ by b$_{n-s}$ arrive with a difference of 2$^{n-s}$ clock cycles according to the natural order. At each stage, a buffer of length L=2$^{n-s}$ is used to store these pairs of data concurrently. Thus, the buffer’s output is calculated simultaneously with the stage’s input in the PE. Following that, one of the butterfly’s outputs is sent to the multiplier, while the other is placed in the buffer. As illustrated in Fig. 6, each stage consists of one BF, one multiplier, three MRs, and a FIFO with a length of L=2$^{n-s}$. When all hardware resources are added for all stage s={1,···,n}, log$_{2}$N BFs, log$_{2}$N multipliers, 3log$_{2}$N MRs, and log$_{2}$N FIFO are required in total. Compared to the fully-parallel architecture shown in Fig. 3, the SDF design ^[26] can overwhelmingly improve the hardware complexity problem because it uses a single path. However, it has the problem that the hardware throughput is processing one data per clock due to serial data flow, and hardware utilization is reduced to 50% due to the feedback loop.

Fig. 6. The SDF architecture for N = 16.}

2. Multi-path Delay Feedback (MDF) Design

The MDF design ^[27] is the parallel version of the SDF design ^[26]. Fig. 7 shows a 16-point 4-parallel MDF design, which consists of the first independent serial PEs and the second combining parallel PEs. Let us compare the SDF in Fig. 6 and MDF in Fig. 7. Whereas data in the SDF ^[26] is processed in series in natural order from stage 1 to n = 4, MDF processes P data flow independently through the first serial PEs and combines P data flow through the second parallel PEs ^[27]. The first serial PEs are the same as the original SDF ^[26] except for the fact that the length of the buffers in MDF ^[27] is divided by P with respect to those in the SDF ^[26]. Since each independent serial part provides parallel streams that differ in the bit b$_{n-s}$, the remaining parallel part simply combines those parallel streams with shuffling circuits. The general P-parallel MDF ^[27] uses $P\log _{2}(N/P)$ $+(P/2)\log _{2}P\,\mathrm{BFs},$ $P\log _{2}(N/P)+(P/2)\log _{2}P$ multi-pliers, $3(P\log _{2}(N/P)+(P/2)\log _{2}P)$ MRs, and $N-P$ FIFO. Consequently, the MDF design ^[27] can parallelize the SDF design ^[26] by P=2$^{p}$ to improve the throughput by P times. However, it uses approximately P times more hardware than the SDF design ^[26], and like the SDF design ^[26], it fails to achieve full hardware utilization.

Fig. 7. The MDF architecture for N = 16 and P = 4.}

3. Single-path Delay Commutator (SDC) Design

In comparison to feedback designs ^[26,27], feedforward designs ^[28,29] incorporate additional reordering circuitry to ensure that the NTT pair property is satisfied. Fig. 8 illustrates a 16-point SDC for serial data processing. Despite the fact that the SDC processes serial data ^[28], it is based on the 2-parallel MDC depicted in Fig. 9(a). Let us begin with the 2-parallel MDC ^[29]. In 2-parallel MDC ^[29], it is assumed that input data differentiated in bit arrive, but the data order is not consistent between stages, necessitating the participation of shuffling circuits to reorder the data as shown in Fig. 9(a). The reordering circuits consist of upper and lower paths, each of which demands buffers and multiplexers to satisfy the NTT pair property. First, the lower path is delayed using the buffers, and then both upper and lower sets of data are swapped using multiplexers. Lastly, the upper path is delayed using buffers, resulting in an aligned data pair.

The SDC in Fig. 8 receives input data in series. The only difference between SDC ^[28] and 2-parallel MDC ^[29] is in the data input and output. As shown in Fig. 8, the first half of the data is routed through the input buffer, while the second half is connected to the SDC’s lower input ^[28]. Finally, the output is serialized once again. Due to data parallelization, SDC ^[28] is only operational 50% of the time, with the remaining 50% used to receive and produce data. The general SDC employs a total of log$_{2}$N BFs, log$_{2}$N multipliers, 3log$_{2}$N MRs, and 2(N-1) FIFO in terms of hardware resources.

Fig. 8. The SDC architecture for N = 16.}

Fig. 9. The MDC architecture for N = 16 and P = 2 and 4.

4. Multi-path Delay Commutator (MDC) Design

The MDC design has a parallel design with a higher parallel factor because it uses high-radix for radix-2 based 2-parallel MDC ^[29]. Fig. 9(a) and (b) show the 2-parallel MDC and 4-parallel MDC designs, respectively. The 2-parallel MDC ^[29] has the same structure as the SDC design ^[28] after removing additional input/output circuits required for serial processing. Fig. 9(a) processes two data per one PE and processes two data per clock based on radix-2, and one stage of the 2-parallel MDC shown in Fig. 9(a) carries out the operation assigned to one stage of the fully-parallel architecture ^[26]. On the other hand, Fig. 9(b) processes four data per one PE and four data per clock based on radix-4. One stage of the 4-parallel MDC in Fig. 9(b) performs the operations assigned to two successive stages of the 2-parallel MDC. A typical P-parallel MDC design ^[29] requires$P\log _{p}N$ BFs, $(P-1)\log _{p}N$multipliers, $2(P-1)\log _{p}N$ MRs, and $N-P$ FIFO.

In conclusion, the P-parallel MDC design ^[29] achieves a throughput improvement by P times by changing the 2-radix structure of the 2-parallel MDC design to the P-radix structure. Due to the limit on the use of the trivial multiplier, the high radix application of the NTT does not significantly improve performance. In addition, it has the disadvantage that hardware utilization is limited by P times due to the input/output delay circuit.

1. Proposed Partially-parallel NTT Algorithm

The proposed new partially-parallel NTT design begins with analyzing the data rearrangement processes to transform them to fit the given parallel factors. Fig. 10 shows the rearrangement processes extracted from the 16-point fully-parallel architecture in Fig. 3. The input of the reordering circuit has a pair that differs only in b$_{n-s}$ bits at stage s and satisfies the pair property, and the output of the reordering circuit are described in natural order. For example, in the fully-parallel architecture for N = 16 points in Fig. 3, the NTT algorithm is performed from stage 1 to 4, in reordering 1 shown in Fig. 10(a), there is a difference in b$_{4-1}$=b$_{3}$ in each pair, and in reordering 2 shown in Fig. 10(b), there is a difference in the b$_{4-2}$=b$_{2}$ bit of each pair. Similarly, in reordering 3 shown in Fig. 10(c), it can be seen that b$_{1}$ of the pair are different. In the previous NTT structure including SDF ^[26], MDF ^[27], SDC ^[28], and MDC ^[29], it can be seen that the NTT pair property is satisfied for all data pairs in the NTT processing process regardless of serial and parallel data flow, feedback and feedforward types ^[26-29].

In order to derive the proposed partially-parallel architecture based on Fig. 10, a new scheduling task should be performed that transforms each of N×1 matrices into P×(N/ P) matrices. Fig. 10 and 11 represent 16×1 matrices and 4×4 matrices for reordering, respectively. For matrix representation, the column of the matrix means one clock cycle and the row means the number of data processed per one clock cycle. Note that P row determines the number of PEs as P/2 to process P data in parallel. The P×(N/P) matrix represents P data in one clock for N/P clock cycles to process the entire N data. Whereas the 16×1 matrices shown in Fig. 10 rearranges sixteen data at a single clock in a fully-parallel manner, the 4×4 matrices shown in Fig. 11 processes four data for four clock cycles in a partially-parallel manner. As with the transformed 16×1 matrix where the NTT pair property is maintained, the NTT pair property is also maintained in all 4×4 matrices.

More importantly, through transformation into 4×4 matrices, the data pair that needs swapping can be identified out of the entire 16 data. The pairs that require swapping are highlighted in Fig. 11 and summarized as follows:

Stage 1: (1,8), (3,10), (5,12), (7,14)

Stage 2: (1,4), (3,6), (9,12), (11,14)

Stage 3: (1,2), (5,6), (9,10), (13,14)

As shown in Fig. 11, the swapping pairs in stages 1 and 2 require delay factors as much as 2 and 1, and the swapping pairs in stage 3 does not require any delay.

In order to satisfy the NTT pair property by changing the 16×1 matrix of the fully-parallel architecture to the 4×4 matrix of the partially-parallel architecture, the design of a reordering circuit that performs swapping to an appropriate clock is carefully designed. In this case, the required hardware structure varies depending on whether there is a delay between swapping data and inter/intra-PE. To explain in more detail, the reordering circuit used in SDC ^[28] and MDC ^[29] is suitable in cases where delay is required, as with stage 1 and stage 2, and swapping occurs in intra-PE. Upper and lower paths of reordering circuits can be exchanged with the desired delay difference through the FIFO and multiplexers of each path. Additionally, as with stage 3, when swapping occurs between inter-PEs without requiring delay, it is easy to implement simple hardwiring similar to the last combining circuitry of MDF ^[27]. Since the replacement data pair already occurs in the same clock, data rearrangement can be completed with a simple interconnection without delay.

Fig. 10. Reordering analysis of (a) reordering 1; (b) reordering 2; (c) reordering 3.

Fig. 11. 4${\times}$4 matrix representation for (a) reordering 1; (b) reordering 2; (c) reordering 3.

2. Proposed Partially-parallel NTT Structure

With the matrix transformation, analysis, and derivation of a rearrangement circuit, the finally proposed 4-parallel structure for 16-point NTT is as shown in Fig. 12. Basically, since P data are processed in parallel per clock cycle, each stage consists of P/2 PEs, and a rearrangement circuit depicted in Fig. 11 was added between each stage to operate to fit the matrix operation. Between stage 1 and stage 2, a feedforward type reordering circuit was built with delay times 2 and 1, and in stage 3, they were interconnected with hardwiring. In conclusion, two independent MDC designs ^[29] operate in 2-parallel in the front part of the proposed partially-parallel NTT architecture, and parallel structures similar to MDF design ^[27] combine independent streams in the rear part. In other words, the overall structure is similar to the MDF design in Fig. 7, but the internal structure is composed of the 2-parallel MDC design in Fig. 9, not the feedback-based SDF in Fig. 6. To sum up, the proposed NTT processor requires $(P/2)\log _{2}N\,\mathrm{BFs},$ $(P/2)\log _{2}N$ multipliers, $3(P/2)\log _{2}N$MRs, and N-P FIFO for partially-parallel P. The proposed partially-parallel architecture can achieve 100% hardware utilization because it does not internally include the feedback loop that MDF ^[27] has and minimizes the waste of the delay element of the reordering circuit due to the high radix of MDC ^[29]. In conclusion, it is possible to provide higher throughput compared to SDF ^[26] and SDC ^[28] while absorbing all the advantages of MDF ^[27] and MDC ^[29]. Consequently, the design method for the proposed partially-parallel architecture can be described as follows:

1) Create n-1 pieces of N×1 matrices by reordering for a fully-parallel architecture

2) Transform the N×1 matrices into n−1 pieces of P×(N/P) matrices by stage for a partially-parallel architecture

3) Check swapping data by stage and configure the reordering circuit

4) Place P/2 PEs for each stage and interconnect them with the reordering circuit

Fig. 13 shows practical examples of N = 512, q = 12,289, W = 3 using the design method above. While changing the parallel factor to 4, 8, and 16, it can be seen that the above systematic design method is applied regardless of the NTT length and parallel factor. Note that if the parallel factor P is 2, the proposed partially-parallel structure will become a 2-parallel MDC ^[29], and if the parallel factor P is equal to the NTT length N, the proposed partially-parallel architecture will become a fully-parallel architecture ^[26]. It is important to note that since the proposed partially-parallel architecture proposes a comprehensive structure and can be applied to any P, it is possible to implement the most efficient NTT processor under the constraints by selecting a P suitable for the design environment.

Fig. 12. The proposed partially-parallel design for N = 16 and P = 4.}

Fig. 13. The proposed partially-parallel design for N = 512 and P = 4, 8, and 16.