Paper 2025/1077

Shorter VOLE-in-the-Head-based Signatures from Vector Semi-Commitment

Abstract

The VOLE-in-the-Head (VOLEitH) paradigm compiles VOLE-based zero-knowledge proofs into publicly verifiable post-quantum signature schemes. A central component of VOLEitH is a GGM-style tree used to realize a vector commitment, whose size dominates the signature. In this work, we adapt vector semi-commitment (VSC)---previously developed for MPC-in-the-Head (MPCitH) by Kim et al. (\emph{Eurocrypt 2025})---to the VOLEitH paradigm and prove its security. While prior MPCitH analyses relied on assumption-specific, fragmented security proofs, we give a \emph{unified} treatment that characterizes which abstract property the underlying tree must satisfy, and instantiate it under the random oracle, Davies--Meyer, counter (CTR), and pseudorandom generator (PRG) models. Building on this, we construct reduced VOLE-in-the-Head (rVOLEitH) and apply it to FAEST, one of the NIST additional post-quantum signature candidates, obtaining signature sizes comparable to those of FAEST v2.0, ranging from 94.9\% to 102.8\% of the corresponding FAEST v2.0 sizes, while attaining 27.7--124.2\% faster signing and 28.3--115.3\% faster verification for 128-bit parameters. Finally, we describe a forgery attack on a recently proposed VOLEitH variant of the subfield bilinear collision (SBC) signature scheme by Huth and Joux (\emph{Asiacrypt 2025}) which replaces leaf commitments with a single global commitment, demonstrating the necessity of the commitment structure retained by VSC.