papers/ntt-transform/sections/02-number-theoretic-transform-background.tex

\section{Number Theoretic Transform Background}


\subsection{Mathematical Foundation}

The Number Theoretic Transform operates on the cyclotomic ring $R_q = \mathbb{Z}_q[X]/(X^n + 1)$, where $q$ is a prime satisfying $q \equiv 1 \pmod{2n}$ and $n$ is a power of 2. This structure is fundamental to lattice-based cryptography as it provides efficient polynomial arithmetic while maintaining security properties.

\begin{definition}[NTT]
Let $a = (a_0, a_1, \ldots, a_{n-1}) \in \mathbb{Z}_q^n$ be the coefficient vector of a polynomial $a(X) = \sum_{i=0}^{n-1} a_i X^i$. The NTT of $a$ is defined as:
\[
\text{NTT}(a)[k] = \sum_{i=0}^{n-1} a[i] \cdot \omega^{ik} \bmod q
\]
where $\omega$ is a primitive $n$-th root of unity modulo $q$, satisfying $\omega^n \equiv 1 \pmod{q}$ and $\omega^k \not\equiv 1 \pmod{q}$ for $0 < k < n$.
\end{definition}

\subsection{Negative Wrapped Convolution}

For cryptographic applications, we use the negative wrapped convolution variant, which operates on the ring $\mathbb{Z}_q[X]/(X^n + 1)$. This requires a $2n$-th root of unity $\psi$ where $\psi^n = \omega$. The transformation includes pre-multiplication by powers of $\psi$:

\begin{align}
\tilde{a}[i] &= a[i] \cdot \psi^i \bmod q \\
\text{NTT}_{\text{NWC}}(a) &= \text{NTT}(\tilde{a})
\end{align}

\subsection{Inverse NTT}

The inverse transformation recovers the original polynomial:

\begin{definition}[Inverse NTT]
\[
\text{INTT}(A)[i] = n^{-1} \cdot \sum_{k=0}^{n-1} A[k] \cdot \omega^{-ik} \bmod q
\]
where $n^{-1}$ is the modular inverse of $n$ modulo $q$.
\end{definition}

\subsection{Prime Field Selection}

The choice of prime $q$ critically impacts performance. We require:
\begin{enumerate}
\item $q = k \cdot 2^m + 1$ for small $k$ (enables efficient modular reduction)
\item $q$ fits within EVM's 256-bit word size
\item $q$ supports the required security level
\end{enumerate}

For our implementations:
\begin{itemize}
\item FALCON: $q = 12289 = 3 \cdot 2^{12} + 1$ (14-bit prime)
\item Dilithium: $q = 8380417 = 2^{23} - 2^{13} + 1$ (23-bit prime)
\item BabyBear (STARKs): $q = 2^{31} - 2^{27} + 1$ (31-bit prime)
\end{itemize}