Paper 2024/1777

Masking Gaussian Elimination at Arbitrary Order, with Application to Multivariate- and Code-Based PQC

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

Digital signature schemes based on multivariate- and code-based hard problems are promising alternatives for lattice-based signature schemes, due to their smaller signature size. Hence, several candidates in the ongoing additional standardization for quantum secure digital signature (DS) schemes by the National Institute of Standards and Technology (NIST) rely on such alternate hard problems. Gaussian Elimination (GE) is a critical component in the signing procedure of these schemes. In this paper, we provide a masking scheme for GE with back substitution to defend against first- and higher-order attacks. To the best of our knowledge, this work is the first to analyze and propose masking techniques for multivariate- or code-based DS algorithms. We propose a masked algorithm for transforming a system of linear equations into row-echelon form. This is realized by introducing techniques for efficiently making leading (pivot) elements one while avoiding costly conversions between Boolean and multiplicative masking at all orders. We also propose a technique for efficient masked back substitution, which eventually enables a secure unmasking of the public output. We evaluate the overhead of our countermeasure for several post-quantum candidates and their different security levels at first-, second-, and third-order, including UOV, MAYO, SNOVA, QR-UOV, and MQ-Sign. Notably, the operational cost of first-, second-, and third-order masked GE is 2.3$\times$ higher, and the randomness cost is 1.2$\times$ higher in MAYO compared to UOV for security levels III and V. In contrast, these costs are similar in UOV and MAYO for one version of level I. We also show detailed performance results for masked GE implementations for all three security versions of UOV on the Arm Cortex-M4 and compare them with unmasked results. Our first-order implementations targeting UOV parameters have overheads of factor 6.5$\times$, 5.9$\times$, and 5.7$\times$ compared to the unprotected implementation for NIST security level I, III, and V.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Preprint.
Keywords
Post-Quantum CryptographyMaskingGaussian EliminationDigital SignaturesUOV
Contact author(s)
quinten norga @ esat kuleuven be
suparna kundu @ esat kuleuven be
uttamkumarojha1729 @ gmail com
anindya @ cse iitk ac in
angshuman @ cse iitk ac in
ingrid verbauwhede @ esat kuleuven be
History
2024-11-16: revised
2024-10-31: received
See all versions
Short URL
https://ia.cr/2024/1777
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/1777,
      author = {Quinten Norga and Suparna Kundu and Uttam Kumar Ojha and Anindya Ganguly and Angshuman Karmakar and Ingrid Verbauwhede},
      title = {Masking Gaussian Elimination at Arbitrary Order, with Application to Multivariate- and Code-Based {PQC}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1777},
      year = {2024},
      url = {https://eprint.iacr.org/2024/1777}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.