Paper 2026/1508

ZKPoSP: Post-Quantum Zero-Knowledge Proofs for Hierarchical Deterministic Wallets

Abstract

In the blockchain setting, where key derivation standards such as BIP32, BIP44, and SLIP-10 are the dominant infrastructure for wallet management, a quantum computer running Shor's algorithm can recover any elliptic-curve private key from the corresponding public key, threatening every wallet in production today. Migrating to post-quantum signature schemes requires changing the public key format and forcing address migration across all participating networks. We present an orthogonal approach: keep the existing address format unchanged and replace the classical signing step with a NIZK proof of knowledge of the seed underlying the address (or of the private data of a hardened ancestor), where no step of the security argument relies on the discrete logarithm problem. We prove security against quantum adversaries in the quantum random oracle model, under an explicit assumption on the zero-knowledge and simulation extractability of the NIZK. We build on the observation of Baldimtsi et al.\ that EdDSA's deterministic seed-to-key mapping makes the seed a valid zero-knowledge witness for the public key, and extend their result to hierarchical deterministic wallets. Our main contribution is ZKPoSP (Zero-Knowledge Proof of Seed Provenance), a signature scheme that splits the proof into a derivation proof generated once per key pair and a signing proof generated once per message, so that the per-message proving cost does not depend on the derivation depth. We also introduce QBIP32, a key derivation scheme based on a keyed function HASH768 (instantiated with KMAC256) that produces the signing scalar, an explicit witness, and the chain code in a single call at hardened steps, for any elliptic curve group of prime order. As last contributioun we notice that after Q-day, once networks reject all non-post-quantum signatures, the signing scalars can be moved to the public statement reducing derivation proving time.