Formally Verified Number-Theoretic Transform

Abstract

In recent years, the number-theoretic transform (NTT) has become increasingly common in cryptography, in part due to multiple lattice-based cryptographic schemes being selected for standardization during the NIST PQC competition. Indeed, polynomial multiplications are one of the most computing intensive operations in these schemes and the NTT is crucial in decreasing the performance cost. The NTT also appears in other areas such as fully homomorphic encryption (FHE) and zero-knowledge proofs (ZKP) which are increasingly used in privacy-preserving applications. In this paper, we show how to formally specify the NTT in the Rocq proof assistant, and how we used this specification to automatically derive formally verified implementations of both complete and incomplete NTTs for multiple cryptographic schemes.