mirror of
https://github.com/lux-apps/papers.git
synced 2026-10-30 18:15:21 +00:00
zeekay
9504b4c3ef
Sweep across the non-Tier-1 paper catalogue (Tier-1 owned by parallel
agent and excluded). All 113 processed papers already had luxcover
wired up; this commit fixes 14 build breakers and produces fresh
PDFs across the catalogue.
Fixes:
- lux-blockchain-scaling-laws: em-dash inside lstlisting -> --
- lux-corona-pq: stale \input pointing at 03-the-corona-scheme renamed
to 03-the-corona-scheme (file already renamed on disk)
- lux-lattice-cryptography-primer: same Corona->Corona rename
- lux-formal-verification-lean4: Lean source uses unicode (×, ∀, ∃, ∈,
∧, ∨, ∩, ≠, ⟨, ⟩, ·, ¬) inside lstlistings. Added a literate map
so listings render the math glyphs without UTF-8 fault.
- lux-id-did-specification: ✓/✗ in tabular replaced with \ding{51}
/ \ding{55} (pifont). Added pifont package.
- lux-ntt-simd-implementation: middle-dot in Go assembly listings;
added literate {·}{\textperiodcentered}.
- lux-ntt-transform: μ, ×, –, — in regular text (no T1 fontenc).
Replaced with $\mu$/$\times$/--/--- via unicode->latex sweep.
- lux-perpetuals-derivatives, lux-quantum-consensus,
lux-quasar-consensus, lux-tee-computing-mesh: same unicode->latex
sweep across body text. Also fixed broken math segment
`$L_{avg} = 10$\times$$` -> `$L_{avg} = 10\times$`.
- lux-zchain: emoji glyphs in roadmap table replaced with
parenthetical text.
- lux-triple-proof-consensus: dropped duplicate \usepackage{geometry}
that clashed with luxcover (geometry option clash).
- pq: defined missing \Rq macro.
PDFs rebuilt for the full Tier-2/3 set.
Excluded (Tier-1, parallel agent): lp-073-pulsar, lp-stricte2epq,
dag-evm-formal, lp-010-quasar-stm-{3,4}, lp-020-quasar-consensus,
lux-institutional-custody, lux-nist-mptc-submission, pqsafe-il5,
pq-rns, plus shared/ and lps/.
23 lines
2.5 KiB
TeX
23 lines
2.5 KiB
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 ML-DSA, 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, ML-DSA, and SLH-DSA (FIPS 205, formerly 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}
|
|
|