MG-PM: A Mixed-Granularity Polynomial Multiplier for High-Efficient Computation Across Variable Degrees

Polynomial multiplication across variable degrees has been a dominant bottleneck in cryptographic applications, including post-quantum cryptography (PQC) to fully homomorphic encryption (FHE). Yet, none of the existing approaches can achieve both high performance and scalability across variable degrees. Number theoretic transform (NTT) excels at large degrees but suffers from performance degradation when the polynomial is decomposed into small degrees, while the iterative convolution algorithm (ICA) scales poorly to large degrees. Reconciling two disparate approaches has been hindered by a mathematical barrier: NTT decomposition produces heterogeneous polynomial rings that defy uniform ICA processing. This work overcomes this barrier by establishing a new algorithm, based on isomorphic mapping, to transform heterogeneous rings into a fixed-size cyclic ring. Leveraging this algorithm, we propose a scalable architecture called MG-PM, a mixed-granularity polynomial multiplier that, for the first time, enables efficient acceleration across variable degrees. Implemented on a Xilinx VCU118 FPGA, MG-PM supports degrees from 256 to 65 536, achieving up to$\mathbf {9.1\times }$latency reduction and$\mathbf {2.2\times }$area reduction under different configurations, as well as 92.3% improvement in area-time product (ATP) compared with other state-of-the-art designs, establishing MG-PM as a highly efficient and scalable solution for accelerating polynomial multiplication across variable degrees.