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

Lin Jiao; Hongsen Yang; Hongrui Cui; Yituo He; Yonglin Hao; Xiaojie Guo; Qunxiong Zheng; Jiang Zhang; Yu Yu; Kang Yang

Paper 2026/1099

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

Lin Jiao, State Key Laboratory of Cryptology, Beijing, China

Hongsen Yang, Information Engineering University, Zhengzhou, China

Hongrui Cui, Shanghai Jiao Tong University, Shanghai, China

Yituo He, Shanghai Jiao Tong University, Shanghai, China

Yonglin Hao, State Key Laboratory of Cryptology, Beijing, China

Xiaojie Guo, Shanghai Qi Zhi Institute, Shanghai, China

Qunxiong Zheng, Information Engineering University, Zhengzhou, China

Jiang Zhang, State Key Laboratory of Cryptology, Beijing, China

Yu Yu, Shanghai Jiao Tong University, Shanghai, China, East China Normal University, Shanghai, China

Kang Yang, State Key Laboratory of Cryptology, Beijing, China

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 customized 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 possible 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.6% (resp., 89.3%).

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: Preprint.
Keywords: Post-quantum，Signatures，VOLE-in-the-Head
Contact author(s): jiaolin_jl @ 126 com
History: 2026-05-31: last of 2 revisions; 2026-05-29: received; See all versions
Short URL: https://ia.cr/2026/1099
License: CC BY

BibTeX

@misc{cryptoeprint:2026/1099,
      author = {Lin Jiao and Hongsen Yang and Hongrui Cui and Yituo He and Yonglin Hao and Xiaojie Guo and Qunxiong Zheng and Jiang Zhang and Yu Yu and Kang Yang},
      title = {Lynx: Symmetric Primitive for Shorter and Faster {VOLE}-in-the-Head Signatures},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/1099},
      year = {2026},
      url = {https://eprint.iacr.org/2026/1099}
}