papers/ntt-transform/sections/01-introduction.tex

\section{Introduction}


The emergence of quantum computing, particularly with Google's Willow chip achieving quantum error correction below critical thresholds, has accelerated the timeline for practical quantum attacks on classical cryptographic systems. Shor's algorithm poses a direct threat to the elliptic curve cryptography (ECC) underlying all major blockchain networks, including Ethereum's secp256k1 signatures. While estimates vary, the cryptographic community consensus suggests that quantum computers capable of breaking 256-bit ECC may emerge within 10-15 years, necessitating immediate action to develop quantum-resistant alternatives.

Post-quantum cryptographic schemes, particularly lattice-based algorithms like FALCON and Dilithium, rely heavily on polynomial arithmetic over finite fields. The computational bottleneck for these algorithms is polynomial multiplication, which has $O(n^2)$ complexity using naive methods. The Number Theoretic Transform (NTT), a discrete analogue of the Fast Fourier Transform (FFT) operating on prime fields, reduces this complexity to $O(n \log n)$, making post-quantum cryptography computationally feasible.

However, implementing NTT efficiently on the Ethereum Virtual Machine presents unique challenges. The EVM's gas model, designed to prevent denial-of-service attacks, imposes strict computational limits that make naive implementations prohibitively expensive. Our initial FALCON-512 verification implementation consumed 24M gas—nearly 80\% of Ethereum's block gas limit—rendering it impractical for production use.

This paper presents our journey from this baseline to a highly optimized implementation achieving 3.6M gas consumption, an 85\% reduction that brings post-quantum signatures within practical reach for EVM chains. We detail the mathematical foundations, algorithmic optimizations, and implementation techniques that made this breakthrough possible.

\subsection{Contributions}

Our primary contributions include:
\begin{enumerate}
\item A production-ready NTT implementation for EVM achieving 85\% gas reduction compared to naive approaches
\item Comprehensive benchmarks demonstrating practical feasibility of FALCON, Dilithium, and SPHINCS+ on EVM
\item Novel Yul optimization techniques specifically tailored for modular arithmetic operations
\item An EIP proposal for standardizing NTT as a precompiled contract
\item Open-source implementations enabling immediate adoption by the Ethereum ecosystem
\end{enumerate}