Paper 2026/990

Single-Trace Power Analysis of LESS Key Generation

Abstract

This paper presents a side-channel attack on the Linear Equivalence Signature Scheme (LESS) v2.0. LESS derives its security from the Linear Equivalence Problem and was evaluated as a candidate during Round 2 of the NIST post-quantum cryptography standardization process. LESS secret keys are used to generate monomial matrices, which are stored efficiently in two one-dimensional lists: the permutation list and the coefficient list. Recovering the secret monomial matrices is sufficient to forge signatures, as they are the values actually used during signing. We propose a profiled, single-trace horizontal attack on LESS key generation that recovers the full secret monomial matrices. First, the monomial coefficients that are multiplied by the dense part of the public generator matrix are recovered via power analysis of the matrix multiplication function. Next, we attack the reduced row echelon form function to recover the permutation list. We then complete the attack algebraically via two independent paths: the Primary attack and the Secondary attack. The Primary attack uses only the recovered coefficients in matrix multiplication together with their permutation positions, and a known parity-check matrix equation. The Secondary attack is an alternative that relies on another algebraic relation between the secret key and the public key and uses all the recovered values. We validated our attack on an ARM Cortex-M4 microcontroller. On the NIST Category 1 parameter set, the Primary attack achieves a 99.1% exact-recovery rate and the Secondary attack achieves a 99% exact-recovery rate, over 6000 independent keys. We also analyze potential countermeasures and show that independently shuffling the row processing order within each column reduces the success rate of our attack to negligible levels, providing protection against the specific attack vector demonstrated in this paper.