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.3 KiB
TeX
77 lines
3.3 KiB
TeX
\section{Shor's Algorithm: Impact on Blockchain Primitives}
|
|
|
|
\label{sec:shor}
|
|
|
|
\subsection{Algorithm Overview}
|
|
|
|
Shor's algorithm~\cite{shor1997} finds the order of an element in a finite group
|
|
using quantum phase estimation. For an element $g$ of order $r$ in a group
|
|
$\mathbb{G}$, Shor's algorithm finds $r$ in $O((\log |\mathbb{G}|)^2 \cdot \log\log |\mathbb{G}|)$
|
|
quantum gates, with $O(\log |\mathbb{G}|)$ qubits. Given the order, the discrete
|
|
logarithm follows by standard reductions.
|
|
|
|
\subsection{ECDSA (secp256k1)}
|
|
|
|
ECDSA security rests on the difficulty of computing $k$ from $kG$ where $G$ is the
|
|
generator of a 256-bit elliptic curve group. Shor's algorithm solves this with
|
|
approximately $2{,}330$ logical qubits and $1.26 \times 10^{11}$ T-gates for
|
|
secp256k1~\cite{roetteler2017quantum}. With a $1\,\mu$s T-gate time and a
|
|
surface code implementing error correction:
|
|
|
|
\begin{table}[ht]
|
|
\centering
|
|
\caption{Quantum resource estimates for breaking elliptic curve DLP.}
|
|
\label{tab:ecdsa-resources}
|
|
\begin{tabular}{lrrr}
|
|
\toprule
|
|
\textbf{Curve} & \textbf{Logical Qubits} & \textbf{T-gates} & \textbf{Est. Time} \\
|
|
\midrule
|
|
secp256k1 (256-bit) & 2{,}330 & $1.26 \times 10^{11}$ & 8 hours \\
|
|
Ed25519 (255-bit) & 2{,}310 & $1.24 \times 10^{11}$ & 8 hours \\
|
|
P-384 (384-bit) & 3{,}484 & $4.16 \times 10^{11}$ & 26 hours \\
|
|
\bottomrule
|
|
\end{tabular}
|
|
\vspace{0.3em}
|
|
\footnotesize{Resource estimates from Roetteler et al.~\cite{roetteler2017quantum},
|
|
assuming surface code with code distance 27 and $1\,\mu$s cycle time.}
|
|
\end{table}
|
|
|
|
The critical observation: once a quantum computer exists with sufficient qubits, key
|
|
recovery is measured in \emph{hours}, not years. There is no gradual degradation.
|
|
|
|
\subsection{BLS12-381}
|
|
|
|
BLS signatures operate on the pairing-friendly curve BLS12-381, where security rests
|
|
on the co-CDH assumption in groups $\mathbb{G}_1$ (381-bit) and $\mathbb{G}_2$
|
|
(762-bit). Shor's algorithm applies to both groups. Breaking BLS12-381 requires
|
|
approximately $3{,}800$ logical qubits---more than secp256k1 due to the larger
|
|
field, but the same order of magnitude.
|
|
|
|
BLS is more dangerous to break than ECDSA in the blockchain context because:
|
|
\begin{itemize}[leftmargin=2em]
|
|
\item Validator BLS keys are \emph{static}: they persist for the validator's
|
|
entire lifetime, often years.
|
|
\item BLS aggregate signatures compress $n$ validator votes into 48 bytes. If BLS
|
|
is broken, an attacker can forge consensus certificates for any historical or
|
|
future block.
|
|
\item A forged BLS certificate can rewrite chain history or create conflicting
|
|
finalized chains---a safety violation, not merely a liveness issue.
|
|
\end{itemize}
|
|
|
|
\subsection{RSA}
|
|
|
|
While RSA is not commonly used in blockchain consensus, it appears in:
|
|
\begin{itemize}[leftmargin=2em]
|
|
\item TLS certificates for RPC endpoints
|
|
\item Verifiable delay functions (VDFs) based on RSA groups
|
|
\item Some oracle attestation schemes
|
|
\end{itemize}
|
|
|
|
Shor's algorithm factors RSA-2048 with approximately $4{,}098$ logical qubits.
|
|
RSA-3072 requires approximately $6{,}146$ logical qubits. Both are within the
|
|
projected capability of CRQCs by 2035.
|
|
|
|
%% ========================================================================
|
|
%% 3. GROVER'S ALGORITHM: HASH FUNCTION IMPACT
|
|
%% ========================================================================
|