Scalable Batch Verification for Post-Quantum Hash-Based Signatures Using STARKs
Rodrigo Duarte de Meneses, Marco Aurélio Amaral Henriques · 2025
This paper introduces a STARK-based batch verifier for a Merkle Signature Scheme (MSS) built from parallel Lamport-style one-time signatures and implemented in the Winterfell framework. The method compresses the validation of N signatures under a single Merkle root into a compact proof of 50-75 KiB. Verification then requires only a few dozen hash evaluations and completes in under 3.1 s for N = 64, outperforming naı̈ve per-signature checks for all N ≥ 8. Requiring no trusted setup, this approach paves the way for scalable, efficient validation of multiple post-quantum signatures.