New algorithms for decoding in the rank metric and an attack on the LRPC cryptosystem
This work addresses security vulnerabilities in rank metric code-based cryptography, specifically targeting the LRPC cryptosystem, and is incremental as it builds on existing decoding methods.
The paper tackles the decoding problem for rank metric codes by leveraging additional linear combination information to improve algorithm complexity, and applies this with a folding technique to mount a feasible attack on a suggested parameter of the LRPC cryptosystem.
We consider the decoding problem or the problem of finding low weight codewords for rank metric codes. We show how additional information about the codeword we want to find under the form of certain linear combinations of the entries of the codeword leads to algorithms with a better complexity. This is then used together with a folding technique for attacking a McEliece scheme based on LRPC codes. It leads to a feasible attack on one of the parameters suggested in \cite{GMRZ13}.