Paper 2026/516

Towards Compact UOV-Based MQ Signatures: Rectangular and Lifted Whipping Structures

Minh Hieu Nguyen, Academy of Cryptography Techniques

Abstract

Multivariate quadratic (MQ) signatures offer fast signing and verification with short signatures, but their practicality is often limited by large public keys. Recent schemes, such as MAYO, address this limitation by employing the "whipping" technique. This method utilizes emulsifier matrices—the core component underlying Beullens' MAYO scheme—to expand a mini-UOV map into a larger one while ensuring that signing reduces to solving a linear system that is full-rank with high probability. In this work, we focus on modifying these fundamental emulsifier matrices themselves to achieve better performance and smaller key sizes. First, we propose lifting the emulsifier matrices to an extension field while maintaining the base UOV map over the ground field. By leveraging the whipping technique to keep the variable-to-equation ratio close to one, this structural modification effectively avoids known lifted system attacks. Second, we enhance rectangular emulsifier matrices—originally introduced in prior work—with a structured block design that accelerates signing and verification while preserving the necessary full-rank behavior. This approach allows the underlying UOV instance to utilize fewer equations, yielding significantly smaller public keys and potentially faster operations. By combining both techniques, we design a new variant MAYO$^−_L$ and provide a detailed security analysis against known forgery and key-recovery attacks, and propose parameter sets that improve public key and signature sizes at comparable security levels. Finally, we discuss the applicability of our lifting improvement to SNOVA, demonstrating that this enhancement can be integrated into other UOV-based schemes employing the whipping technique.

Note: Corrected several typographical errors and notation inconsistencies.

@misc{cryptoeprint:2026/516,
      author = {Quang-Duc Nguyen and Minh Hieu Nguyen},
      title = {Towards Compact {UOV}-Based {MQ} Signatures: Rectangular and Lifted Whipping Structures},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/516},
      year = {2026},
      url = {https://eprint.iacr.org/2026/516}
}