Paper 2026/1099 Original: eprint.iacr.org/2026/1099 ↗

Lynx: Symmetric Primitive for Shorter and Faster VOLE-in-the-Head Signatures

Abstract

VOLE-in-the-Head (VOLEitH) is one of the most promising frameworks to design post-quantum digital signatures based on symmetric primitives. However, all existing symmetric primitives do not capture the specialized characteristics of the VOLEitH framework and are not VOLEitH-friendly, leaving room for improving the efficiency of VOLEitH-based signatures. In this paper, we propose a VOLEitH-friendly symmetric primitive called Lynx, which is optimal in terms of the number of required VOLE correlations that directly determines the efficiency of VOLEitH-based signature schemes. In particular, Lynx adopts a multi-branch structure featuring a new truncation function: (a)~nonlinear components are set to minimize the witness length and polynomial degree, as well as the number of finite-field multiplications; (b)~linear layers are strategically interleaved to strengthen security. The security of Lynx is rigorously validated by covering all current attacks in the presence of both classical and quantum adversaries. Built upon Lynx, we design a post-quantum signature scheme, Lynxer, in the VOLEitH framework, which is shorter and faster than all known post-quantum signature schemes from symmetric primitives. According to our experimental results, compared to the state-of-the-art symmetric-based signature schemes in the same setting, i.e., Rainier (CCS'22), AIMer (CCS'23) and FAESTv2 (Crypto'25), our signature scheme Lynxer reduces the ``public-key size + signature size'' by 25%~51%, and improves the signing (resp., verification) time up to 90.5% (resp., 89.9%).