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

Debrup Chatterjee

Paper 2025/2331

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

Debrup Chatterjee

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.

Note: This is the first public version of the manuscript; feedback is welcome.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint.
Keywords: code-based cryptography digital signatures syndrome decoding sum-check protocol post-quantum cryptography zkp
Contact author(s): debrupc3 @ gmail com
History: 2025-12-29: approved; 2025-12-28: received; See all versions
Short URL: https://ia.cr/2025/2331
License: CC BY

BibTeX

@misc{cryptoeprint:2025/2331,
      author = {Debrup Chatterjee},
      title = {{SUMSIG}: Compact Code-Based Signatures from Sum-Check Protocols},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/2331},
      year = {2025},
      url = {https://eprint.iacr.org/2025/2331}
}