papers/lux-ethfalcon-post-quantum/sections/02-falcon-background.tex

\section{FALCON Background}


\subsection{Lattice-Based Cryptography Foundations}

FALCON belongs to the family of lattice-based cryptographic schemes, which base security on the hardness of problems in high-dimensional lattices. Specifically, FALCON's security reduces to the Short Integer Solution (SIS) problem over NTRU lattices \cite{prest2017sharper}.

\textbf{NTRU Lattice:} Given a polynomial ring $\mathcal{R}_q = \mathbb{Z}_q[x]/(x^n + 1)$ where $n = 512$ and $q = 12289$, an NTRU lattice is defined by a polynomial $h \in \mathcal{R}_q$ such that:
\begin{equation}
h = g \cdot f^{-1} \mod q
\end{equation}
where $f, g$ are secret polynomials with small coefficients. The public key is $h$, while $(f, g)$ form the secret key.

\textbf{Short Vector Problem:} Given $h$, find short polynomials $(s_1, s_2)$ such that:
\begin{equation}
s_1 + s_2 \cdot h \equiv c \mod q
\end{equation}
for a target $c = \text{HashToPoint}(m)$. This is the core of FALCON verification.

\subsection{FALCON Signature Scheme}

FALCON (Fast-Fourier Lattice-based Compact Signatures over NTRU) was proposed by Fouque et al. \cite{falcon2020} and selected by NIST in 2022. The scheme operates as follows:

\textbf{Key Generation:}
\begin{enumerate}
    \item Generate NTRU polynomials $f, g \in \mathcal{R}_q$ with small coefficients
    \item Compute $h = g \cdot f^{-1} \mod q$
    \item Compute Gram-Schmidt orthogonalization of basis $(f, g)$ to obtain secret tree $T$
    \item \textbf{Public key:} $pk = h$
    \item \textbf{Secret key:} $sk = T$ (FFT tree for fast sampling)
\end{enumerate}

\textbf{Signing:} Given message $m$ and secret key $sk = T$:
\begin{enumerate}
    \item Sample random salt $r \in \{0,1\}^{320}$
    \item Compute $c = \text{HashToPoint}(r \| m)$ using SHAKE256
    \item Sample short signature $(s_1, s_2)$ from lattice using FFT sampling with tree $T$ such that:
    \begin{equation}
    s_1 + s_2 \cdot h \equiv c \mod q
    \end{equation}
    \item Compress $s_2$ using custom encoding (Algorithm 17 in \cite{falcon2020})
    \item \textbf{Output:} $\sigma = (r, \text{compress}(s_2))$ (666 bytes for $n=512$)
\end{enumerate}

\textbf{Verification:} Given message $m$, signature $\sigma = (r, s_2')$, public key $pk = h$:
\begin{enumerate}
    \item Decompress $s_2'$ to obtain $s_2$
    \item Compute $c = \text{HashToPoint}(r \| m)$
    \item Compute $s_1 = c - s_2 \cdot h \mod q$
    \item Compute squared norm: $\|s_1\|^2 + \|s_2\|^2$
    \item \textbf{Accept} if $\|s_1\|^2 + \|s_2\|^2 \leq B$ where $B = 34034726$ (FALCON-512 bound)
    \item \textbf{Reject} otherwise
\end{enumerate}

\subsection{Number Theoretic Transform (NTT)}

The polynomial multiplication $s_2 \cdot h$ in verification is the computational bottleneck. FALCON uses the Number Theoretic Transform (NTT), a discrete Fourier transform over finite fields, to accelerate this operation from $O(n^2)$ to $O(n \log n)$.

\textbf{NTT Definition:} For polynomial $p = \sum_{i=0}^{n-1} p_i x^i$, its NTT is:
\begin{equation}
\hat{p}_j = \sum_{i=0}^{n-1} p_i \cdot \omega^{ij} \mod q
\end{equation}
where $\omega$ is a primitive $2n$-th root of unity in $\mathbb{Z}_q$.

\textbf{Convolution Property:}
\begin{equation}
\text{NTT}(p \cdot h) = \text{NTT}(p) \odot \text{NTT}(h)
\end{equation}
where $\odot$ denotes pointwise multiplication. This reduces $n^2$ multiplications to $n$ after transformation.

\textbf{Cost Analysis:}
\begin{itemize}
    \item Forward NTT: $n \log n$ multiplications and additions
    \item Inverse NTT: $n \log n$ multiplications and additions
    \item Standard FALCON verification: 2 forward NTTs + 1 inverse NTT
\end{itemize}

\subsection{HashToPoint Function}

FALCON requires mapping messages to lattice points via HashToPoint. The NIST specification uses SHAKE256 as an extendable output function (XOF):

\textbf{Algorithm:}
\begin{algorithmic}[1]
\STATE $\text{xof} \gets \text{SHAKE256}(r \| m)$
\FOR{$i = 0$ to $n-1$}
    \REPEAT
        \STATE $x \gets \text{xof.read}(16 \text{ bits})$
    \UNTIL{$x < 61445$}
    \STATE $c_i \gets x \mod q$
\ENDFOR
\RETURN $c = (c_0, \ldots, c_{n-1})$
\end{algorithmic}

This rejection sampling ensures uniform distribution modulo $q = 12289$. The average rejection rate is $\approx 6\%$ since $61445/65536 \approx 0.94$.