Paper 2026/2880
Sum-Checking SmallWood: Smaller Hash-Based Zero-Knowledge Arguments
Abstract
Hash-based zero-knowledge (ZK) arguments are particularly attractive for their conservative post-quantum security, relying only on cryptographic hash functions. While VOLE-in-the-Head proofs, based on GGM trees, are the most compact for very small witnesses, Merkle-tree-based approaches take over for larger ones. In this regime, the recent SmallWood scheme achieves the smallest proof sizes for witness sizes ranging from $2^6$ to $2^{16}$. In this work, we present SmallWood+, an enhanced variant of SmallWood that leverages sum-check-based protocols to further reduce proof sizes. Following the paradigm of Longfellow ZK, where a hash-based ZK argument is used to wrap the verification of a sum-check-based protocol, we formalize the notion of Sum-Check Verification Constraint System (SVCS), which captures a broad class of such protocols, including GKR for layered circuits and the sum-check protocol for R1CS. We then design generic compilers transforming SVCS instances into ZK arguments from linear commitment schemes and/or multilinear polynomial commitment schemes, which we efficiently instantiate from SmallWood. Along the way, we develop tools of independent interest: hiding multilinear extensions, which make a multilinear evaluation of the committed witness safe to reveal in the small-field regime, a zero-knowledge version of the ring-switching protocol, and an improved circuit-flattening technique for GKR. Applied to (layered) arithmetic circuits, hash functions, and lattice-based statements, our constructions establish new state-of-the-art proof sizes for hash-based ZK arguments - for instance, 18 KB and 63 KB to prove 1 and 100 Keccak permutations, against 29 KB and 127 KB for the best previous schemes.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- Zero-knowledge argumentsSum-check protocolHash-based proof systemsPost-quantum cryptography
- Contact author(s)
-
thibauld feneuil @ cryptoexperts com
killian provin @ cryptoexperts com
matthieu rivain @ cryptoexperts com - History
- 2026-11-16: approved
- 2026-11-12: received
- See all versions
- Short URL
- https://ia.cr/2026/2880
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2026/2880,
author = {Thibauld Feneuil and Killian Provin and Matthieu Rivain},
title = {Sum-Checking {SmallWood}: Smaller Hash-Based Zero-Knowledge Arguments},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/2880},
year = {2026},
url = {https://eprint.iacr.org/2026/2880}
}