papers/lux-ethfalcon-post-quantum/sections/01-introduction.tex

\section{Introduction}


\subsection{The Quantum Threat to Blockchains}

Blockchain networks secure over \$2 trillion in digital assets through cryptographic signatures, predominantly ECDSA (Elliptic Curve Digital Signature Algorithm) on secp256k1 curve. Shor's algorithm \cite{shor1997polynomial} demonstrates that sufficiently large quantum computers can break ECDSA in polynomial time, threatening the foundation of all major blockchains including Bitcoin, Ethereum, and their derivatives. While practical quantum computers remain years away, the ``harvest now, decrypt later'' threat model necessitates immediate post-quantum cryptography (PQC) deployment \cite{mosca2018cybersecurity}.

NIST's Post-Quantum Cryptography Standardization project selected FALCON \cite{falcon2020} as a primary digital signature standard in Round 3 (2022). FALCON offers:
\begin{itemize}
    \item \textbf{Compact signatures}: 666 bytes for FALCON-512 (128-bit quantum security)
    \item \textbf{Fast signing}: $<$ 1ms on modern CPUs
    \item \textbf{Strong security}: Based on hardness of NTRU lattice problems
    \item \textbf{Mathematical elegance}: Uses Fast Fourier Transforms over polynomial rings
\end{itemize}

However, FALCON's reliance on SHAKE (SHA-3 XOF), recursive NTT (Number Theoretic Transform), and floating-point arithmetic creates severe inefficiencies when deployed on Ethereum's deterministic, 256-bit integer-based virtual machine.

\subsection{Ethereum's Gas Cost Challenge}

The Ethereum Virtual Machine (EVM) operates on a pay-per-computation model where every operation consumes ``gas''. A typical ECDSA signature verification (ecrecover precompile) costs 3,000 gas. Early FALCON implementations on EVM exceeded 24 million gas \cite{tetration2023falcon}, making them economically infeasible (current block gas limit: 30 million).

This paper addresses three fundamental incompatibilities:
\begin{enumerate}
    \item \textbf{SHAKE vs. Keccak}: FALCON uses SHAKE256 (SHA-3 XOF) extensively, while EVM provides native Keccak256 at 30 gas per call. Implementing SHAKE in Solidity costs $>$500,000 gas per invocation.
    \item \textbf{Recursive vs. Iterative NTT}: FALCON's reference NTT implementation uses recursion, which Solidity handles inefficiently. Custom iterative implementations reduce costs by 3-5x.
    \item \textbf{Public Key Recovery}: ECDSA's ecrecover allows deriving addresses from signatures without storing public keys. FALCON's standard mode requires explicit public key storage, complicating Account Abstraction integration.
\end{enumerate}

\subsection{Contributions}

This work presents ETHFALCON, a family of three FALCON variants optimized for EVM deployment:

\textbf{1. FALCON-SOLIDITY} (EVM-friendly base variant)
\begin{itemize}
    \item Replaces SHAKE with Keccak-CTR XOF construction
    \item Maintains 128-bit quantum security
    \item Reduces gas cost to 7M (70\% improvement over naive port)
    \item Proven compatible with NIST FALCON-512 test vectors
\end{itemize}

\textbf{2. EPERVIER} (Public key recovery variant)
\begin{itemize}
    \item First FALCON variant with ecrecover-compatible public key recovery
    \item Eliminates inverse NTT through NTT-domain public key representation
    \item Achieves 1.9M gas verification (comparable to 2 NTT operations)
    \item Enables quantum-resistant Account Abstraction (EIP-7702, EIP-4337)
\end{itemize}

\textbf{3. Architectural Optimizations}
\begin{itemize}
    \item Custom iterative NTT replacing recursive implementation (-50\% cost)
    \item 16-coefficient packing per 256-bit word (optimal for EVM)
    \item Precomputed NTT-domain public keys (eliminates redundant transformations)
    \item Yul assembly implementations with extcodecopy optimization \cite{grassi2023efficient}
\end{itemize}

Our implementations are production-ready:
\begin{itemize}
    \item Deployed on Optimism Sepolia testnet (verified contracts)
    \item Comprehensive test suite against NIST KAT vectors
    \item Python reference implementation for cross-validation
    \item Full EIP-7702 delegation example
\end{itemize}

The remainder of this paper is structured as follows: Section 2 provides FALCON background; Section 3 details EVM optimization strategies; Section 4 presents EPERVIER's public key recovery innovation; Section 5 benchmarks performance; Section 6 analyzes security; Section 7 discusses Ethereum integration; Section 8 compares with alternative PQC schemes; Section 9 concludes.