Proof-Carrying Arithmetic for Quantum ECDLP: A Certificate Format for Public Reversible Blocks

Abstract

Quantum resource estimates for the elliptic-curve discrete logarithm problem (ECDLP) now shape cryptographic migration planning, blockchain security analysis, and fault-tolerant architecture design. Recent work has moved in two complementary directions: Babbush et al. give improved secp256k1 resource estimates supported by zero-knowledge attestation while withholding sensitive circuit details, whereas Luo et al. publish an explicit reversible modular-inversion construction based on the extended Euclidean algorithm, reducing the logical-qubit footprint of prime-field ECDLP and identifying gate count, depth, and architecture-aware implementation as natural optimization targets. This note proposes a third disclosure model: verifiable resource certificates for public reversible arithmetic blocks. A certificate records a circuit commitment, gate basis, resource counts, input-output specification, deterministic test generation, correctness transcript, and optional proof artifact. We specialize the framework to modular inversion blocks |x⟩|0⟩ → |x⟩|x−1 mod p⟩, for \(x\in\mathbb F_p^\times\), which are central to affine-coordinate quantum ECDLP implementations. We prove a basic soundness bound for hash-derived randomized testing and outline a prototype verifier. The goal is not a new quantum attack, but reproducible, comparable, and independently auditable quantum-ECDLP arithmetic claims.