Efficient error detection for NTT using algebraic invariants (AIC) checking for PQC and FHE on FPGA

Polynomial multiplication is the most computationally demanding arithmetic operation used in many Post-Quantum Cryptographic (PQC) and Fully Homomorphic Encryption (FHE) algorithms. The Number Theoretic Transform (NTT) is the most efficient technique for performing polynomial multiplication in these schemes. However, at the implementation level, NTT designs used in PQC and FHE are vulnerable to information leakage due to intentional fault injection attacks. Preventing both intentional and unintentional faults has become a major concern for next-generation secure processors. In this regard, we introduce Full and Partial Recomputation–based Algebraic Invariant Checking (FR-AIC and PR-AIC) schemes to robustly safeguard the arithmetic operations of the NTT processing element (PE). The FR-AIC achieves a high fault detection rate, and the lightweight PR-AIC offers reduced hardware overhead at the cost of a slightly lower detection capability. The proposed architecture is scalable across different NTT variants, supporting arbitrary polynomial sizes (n), the number of polynomial coefficients) and data widths (log q), thereby making it suitable for a wide range of PQC and FHE applications. Furthermore, the design is fully compatible with multi-PE parallel architectures, enabling efficient acceleration to meet high-throughput NTT performance requirements. Extensive simulations and fault-injection emulation of multiple NTT variants implemented on an Artix-7 FPGA for PQC and FHE applications show that the proposed fault detection mechanism efficiently detects nearly 100% of faults without introducing any latency overhead. The area and energy overheads of our schemes are tolerable for practical implementations of NTT.