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 small signature size. Gaussian Elimination (GE) is a critical operation 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. All novel gadgets are proven secure in the
Metadata
- Available format(s)
-
PDF
- Category
- Implementation
- Publication info
- Published elsewhere. Major revision. CT-RSA 2025
- 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
- 2025-01-23: last of 3 revisions
- 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} }