SmallWood: Hash-Based Zero-Knowledge Arguments for Relatively Small Instances

"Preview Talk" (by Team SmallWood) @ MPTS 2026, in reply to the NIST Threshold Call

Abstract. This talk is related to the SmallWood previous submission to the MIST MPTC call. SmallWood is a hash-based zero-knowledge argument of knowledge, designed for efficiently proving statements of small to medium size. While existing hash-based arguments such as STARK or Brakedown achieve excellent asymptotic performance for very large instances, and protocols such as VOLE-in-the-Head excel for tiny instances, SmallWood bridges the gap between these extremes. It efficiently handles proofs related to moderate-size statements, such as demonstrating knowledge of a private key, a digital signature, or a hash preimage. Built entirely upon hash-based primitives, SmallWood provides post-quantum security, as it relies only on assumptions believed to resist quantum attacks. Although its precise application domain is still under exploration, SmallWood already shows promising integration potential within lattice-based cryptosystems and arithmetization-oriented hash constructions, making it a compelling candidate for future threshold cryptographic frameworks. SmallWood was first introduced in a preprint released in early 2025, accompanied by preliminary proof-of-concept implementations. This talk will provide an overview of the SmallWood construction, which follows the widely used approach of composing a Polynomial Commitment Scheme (PCS) with a Polynomial Interactive Oracle Proof (PIOP). It will also showcase preliminary results across several applications, including arithmetic circuits, lattice-based statements, and the design of SNARK-friendly post-quantum signatures.

Joint work: Thibauld Feneuil, Matthieu Rivain.

[Slides] Suggested readings:

• Preview Writeup: SmallWood: Hash-Based Zero-Knowledge Arguments for Relatively Small Instances
• SmallWood: Hash-Based Polynomial Commitments and Zero-Knowledge Arguments for Relatively Small Instances (ia.cr/2025/1085)