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. ( Eurocrypt 2025 )---to the VOLEitH paradigm and prove its security. While prior MPCitH analyses relied on assumption-specific, fragmented security proofs, we give a 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 ( Asiacrypt 2025 ) which replaces leaf commitments with a single global commitment, demonstrating the necessity of the commitment structure retained by VSC.
We present a new method for transforming zero-knowledge protocols in the designated verifier setting into public-coin protocols, which can be made non-interactive and publicly verifiable. Our transformation applies to a large class of ZK protocols based on oblivious transfer. In particular, we show that it can be applied to recent, fast protocols based on vector oblivious linear evaluation (VOLE), with a technique we call VOLE-in-the-head, upgrading these protocols to support public verifiability. Our resulting ZK protocols have linear proof size, and are simpler, smaller and faster than related approaches based on MPC-in-the-head. To build VOLE-in-the-head while supporting both binary circuits and large finite fields, we develop several new technical tools. One of these is a new proof of security for the SoftSpokenOT protocol (Crypto 2022), which generalizes it to produce certain types of VOLE correlations over large fields. Secondly, we present a new ZK protocol that is tailored to take advantage of this form of VOLE, which leads to a publicly verifiable VOLE-in-the-head protocol with only 2x more communication than the best, designated-verifier VOLE-based protocols. We analyze the soundness of our approach when made non-interactive using the Fiat-Shamir transform, using round-by-round soundness. As an application of the resulting NIZK, we present
FAEST , a post-quantum signature scheme based on AES. FAEST is the first AES-based signature scheme to be smaller than SPHINCS+, with signature sizes between 5.6 and 6.6kB at the 128-bit security level. Compared with the smallest version of SPHINCS+ (7.9kB), FAEST verification is slower, but the signing times are between 8x and 40x faster.