Paper 2026/132

Subspace Guessing and Rank-Metric Solvers with Hints

Harrison Banda, University of Regensburg

Jan Brinkmann, University of Regensburg

Anna Baumeister, Technical University of Munich

Juliane Krämer, University of Regensburg

Antonia Wachter-Zeh, Technical University of Munich

Abstract

We show how to improve rank-metric solvers when certain side information (hints) about the secret is available. Concretely, we adapt the kernel search algorithm for MinRank and the GRS algorithm for the Rank Syndrome Decoding problem when some entries in the rank decomposition of the error matrix are known. This setting is motivated by side-channel leakage and cryptographic applications: Mirath and RYDE, two signature candidates in the NIST post-quantum competition, rely on these problems and employ secret keys in this decomposed form. As a main technical ingredient, we give an optimal procedure for guessing a subspace containing the row space of a systematic matrix given only partial knowledge of its entries. Further, we describe a profiling side-channel attack on the reference implementation of Mirath to demonstrate the plausibility of obtaining such hints.

Note: Full version with appendices.

@misc{cryptoeprint:2026/132,
      author = {Anmoal Porwal and Harrison Banda and Jan Brinkmann and Anna Baumeister and Juliane Krämer and Antonia Wachter-Zeh},
      title = {Subspace Guessing and Rank-Metric Solvers with Hints},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/132},
      year = {2026},
      url = {https://eprint.iacr.org/2026/132}
}