Paper 2026/945

SPRITZ: A Short PRISM-Based Threshold Signature via Zero-Knowledge Proof

Abstract

Threshold signatures for distributed systems require compact public keys and signatures to reduce communication overhead by avoiding packet fragmentation. However, with existing post-quantum threshold signatures, either the public key or the signature does not fit within a single unfragmented network packet. In this work, we present SPRITZ, an isogeny-based post-quantum threshold signature scheme whose public keys and signatures both fit within a single unfragmented network packet at every NIST security level. To the best of our knowledge, SPRITZ is the first post-quantum threshold signature scheme to do so with an arbitrary number of parties. While isogeny-based signatures such as SQIsign and PRISM are known for exceptionally compact public keys and signatures, their algebraic structure makes thresholdization for an arbitrary number of parties highly nontrivial. We address this challenge by introducing a novel graph-based threshold access structure tailored to the isogeny setting. For security against known attacks, we employ a non-interactive zero-knowledge (NIZK) protocol for the verification of isogeny push-forward procedures. At NIST security levels I/III/V, SPRITZ achieves public keys of 129/193/257 bytes and signatures of 223/335/447 bytes, respectively. Among the schemes submitted to the NIST MPTC (Multi-Party Threshold Cryptography) previews phase 2 whose public keys fit within a single unfragmented network packet, SPRITZ achieves the smallest signature size. We also provide a proof-of-concept implementation of SPRITZ.