Jean-Sébastien Coron
DCS, University of Luxembourg, Esch-sur-Alzette, Luxembourg

François Gérard
DCS, University of Luxembourg, Esch-sur-Alzette, Luxembourg

Bowen Zhang
Crypto Group, ICTEAM, UCLouvain, Louvain-la-Neuve, Belgium; DCS, University of Luxembourg, Esch-sur-Alzette, Luxembourg

Keywords: Multivariate signature, Unbalanced Oil and Vinegar, Masking

Abstract

In response to the looming quantum threat, NIST has selected four algorithms for standardization (i.e., ML-KEM, ML-DSA, SLH-DSA, and FN-DSA), yet three of the four schemes are based on Euclidean lattices, which raises concerns about the mathematical diversity of post-quantum algorithms. NIST has therefore announced an additional call for post-quantum signatures with a preference for schemes constructed from assumptions other than lattices. Among such candidates, the Unbalanced Oil and Vinegar (UOV) signature over the multivariate quadratic (MQ) problem is attractive for its short signature and security against quantum cryptanalysis. However, the practical implementations of UOV remain vulnerable to power side-channel attacks.In this paper, we address this issue by presenting two improved techniques for masking linear equations system solving at arbitrary order, with a proof of security in the t-probing model. We show that in the masked setting, our inversion-based techniques outperform Gaussian elimination, unlike the unmasked setting where Gaussian elimination is typically more efficient. As an application, we develop a complete C implementation of the fully masked UOV signing using our improved techniques. Compared to masked Gaussian elimination, our techniques achieve at least 2.2 times speedup at high-order. Against Kundu’s latest implementation (CCS 2025), our masked UOV signing is faster by an average factor of 4.0 at higher masking orders.