Formally Verified Number-Theoretic Transform
Author:
Open Access
- 8 January 2026
- journal article
- Published by International Association for Cryptologic Research in IACR Communications in Cryptology
- Vol. 2 (4)
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.Keywords
This publication has 29 references indexed in Scilit:
- Incompleteness in Number-Theoretic Transforms: New Tradeoffs and Faster Lattice-Based Cryptographic Applications2025
- Formally Verifying Kyber2024
- Towards a Scalable Proof Engine: A Performant Prototype Rewriting Primitive for CoqJournal of Automated Reasoning, 2024
- Verification of Correctness and Security Properties for CRYSTALS-KYBER2024
- Efficient Multiplication of Somewhat Small Integers Using Number-Theoretic Transforms2022
- Improving Software Quality in Cryptography Standardization Projects2022
- The Lean 4 Theorem Prover and Programming Language2021
- Computer-Aided Security Proofs for the Working Cryptographer2011
- HOL Light: An Overview2009
- Certifying the Fast Fourier Transform with Coq2001