papers/ntt-transform/sections/06-supported-post-quantum-algorithms.tex

\section{Supported Post-Quantum Algorithms}


\subsection{FALCON}

FALCON (Fast-Fourier Lattice-based Compact signatures over NTRU) provides the most compact signatures among lattice-based schemes:

\begin{itemize}
\item \textbf{Signature size}: 897 bytes (FALCON-512)
\item \textbf{Public key size}: 897 bytes
\item \textbf{Security level}: NIST Level I (128-bit)
\item \textbf{Verification gas cost}: 3.6M (optimized)
\end{itemize}

FALCON's compact signatures make it ideal for blockchain applications where storage is expensive.

\subsection{Dilithium (ML-DSA)}

Dilithium, standardized as ML-DSA (Module Lattice Digital Signature Algorithm), is NIST's primary recommendation:

\begin{itemize}
\item \textbf{Signature size}: 3,293 bytes (Dilithium-3)
\item \textbf{Public key size}: 1,952 bytes
\item \textbf{Security level}: NIST Level III (192-bit)
\item \textbf{Verification gas cost}: 4.1M (optimized)
\end{itemize}

Dilithium's simpler structure and NIST standardization make it attractive for conservative implementations.

\subsection{SPHINCS+}

SPHINCS+ offers a hash-based alternative without lattice assumptions:

\begin{itemize}
\item \textbf{Signature size}: 17,088 bytes (SPHINCS+-SHA256-192s)
\item \textbf{Public key size}: 48 bytes
\item \textbf{Security level}: NIST Level III (192-bit)
\item \textbf{Verification gas cost}: 5.2M (without NTT)
\end{itemize}

While SPHINCS+ doesn't directly use NTT, our optimization techniques for hash operations provide similar benefits.

\subsection{STARK Verifiers}

STARKs (Scalable Transparent ARguments of Knowledge) rely heavily on polynomial arithmetic:

\begin{itemize}
\item \textbf{Proof size}: Variable (typically 50-200 KB)
\item \textbf{Verification complexity}: $O(\log^2 n)$
\item \textbf{NTT application}: Reed-Solomon encoding/decoding
\item \textbf{Gas savings}: 60-70\% for polynomial operations
\end{itemize}

\subsection{Performance Comparison}

\begin{table}[h]
\centering
\caption{Post-Quantum Algorithm Performance on EVM}
\begin{tabular}{lrrrr}
\toprule
Algorithm & Sig Size & Verify Gas & Security & NTT Benefit \\
\midrule
ECDSA (current) & 65B & 3,000 & Classical & N/A \\
FALCON-512 & 897B & 3.6M & NIST-I & 85\% \\
Dilithium-2 & 2,420B & 3.8M & NIST-I & 82\% \\
Dilithium-3 & 3,293B & 4.1M & NIST-III & 81\% \\
SPHINCS+-192s & 17KB & 5.2M & NIST-III & Indirect \\
\bottomrule
\end{tabular}
\end{table}