Paper 2025/2331 Original: eprint.iacr.org/2025/2331 ↗

SUMSIG: Compact Code-Based Signatures from Sum-Check Protocols

Abstract

We present SumSig, a code-based digital signature scheme that leverages sum-check protocols to reduce the reliance on repetition in Fiat–Shamir-based constructions. Instead of repeating a constant-soundness $\Sigma$-protocol many times, our approach verifies algebraic consistency of the entire witness via a single sum-check over an extension field, achieving negligible soundness error without repetition. Our construction introduces three main ideas: (1) a representation of the syndrome decoding witness as a multilinear polynomial suitable for sum-check verification; (2) a degree-doubling binarity enforcement technique based on power-sum constraints $S_1 = S_2 = S_4 = w$ to ensure binary witnesses; and (3) a linearization helper polynomial that enables efficient simulation in the random oracle model. For 128-bit security, SumSig yields signatures of approximately 5–8 KB with public keys of 50–100 KB, depending on the polynomial commitment scheme. This offers a different trade-off compared to existing code-based signatures such as Wave and LESS, which achieve either very small signatures with large public keys or moderate public keys with larger signatures. The resulting scheme features deterministic signing with no aborts and admits a quasi-tight reduction to the Syndrome Decoding problem in the random oracle model.