A Fully Pipelined FIFO Based Polynomial Multiplication Hardware Architecture Based On Number Theoretic Transform

Moslem Heidarpur, Mitra Mirhassani, Norman Chang · 2025

Read A Fully Pipelined FIFO Based Polynomial Multiplication Hardware Architecture Based On Number Theoretic Transform by Moslem Heidarpur, Mitra Mirhassani, Norman Chang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-11867.txt.

Introduction

Heidarpur, Mirhassani, and Chang build chip hardware that multiplies large polynomials twice as fast as the best prior designs. Polynomial multiplication sits at the heart of many modern encryption schemes, including ones built to resist quantum attacks. Their 2025 design runs on programmable FPGA chips and uses a number theoretic transform, a number-based cousin of the fast Fourier method.

Data flows through first-in, first-out buffers so every stage works at once, letting the chip finish two polynomials of degree n in about n over two clock cycles. That halves the processing time of the fastest reported work. The design also uses fewer chip resources than that fastest rival. The authors target faster encryption hardware.

Catalog record

CREATORMoslem Heidarpur, Mitra Mirhassani, Norman Chang
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE27 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-11867

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Fully Pipelined FIFO Based Polynomial Multiplication Hardware Architecture Based On Number Theoretic Transform Moslem Heidarpur, Mitra Mirhassani, Norman Chang Abstract This paper presents digital hardware for computing polynomial multiplication using Number Theoretic Transform (NTT), specifically designed for implementation on Field Programmable Gate Arrays (FPGAs). Multiplying two large polynomials applies to many modern encryption schemes, including those based on Ring Learning with Error (RLWE). The proposed design uses First In, First Out (FIFO) buffers to make the design fully pipelined and capable of computing two n n degree polynomials in n / 2 n/2 clock cycles. This hardware proposes a two-fold reduction in the processing time of polynomial multiplication compared to state-of-the-art enabling twice as much encryption in the same amount of time. Despite that, the proposed hardware utilizes fewer resources than the fastest-reported work. 1 1 1 Part of our code is publicly available at https://github.com/mheidarpur/fpntt 1 Introduction Some of the widely used cryptography schemes such RSA [ 12 ] , ECC [ 18 ] , and AES [ 15 ] are based on the hardness of number theoretical problems that are very hard to solve on classical computers. However, quantum computers can solve these problems in polynomial time using the Shor [ 20 ] algorithm. Since quantum computers are becoming a reality [ 1 , 2 ] , pqc ( pqc ) algorithms have gained greater attention. Lattice-based cryptography algorithms such rle ( rle ) [ 19 ] , and NTRU [ 9 ] are among the strong candidates for quantum-safe cryptography. Lattice-based systems are based on the hardness of lattice problems and are believed to resist quantum computer attacks. Furthermore, rle is one of the algorithms that can be used for FHE ( FHE ) [ 7 ] implementations. The encrypted data can be processed using FHE without decrypting it first, which is useful in preserving privacy. Fully homomorphic encryption is not yet quite feasible, mainly due to the large number of computations required to perform homomorphic operations on the encrypted data. Polynomial multiplication is the slowest and the most area-consuming operation in rle cryptography systems. One efficient and fast algorithm widely used to perform polynomial multiplication is ntt ( ntt ) [ 6 , 10 , 16 , 17 , 4 , 13 , 22 , 21 ] . An NTT polynomial multiplier hardware using a systolic array of the n -point NTT-core is presented in [ 16 ] .The work in [ 6 ] used various optimization algorithms to optimize the ntt based polynomial and reduce ROM usage. In [ 17 ] , authors proposed a fast polynomial multiplier using a multi-lane Stockham NTT algorithm. Chen et al. [ 4 ] propose an optimized ntt based polynomial multiplier by selecting an efficient parameter set and a pipelined architecture. Reference [ 13 ] proposed a ntt multiplier to be used as an accelerator for Encrypted Arithmetic Library (SEAL) [ 14 ] . However, to be a suitable candidate for post-quantum cryptography, speed of operations is a very important factor. The works presented in [ 6 , 17 , 4 , 13 ] are slow and therefore, cannot fulfil this need. Additionally, improving the speed of operation is vital for FHE implementation, considering the very large number of computations required. Reviewing the state-of-the-art, there is a gap in research with focus on improving the speed while at the same time having area-efficient ntt multipliers to be used in pqc and FHE devices. This work proposes a novel optimized hardware architecture to perform polynomial multiplication using ntt . The objective is to design a high speed polynomial multiplier while, at the same time, keeping the required resources low when compared with the state-of-art. In order to accomplish this, the order of performing operations was studied so that the pipelined hardware ntt could be completed with a minimal number of clock cycles. fifo ( fifo ) register shift buffers were used instead of memories to store data. Butterfly operations start at each stage of ntt as soon as all required data become available. Since the design is pipelined, it can perform n -point polynomial multiplication in n/2 number of clock cycles which is an increase by factor of two comparing to the fastest work reported. The rest of the paper is organized as follows. Section II reviews the ntt , polynomial multiplication, Karatsuba and Barret reduction algorithms. Section III discusses the architecture of the design. Section IV presents the details of the novel hardware presented for NTT-based pipelined polynomial multiplication. Section V presents the results and comparison with state-of-the-art. Finally, Section VI concludes the paper. 2 Background In Ring-LWE cryptography systems, operations are performed in the ring Rq. It is assumed that the ring is in the form of ringeq , where n is the polynomial degree, q is the modulus of coefficients. Figure 1: Polynomial multiplication using NTT and negative wrapped convolution could be divided into five steps. Considering a(x)=\sum^{i=N-1}_{i=0}a_{i}x^{i} and b(x)=\sum^{i=N-1}_{i=0}b_{i}x^{i} are two polynomial in the ring ringeq , multiplication is performed as followed: c(x)=a(x)\times b(x)=\sum^{N-1}_{i=0}\sum^{N-1}_{j=0}a_{i}b_{j}x^{i+j}~mod~x^{N+1} (1) The c(x) has a complexity of \mathcal{O}(N^{2}) , which is high. The aim is to reduce the complexity using approaches such as ka ( ka ) [ 23 , 8 ] , Toom-Cook [ 5 ] , or ntt [ 10 ] . The ntt is one of the common techniques to efficiently implement polynomial multiplications with the reduced complexity of \mathcal{O}(Nlog(N)) . NTT Multiplication : For NTT operations, the value of N should be a power of two, therefore, to multiply the two polynomials a(x) and b(x) are padded with zeros to create N -point polynomials \tilde{a}(x) and \tilde{b}(x) . The NTT operation transforms an N -point polynomial \tilde{a}(x) into a N -point NTT version, \tilde{A}(x) : \tilde{A}(x)=NTT\left(\tilde{a}(x)\right)=\sum^{N-1}_{i=0}\tilde{A}_{i}x^{i} (2) The term \tilde{A}_{i} represents the NTT coefficients and is defined as follows: \tilde{A}_{i}=\sum^{N-1}_{j=0}a_{i}\omega^{ij} (3) The constant \omega , named the twiddle factor, should satisfy the condition \omega^{N}\equiv 1~mod~M , and \omega^{i}\not\equiv 1~mod~M \forall~i<N , where M\equiv 1~mod~N The multiplication output, c(x) , is then computed by taking the inverse NTT: c(x)=NTT^{-1}\left(\tilde{A}(x).\tilde{B}(x)\right) (4) However, to avoid the process of zero padding, a fft ( fft )-based weighted NTT can be used [ 11 ] . This method, called negative wrapped convolution reduces the length of the NTT values by eliminating the need for zero padding. Fast Fourier Transform (FFT)-based weighted NTT : Multiplication using the negative wrapped convolution requires selecting a weighing coefficient ( \phi ). If \phi\equiv 1~mod~2N , then NTT multiplication result has mod~x^{N}+1 does not need any polynomial reduction [ 11 ] . The added cost is that coefficients need to be weighed before taking NTT and after performing the inverse NTT. Multiplication steps based on this approach, depicted in Fig. 1 , are described as follows: 1. Multiply each element of the polynomials by \phi^{i} to construct weighted polynomials: \hat{a_{i}}=(a_{i}\times\phi^{i})~mod~M \hat{b_{i}}=(b_{i}\times\phi^{i})~mod~M 2. Perform NTT on the weighted polynomials: \hat{A}(x)=NTT(\hat{a}(x)) \hat{B}(x)=NTT(\hat{b}(x)) 3. Element-wise multiplication of \hat{A} and \hat{B} . \bar{C}_{i}=(\hat{A_{i}}\times\hat{B_{i}})~mod~M 4. Take inverse NTT of \bar{C} C=NTT^{-1}(\bar{C}) 5. Scale and multiply each element of {C} by \phi^{-i} to obtain the multiplication result c_{i}={C_{i}}\times\phi^{-i} To optimize the critical path of the hardware, multiplication can be broken into smaller sub-multiplications.

Read the complete text