High-Speed RLWE-Oriented Polynomial Multiplier Utilizing Karatsuba Algorithm

Lattice-based cryptography (LBC) is one of the promising post-quantum candidates which offers good security and performance. The most time consuming operations in LBC is the polynomial multiplication, which can be performed through widely explored algorithms like schoolbook polynomial multiplication algorithm (SPMA) and Number Theoretic Transform (NTT). However, Karatsuba algorithm with better complexity compared to SPMA, is not widely studied for FPGA implementation of LBC. In this paper, we proposed an optimized SPMA-Karatsuba (SK) architecture with novel technique to implement the negacyclic convolution. The proposed architecture is more than 2.09× faster in expense of 96.06% additional hardware resources compared to the state-of-the-art SPMA architecture. This shows that the combination of SPMA and Karatsuba algorithm can produce hardware architecture with higher speed yet maintain balanced area-time efficiency compared to SPMA-only architecture. This is especially useful for developing IoT edge nodes or gateway devices that require high speed but able to tolerate some additional hardware area.