(2026-01) Masked Solving of Linear Equations System and Application to UOV Signatures
2026-01-12
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 -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 times speedup at high-order. Against Kundu's latest implementation (CCS 2025), our masked UOV signing is faster by an average factor of at higher masking orders.