An Efficient Polynomial Multiplication Accelerator for Lattice-Based Cryptography With a 2-D Winograd-Based Divide-and-Conquer Method

Polynomial multiplication over rings constitutes one of the most computationally expensive operations in lattice-based cryptography. To accelerate it, the algorithm based on divide-and-conquer has received extensive attention because it has no strict parameter restrictions compared with the number theoretic transform (NTT). Among divide-and-conquer algorithms, apart from algorithms like Karatsuba and Schoolbook, the Winograd-based method has emerged as a new approach. This is because it can reduce the amount of computation while maintaining the scalability of parallelism. However, the parameters of the existing Winograd-based polynomial multiplication algorithm are conservative, and there is potential for further reducing the computational load. Therefore, we propose a novel and efficient 2-D Winograd-based polynomial multiplication (2-D WPM) algorithm. In this algorithm, we adopt the 2-D Winograd to alleviate the large denominator divisions and large-number multiplications that occur in the conventional 1-D Winograd as the parameter increases. We also propose a division elimination method to eliminate the inevitable divisions in the 2-D Winograd. When the polynomial length is 1024, compared with Schoolbook, 2-D WPM (<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">${m} =3$</tex-math> </inline-formula>, <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">${r} =3$</tex-math> </inline-formula>) can reduce the number of basic multiplications by 69%. In addition, an efficient polynomial multiplication accelerator for lattice-based cryptography named EPMA is proposed. In EPMA, we design reconfigurable modular arithmetic units to support both prime moduli and power-of-2 moduli. Keeping the full pipelined structure of EPMA, we also fully reuse the input data and the Winograd transformation results to achieve the conservation of hardware resources. EPMA is implemented on Xilinx FPGAs. Compared with previous works on FPGAs, under the same platform and parameters, the area efficiency of EPMA achieves an improvement of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$1.22\times $</tex-math> </inline-formula> to <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$18.02\times $</tex-math> </inline-formula>. Compared with previous works on CPUs and GPUs, the computing speed of EPMA achieves an improvement of 9.25 to <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$1294.51\times $</tex-math> </inline-formula>.