International Association
for Cryptologic Research

The Rank Decoding Problem (R-DP) has gained a lot of attention due to the competitive KEM proposals ROLLO and RQC, as well as the more recent signature scheme RYDE, the latter being a second-round candidate in the ongoing NIST post-quantum standardization process. While previous attacks on the R-DP are based on combinatorial methods, the seminal work of [Bardet et al., 2020] has shown the potential of attacks that use algebraic modelings, breaking the proposed parameters of ROLLO and RQC. These algebraic attacks model the R-DP as a large system of equations. For most parameter ranges, this system is underdetermined; hence, the algebraic attack first needs to perform several guessing steps to obtain a reduced instance for which the system of equations is overdetermined. These steps, in essence, guess a supersupport of the unknown error support, making this attack a hybrid approach between combinatorial and algebraic solvers. In this paper, we present a novel type of guessing step based on searching a subsupport of the error support. While supersupport guessing only reduces the length and dimension of the code, subsupport guessing instead reduces the length and the rank weight of the sought-after error vector. This introduces an additional method for instance reduction compatible with supersupport guessing. Both types of guessing step can be performed sequentially in hybrid attacks, and their numbers can be optimized to outperform current hybrid attacks. We provide experimentally supported comparisons of the attack complexities with and without the novel guessing technique. We measure the impact of our new hybrid attack on the RYDE parameters; for the NIST security category 5 parameters, we decrease the hybrid MaxMinors attack complexity from 301 bits to 272 bits, outperforming all other known rank decoders and tightening the margin above the 256 threshold. For the other security levels, we decrease the complexities to be on par with the best performing combinatorial decoders.