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.
47 lines
2.1 KiB
TeX
47 lines
2.1 KiB
TeX
\section{Grover's Algorithm: Hash Function Impact}
|
|
|
|
\label{sec:grover}
|
|
|
|
Grover's algorithm~\cite{grover1996} provides a quadratic speedup for unstructured
|
|
search: finding a preimage of an $n$-bit hash requires $O(2^{n/2})$ quantum
|
|
evaluations instead of $O(2^n)$ classical evaluations.
|
|
|
|
\begin{table}[ht]
|
|
\centering
|
|
\caption{Impact of Grover's algorithm on hash functions used in blockchain.}
|
|
\label{tab:grover-impact}
|
|
\begin{tabular}{lrrr}
|
|
\toprule
|
|
\textbf{Hash} & \textbf{Classical Security} & \textbf{Quantum Security} & \textbf{Status} \\
|
|
\midrule
|
|
SHA-256 & $2^{256}$ (preimage) & $2^{128}$ & Safe \\
|
|
SHA-256 & $2^{128}$ (collision) & $2^{85}$ & Marginal \\
|
|
Keccak-256 & $2^{256}$ (preimage) & $2^{128}$ & Safe \\
|
|
Keccak-256 & $2^{128}$ (collision) & $2^{85}$ & Marginal \\
|
|
BLAKE2b-256 & $2^{256}$ (preimage) & $2^{128}$ & Safe \\
|
|
Poseidon & $2^{128}$ (algebraic) & $2^{85}$ & Review needed \\
|
|
\bottomrule
|
|
\end{tabular}
|
|
\end{table}
|
|
|
|
The collision resistance reduction to $2^{85}$ is concerning but not immediately
|
|
critical: $2^{85}$ quantum hash evaluations still requires substantial quantum
|
|
resources. However, Merkle tree constructions that rely on collision resistance
|
|
(state tries, transaction trees) have reduced security margins. For chains using
|
|
128-bit collision resistance as a security parameter, upgrading to 256-bit output
|
|
hashes (already standard in SHA-256 and Keccak-256) provides adequate quantum margins.
|
|
|
|
\subsection{Impact on Proof-of-Work}
|
|
|
|
For proof-of-work chains, Grover's algorithm provides a quadratic mining speedup. A
|
|
quantum miner with $2^{40}$ quantum evaluations per second would match a classical
|
|
miner with $2^{80}$ hashes per second. This is a competitive advantage, not a
|
|
security break: difficulty adjustment compensates. However, a quantum miner could
|
|
out-compete all classical miners combined if the quantum hardware gap is sufficiently
|
|
large, enabling 51\% attacks. Proof-of-stake chains (including Lux) are not affected
|
|
by this vector.
|
|
|
|
%% ========================================================================
|
|
%% 4. BLOCKCHAIN-SPECIFIC ATTACK VECTORS
|
|
%% ========================================================================
|