Paper 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%).

Note: The Lynxer signature scheme has been submitted to Next-generation Commercial Cryptographic Algorithms Program (NGCC) (https://www.niccs.org.cn/niccs/), which is a Post-Quantum Cryptography (PQC) competition by China. Compared to the NGCC submission (https://www.niccs.org.cn/niccs/Round1Additional/pc/list.html), the current ePrint version shares the same one-wayness function Lynx and its cryptanalysis, but just follows the construction of batch all-but-one vector commitments (BAVCs) in the newest version of FAEST, and does not adopt the optimizations for BAVCs in the NGCC submission. We note that the detailed security proof in the NGCC submission can be straightforwardly applied to that of the Lynxer algorithm of the ePrint version. Recently, the team of the Center for Cryptology Study at Tsinghua University found a forgery attack on the original Lynxer scheme, and contacts us via an email-based private communication. This attack exploits the fact that the QuickSilver layer in Lynxer does not prove the full Lynx computation but rather a low-degree polynomial relation that coincides with it only on non-anomalous inputs. By targeting anomalous zero points (e.g., k + c_3 = 0, v_1 = 0), the attacker can construct witnesses that satisfy the constraints yet do not correspond to any genuine preimage of Lynx, thereby forging signatures. Besides, Martin Feussner independently discovered the same forgery attack and posted a comment at https://list.niccs.org.cn/archives/list/[email protected]. As Martin Feussner noted, this flaw is specific to certain Lynxer parameters and is not an attack on QuickSilver in general, nor on VOLE-in-the-Head, nor on the intended one-wayness of the Lynx primitive. In the current ePrint version, we have already completed the targeted fix for the Lynxer scheme: the original S-boxes have been replaced with the inverse function across all security levels of Lynx. This revision makes the verification relation accurate and sound over the full key space, which completely invalidates the aforementioned forgery attack. We verify the security of the fixed Lynxer scheme by both ourselves and GPT‑6 Astra. The improved Lynx algorithm can be directly applied in our NGCC submission, which makes the Lynxer scheme in the NGCC submission be secure.