Paper 2026/1526

On the Suitability of Syndrome Decoding for Proof-of-Work under Quantum Adversaries: Design and Analysis

Abstract

Proof-of-work (PoW) remains a fundamental mechanism for achieving decentralized consensus, most commonly instantiated using cryptographic hash functions. In such constructions, mining takes the form of an unstructured search problem over a large input space, where miners repeatedly evaluate candidate solutions until a valid one is found. While this design has proven effective in practice, it admits a quadratic quantum speedup via Grover’s algorithm, raising concerns about the long-term security of hash-based mining. Motivated by this limitation, we investigate the use of code-based cryptographic problems as an al- ternative foundation for proof-of-work. In particular, we focus on the syndrome decoding problem and examine its classical and quantum com- plexity based on current state-of-the-art information-set decoding (ISD) algorithms and their quantum variants, comparing the resulting quantum advantage with that of hash-based and lattice-based constructions. Building on this analysis, we propose a proof-of-work construction based on the Syndrome Decoding Problem (SDP) with a structured profile constraint, which enables controlled variation of solution density and difficulty. Under the standard random-instance heuristic, we derive ex- pressions for the expected number of solutions and the probability of successful mining, providing a principled basis for parameter selection.