Paper 2026/952 Original: eprint.iacr.org/2026/952 ↗

Formalizing PQC Signature Transition: Case of PoW Blockchain Against On-Spend Attack

Abstract

It is getting widely recognized that quantum computers pose a fundamental threat to blockchain security. The transaction signature transition to Post-quantum cryptography (PQC) is therefore an urgent challenge. However, it remains unclear how much quantum computing power would be sufficient to compromise blockchain security and, consequently, by when the transition should be completed. To address these questions theoretically, we first formalize the signature transition process and the quantum adversary based on the well-known Bitcoin backbone protocol framework. We then establish a threshold for the chain's tolerable quantum adversary capability. Specifically, we prove that a security property \emph{migration liveness} holds with overwhelming probability if $$ \Delta_{\mathrm{eff}} \geq \left\lceil \frac{4}{(1 - \epsilon)f} \right\rceil, \quad\text{and}\quad f \cdot \Delta_{\mathrm{eff}} = \Omega(\log^{2}\kappa) $$ where $\Delta_{\mathrm{eff}}$ is the number of rounds the quantum adversary needs to produce a forged transaction after the broadcast of a migration transaction, $f$ is the honest mining success probability, $\epsilon$ is the concentration quality of the underlying random variables, and $\kappa$ is the security parameter. We further generalize the analysis to derive a relationship between the transition process and the tolerable quantum adversary capability, providing a theoretical basis for designing secure signature transition plans.