papers/lux-evm-precompiles/sections/06-post-quantum-signature-precompiles.tex

\section{Post-Quantum Signature Precompiles}
\label{sec:pq}

\subsection{Motivation}

NIST's post-quantum cryptography standardization \cite{nistpqc2024} has finalized ML-DSA (FIPS 204, formerly CRYSTALS-Dilithium) (ML-DSA) and FALCON (FN-DSA) as standard lattice-based signature schemes. Lux Network provides on-chain verification precompiles for both, enabling quantum-resistant smart contract authentication ahead of the quantum threat.

\subsection{ML-DSA Verification}

\begin{definition}[Dilithium-3 Parameters]
\begin{align}
    &\text{Security level: NIST Level 3 ($\approx 192$-bit classical)} \\
    &\text{Public key size: } 1{,}952 \text{ bytes} \\
    &\text{Signature size: } 3{,}293 \text{ bytes} \\
    &\text{Ring dimension: } n = 256, \quad q = 8{,}380{,}417
\end{align}
\end{definition}

\begin{algorithm}[H]
\caption{Dilithium-3 Verification Precompile}
\label{alg:dilithium}
\begin{algorithmic}[1]
\Require Input: $\mathsf{pk}$ (1,952 B) $\|$ $\sigma$ (3,293 B) $\|$ $m$ (variable)
\State Parse $\mathsf{pk} = (\rho, t_1)$ \Comment{Seed and compressed key}
\State Parse $\sigma = (\tilde{c}, z, h)$ \Comment{Challenge, response, hint}
\State Expand $A$ from $\rho$ using SHAKE-128
\State Verify $\|z\|_\infty < \gamma_1 - \beta$
\State Compute $w_1' = Az - ct_1 \cdot 2^d$
\State Use hint $h$ to recover high bits
\State Recompute challenge $\tilde{c}' = H(\rho \| w_1' \| m)$
\If{$\tilde{c}' = \tilde{c}$ and $\|z\|$ norm check passes}
    \State \Return 0x01 (valid)
\Else
    \State \Return 0x00 (invalid)
\EndIf
\end{algorithmic}
\end{algorithm}

Gas cost: 35,000 (independent of message length for messages $< 1$ KB; add 30 gas per additional 32-byte word).

\subsection{FALCON Verification}

\begin{definition}[FALCON-512 Parameters]
\begin{align}
    &\text{Security level: NIST Level 1 ($\approx 128$-bit classical)} \\
    &\text{Public key size: } 897 \text{ bytes} \\
    &\text{Signature size: } 666 \text{ bytes (average)} \\
    &\text{Ring dimension: } n = 512, \quad q = 12{,}289
\end{align}
\end{definition}

FALCON's advantage over ML-DSA is its smaller signature size (666 vs.\ 3,293 bytes), which reduces calldata costs:

\begin{table}[H]
\centering
\caption{Post-quantum signature precompile comparison.}
\label{tab:pq_comparison}
\begin{tabular}{lrrrr}
\toprule
\textbf{Scheme} & \textbf{PK (B)} & \textbf{Sig (B)} & \textbf{Verify Gas} & \textbf{Verify Time (ms)} \\
\midrule
Dilithium-2 & 1,312 & 2,420 & 28,000 & 0.22 \\
Dilithium-3 & 1,952 & 3,293 & 35,000 & 0.30 \\
Dilithium-5 & 2,592 & 4,595 & 48,000 & 0.43 \\
FALCON-512 & 897 & 666 & 28,000 & 0.25 \\
FALCON-1024 & 1,793 & 1,280 & 42,000 & 0.38 \\
\bottomrule
\end{tabular}
\end{table}

\subsection{Calldata Cost Analysis}

On-chain verification of post-quantum signatures requires transmitting large keys and signatures as calldata:

\begin{table}[H]
\centering
\caption{Total on-chain cost including calldata (16 gas/byte non-zero).}
\label{tab:pq_total}
\begin{tabular}{lrrrr}
\toprule
\textbf{Scheme} & \textbf{Verify Gas} & \textbf{Calldata Gas} & \textbf{Total Gas} & \textbf{vs.\ ECDSA} \\
\midrule
ECDSA (secp256k1) & 3,000 & 1,088 & 4,088 & 1.0x \\
Dilithium-3 & 35,000 & 83,920 & 118,920 & 29.1x \\
FALCON-512 & 28,000 & 24,992 & 52,992 & 13.0x \\
FALCON-1024 & 42,000 & 49,168 & 91,168 & 22.3x \\
\bottomrule
\end{tabular}
\end{table}

While post-quantum verification is 13--29x more expensive than ECDSA, the absolute cost remains practical ($< \$0.10$ per verification at typical gas prices), making it feasible for high-value transactions requiring quantum resistance.

\subsection{Hybrid Authentication}

We recommend a hybrid approach where transactions are signed with both ECDSA (for backward compatibility) and a post-quantum scheme (for forward security):

\begin{definition}[Hybrid Signature]
\begin{equation}
    \sigma_{\text{hybrid}} = (\sigma_{\text{ECDSA}}, \sigma_{\text{PQ}})
\end{equation}
Verification succeeds iff both components verify. This provides security against both classical and quantum adversaries without requiring a hard fork to switch signature schemes.
\end{definition}