I. Introduction

Conventional cryptosystems such as RSA and elliptic curve cryptography (ECC) can be solved in polynomial time with the algorithms proposed by Shor using a quantum computer ⁽¹⁾. To replace these classic cryptosystems, post-quantum cryptosystems offering higher levels of security have been researched recently. Among the existing post-quantum cryptosystems, ring-LWE cryptography is a promising candidate because its security is based on the worst-case hardness problem ⁽²⁾. The basic concept of ring-LWE cryptography can be found in ^(2,3). The block diagram of a ring-LWE cryptosystem is shown in Fig. 1. The input message m is encrypted into ciphertext $\left(c_{1}, \quad c_{2}\right)$ using arithmetic computation on public key (a, p) and error polynomials e1, e2, and e3. Original message m can be recovered from ciphertext $\left(c_{1}, \quad c_{2}\right)$ and private key $r_2$ through the decryption operation. The arithmetic operations in ring-LWE cryptography include polynomial addition, modulus, and polynomial multiplication, in which polynomial multiplication is the basic and most computationally intensive operation ⁽⁴⁾.

Several architectures to perform polynomial multiplication have been introduced in literatures. Among the existing approaches used to conduct polynomial multiplication, the number theoretic transform (NTT) studied in ^(4-6) is an efficient method. Let $a(x)$ be a polynomial over the ring $\left.R_{q}=Z_{q} / \underline{(} x^{n}+1\right)$. Then, the NTT transform of each coefficient of $a(x)$ and its inverse NTT (INTT) with a primitive n-th root of unity ${\omega}$ can be expressed as follows:

The multiplication of two polynomials $a(x)$ and $b(x)$ is computed as (3), where ∘ denotes a point-wise multiplication, and two polynomials $a^{\prime}(x)$ and $b^{\prime}(x)$ are constructed as shown in (4).

In ⁽⁴⁾, authors implemented an n-point NTT-core architecture using a systolic array to speed up the multiplication process compared with previous studies. However, this architecture is deployed using a single-path delay feedback (SDF), which offers a low throughput and efficiency. In addition, the SDF and multiple-path delay commutator (MDC) architectures deployed in recent researches ^(5,6) are not sufficient to process the polynomial multiplication.

In this work, a multiple-path delay feedback (MDF) based NTT polynomial multiplier offering high efficiency with low latency is presented. By employing the NTT process of two polynomials $a(x)$ and $b(x)$ concurrently, the multiplication latency is reduced considerably. Additionally, the NTT core is designed using MDF architecture to achieve a better performance compared with previous polynomial multipliers.

II. Proposed NTT Polynomial Multiplier

The block diagram of the proposed NTT polynomial multiplication is shown in Fig. 2. To conduct polynomial multiplication, the coefficients of input polynomials $a(x)$ and $b(x)$ are initially multiplied by a factor ${\varphi}$, where ${\varphi}$ ${\equiv}$ ${\omega}$ mod q, to get the polynomials $a^{\prime}(x)$ and $b^{\prime}(x)$. These multiplication results are then transformed using NTT cores, followed by a point-wise multiplication and an INTT computation.

The polynomial multiplication result $c(x)$ is completely computed by multiplying the output of INTT with the factor ${\varphi}$-1. The entire operations of the multiplier are directed by a controller. To speed up the multiplication of the two polynomials $a(x)$ and $b(x)$, negative wrapped convolutions as well as NTT operations are controlled so that the multiplication latency is minimized. Specifically, the two NTT operations NTT($a^{\prime}$) and NTT($b^{\prime}$) are processed simultaneously, resulting in the reduction of one NTT operation compared with the architecture in ⁽⁵⁾. The negative wrapped convolutions of the two input polynomials $a(x)$ and $b(x)$ are also conducted in parallel to decrease the processing time. Fig. 3 shows the timing diagram of the proposed NTT polynomial multiplier. As can be seen from Fig. 3, two computations a ${\times}$ ${\varphi}$ and b ${\times}$ ${\varphi}$ are scheduled to work simultaneously. Two NTT cores transforms NTT($a^{\prime}$) and NTT($b^{\prime}$) also work in parallel. Compared with the conventional architecture presented in ⁽⁵⁾, the proposed architecture offers a reduction in the processing time of one NTT computation and one negative wrapped convolution.

Fig. 4 presents the proposed NTT core using an 8-datapath MDF architecture to process the input data in parallel. Specifically, the coefficients of the input polynomial $a(x)$ are divided into 8 datapaths, which are processed by different processing elements (PE1s, PE2s). Each PE consists of modular reduction units (MR1, MR2), constant multiplier, butterfly unit (BU), and one first-in-first-out (FIFO) register.

III. Results and Comparisons

The proposed NTT polynomial multiplier architecture is synthesized and implemented on a Xilinx Virtex-7 FPGA board. The simulation results and performance comparison are provided in Table 1. As can be seen from Table 1, the number of clock cycles necessary to complete a polynomial multiplication of the proposed architecture is only 226 clock cycles, which is about 6.25% and 8.69% of that of design 1 in ⁽⁴⁾ and the architecture in ⁽⁵⁾, respectively. In addition, the proposed architecture can operate at a higher clock frequency than others, resulting in a reduction in the multiplication latency. To compare the balance between area and latency of the proposed architecture with that of others, a parameter named area-latency product described in ⁽⁴⁾ is used. As presented in Table 1, the proposed polynomial multiplier architecture offers a much lower area-latency product compared with that of other architectures.

IV. Conclusions

An MDF-based NTT polynomial multiplier for ring-LWE cryptography is presented in this paper. By processing the NTT operation of the input polynomials concurrently, the multiplication process is speeded up. The implementation results prove that the proposed NTT polynomial multiplier achieves better performance than previous approaches. Therefore, it can be applied in ring-LWE and lattice-based cryptosystems to boost polynomial multiplication and improve encryption and decryption processes.