Paper 2024/1875

mUOV: Masking the Unbalanced Oil and Vinegar Digital Signature Scheme at First- and Higher-Order

Suparna Kundu, KU Leuven
Quinten Norga, KU Leuven
Angshuman Karmakar, Indian Institute of Technology Kanpur
Uttam Kumar Ojha, Indian Statistical Institute
Anindya Ganguly, Indian Institute of Technology Kanpur
Ingrid Verbauwhede, KU Leuven
Abstract

In the recent search for additional post-quantum designs, multivariate quadratic equations (MQE) based designs have been receiving attention due to their small signature sizes. Unbalanced Oil and Vinegar (UOV) is an MQE-based digital signature (DS) scheme proposed over two decades ago. Although the mathematical security of UOV has been thoroughly analyzed, several practical side-channel attacks (SCA) have been shown on UOV based DS schemes. In this work, we perform a thorough analysis to identify the variables in UOV based DS schemes that can be exploited with passive SCA, specifically differential power attacks (DPA). Secondly, we introduce masking as a countermeasure to protect the sensitive components of UOV based schemes. We propose efficient masked gadgets for all the critical operations, including the masked dot-product and matrix-vector multiplication. We show that our gadgets are secure in the -probing model through formal proofs, mechanically verified using the maskVerif tool. We implemented and demonstrated the practical feasibility of our arbitrary-order masking algorithms for UOV-Ip and UOV-III. We show that the masked signature generation of UOV-Ip performs up to 62% better than Dilithium2 or ML-DSA and 99% better than Falcon 512 or FN-DSA. In addition, the security of our implementation is practically validated using the test vector leakage assessment (TVLA) methodology.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published elsewhere. Minor revision. ACM SIGSAC Conference on Computer and Communications Security (CCS) 2025
Keywords
Post-Quantum CryptographyDigital SignaturesMaskingUOV
Contact author(s)
suparna kundu @ esat kuleuven be
quinten norga @ esat kuleuven be
angshuman @ cse iitk ac in
uttamkumarojha1729 @ gmail com
anindyag @ cse iitk ac in
ingrid verbauwhede @ esat kuleuven be
History
2025-07-06: revised
2024-11-16: received
See all versions
Short URL
https://ia.cr/2024/1875
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/1875,
      author = {Suparna Kundu and Quinten Norga and Angshuman Karmakar and Uttam Kumar Ojha and Anindya Ganguly and Ingrid Verbauwhede},
      title = {{mUOV}: Masking the Unbalanced Oil and Vinegar Digital Signature Scheme at First- and Higher-Order},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1875},
      year = {2024},
      url = {https://eprint.iacr.org/2024/1875}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.