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.
77 lines
3.1 KiB
TeX
77 lines
3.1 KiB
TeX
\section{Security Analysis}
|
|
|
|
|
|
\subsection{Quantum Security Level}
|
|
|
|
FALCON-512 targets NIST security level 1 \cite{nist2016submission}:
|
|
\begin{itemize}
|
|
\item \textbf{Classical Security:} At least as hard as AES-128 key search
|
|
\item \textbf{Quantum Security:} At least as hard as AES-128 using Grover's algorithm
|
|
\item \textbf{Equivalent:} 143-bit classical security, 128-bit quantum security
|
|
\end{itemize}
|
|
|
|
\textbf{Lattice Problem:} Security reduces to finding short vectors in NTRU lattice with:
|
|
\begin{equation}
|
|
\text{root-Hermite factor } \delta \approx 1.0044
|
|
\end{equation}
|
|
|
|
Current best quantum attacks (using sieve algorithms):
|
|
\begin{itemize}
|
|
\item Classical BKZ: $2^{128}$ operations
|
|
\item Quantum sieve: $2^{107}$ operations (Gates et al. \cite{gates2019estimating})
|
|
\item \textbf{Conclusion:} Secure against projected quantum computers (requires $>10^{32}$ gates)
|
|
\end{itemize}
|
|
|
|
\subsection{Cryptographic Modifications}
|
|
|
|
\subsubsection{Keccak-CTR Security}
|
|
|
|
\textbf{Theorem:} Under the random oracle model, Keccak-CTR provides indistinguishability from random output.
|
|
|
|
\textbf{Proof Sketch:}
|
|
\begin{enumerate}
|
|
\item Keccak256 modeled as random oracle $H: \{0,1\}^* \rightarrow \{0,1\}^{256}$
|
|
\item Each counter value $i$ produces independent block: $B_i = H(\text{state} \| i)$
|
|
\item Adversary distinguishing from random needs to find collision in $H$
|
|
\item Birthday bound: $2^{128}$ queries for collision probability 0.5
|
|
\item \textbf{Conclusion:} Security equivalent to Keccak collision resistance
|
|
\end{enumerate}
|
|
|
|
\textbf{NIST Comparison:} Similar to CTR-DRBG (SP 800-90A) but using hash function instead of block cipher. Keccak's 1600-bit state provides stronger security margins than AES-based constructions.
|
|
|
|
\subsubsection{NTT-Domain Public Keys}
|
|
|
|
\textbf{Claim:} Moving public keys to NTT domain preserves security.
|
|
|
|
\textbf{Argument:}
|
|
\begin{enumerate}
|
|
\item NTT is an isomorphism: bijective mapping between coefficient and NTT domains
|
|
\item Recovering $h$ from $\text{NTT}(h)$ is trivial (apply inverse NTT)
|
|
\item Lattice structure preserved under isomorphism
|
|
\item \textbf{Conclusion:} No security degradation
|
|
\end{enumerate}
|
|
|
|
\subsection{Known Vulnerabilities (Mitigated)}
|
|
|
|
\textbf{CVETH-2025-080201 (Critical):} Salt size not checked in Tetration v1.0, allowing forgery via modified salt length.
|
|
\begin{itemize}
|
|
\item \textbf{Fix:} Enforce $|\text{salt}| = 40$ bytes in verification
|
|
\item \textbf{Impact:} Universal forgery if exploited
|
|
\item \textbf{Status:} Patched in ZKNOX implementation
|
|
\end{itemize}
|
|
|
|
\textbf{CVETH-2025-080202 (Medium):} Signature malleability on coefficient signs (negation attack).
|
|
\begin{itemize}
|
|
\item \textbf{Fix:} Canonical encoding: require $s_{2,i} \in [0, q/2)$
|
|
\item \textbf{Impact:} Multiple valid signatures for same message
|
|
\item \textbf{Status:} Enforced in verification
|
|
\end{itemize}
|
|
|
|
\textbf{CVETH-2025-080203 (Low):} Lack of domain separation in XOF state transitions.
|
|
\begin{itemize}
|
|
\item \textbf{Fix:} Prepend counter domain tag
|
|
\item \textbf{Impact:} Theoretical state collision
|
|
\item \textbf{Status:} Under review
|
|
\end{itemize}
|
|
|