An Area-efficient Twiddle Factor Generator for Fully Homomorphic Encryption

In modern cryptography, fully homomorphic encryption (FHE) and post-quantum cryptography (PQC) rely heavily on number theory transformation (NTT) to accelerate polynomial multiplication. As the polynomial dimension increases, the twiddle factor required for NTT operations has an increasingly serious impact on the system as a whole, not only consuming a large amount of storage space, Meanwhile, the transmission of a large number of twiddle factors will also lead to a decrease in the overall computing speed. To address this issue, this paper analyzes the twiddle factor scheduling under negative wrapped convolution and proposes a pseudo-quadtree register covering scheme. Through data generation and covering, the twiddle factor is compressed to 0.03% of the original storage space. An area-efficient twiddle factor generator (TFG) was implemented for the common Radix-16 NTT architecture in fully homomorphic encryption. The resource consumption was reduced by 22%, and the TPG was increased by approximately one order of magnitude, effectively reducing the negative impact brought by the storage and transmission of twiddle factors.