mirror of
https://github.com/lux-apps/papers.git
synced 2026-10-30 18:15:21 +00:00
zeekay
abf99d05fc
Restructured from flat .tex/.pdf files into per-paper subdirectories. Added Antje Worring as co-author on all papers. Synced PDFs to pdfs/ for download site.
16 lines
799 B
TeX
16 lines
799 B
TeX
\section{Why NTT Matters}
|
|
|
|
|
|
Every lattice-based cryptographic operation involves polynomial multiplication in the ring
|
|
$R_q = \mathbb{Z}_q[X]/(X^n + 1)$. ML-KEM key generation performs $k^2$ polynomial
|
|
multiplications ($k = 2, 3,$ or $4$). ML-DSA signing performs roughly $k(\ell + k)$
|
|
multiplications per attempt, with multiple attempts due to rejection sampling. FHE
|
|
operations perform thousands of polynomial multiplications per bootstrapping.
|
|
|
|
Naive polynomial multiplication is $O(n^2)$: for $n = 256$, that is 65,536 multiply-and-add
|
|
operations, each with modular reduction. The NTT reduces this to $O(n \log n)$: 2,048
|
|
butterfly operations. For $n = 1024$ (FHE), the ratio is $1{,}048{,}576$ vs.\ $10{,}240$---a
|
|
factor of 100.
|
|
|
|
%% ============================================================
|