Paper 2024/1777
Masking Gaussian Elimination at Arbitrary Order, with Application to Multivariate- and Code-Based PQC
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)
- 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-01: approved
- 2024-10-31: received
- See all versions
- Short URL
- https://ia.cr/2024/1777
- License
-
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} }