Paper 2026/1029

Towards a Unified Memory-Less Framework for TCitH

Abstract

The current on-ramp NIST Competition for Additional Post-Quantum Digital Signature Schemes features two MPCitH variants: TCitH and VOLEitH. While VOLEitH yields shorter signatures and more stack memory, making it less suitable for constrained devices. In this work, we demonstrate that TCitH-based schemes are viable on embedded systems, such as Cortex-M4 devices. We present a simple, unified Zero-Knowledge Proof (ZKP) framework covering all TCitH-based submissions to the NIST competition. Our implementation achieves up to 99% reduction in stack usage over a baseline, with minimal code size overhead and negligible performance overhead. The framework is designed for extensibility: adding new schemes requires only implementing the mathematics of the underlying problem and the polynomial proof procedures. We further contribute a novel constant-time, bitsliced implementation of Rijndael-256 for embedded architectures, targeting the GGM tree Expand, PRG, and Commit functions central to TCitH-based schemes. This is an independent contribution of broader relevance, given NIST's ongoing standardization of Rijndael-256 and its use across MPCitH-based schemes. We believe that such a framework and implementation could help new developers and cryptographers when proposing new TCitH-based schemes.