A New Algorithm for Solving the Rank Syndrome Decoding Problem

International audienceIn this paper, we propose an improvement of the attack on the Rank Syndrome Decoding (RSD) problem found in [1], usually the best attack considered for evaluating the security of rank based cryptosystems. For H a full-rank (n − k) × n matrix over Fqm and e ∈ F n q m of small norm r, the RSD problem consists in recovering e from s = He T. In our case, the norm of a vector over Fqm is defined by the dimension of the Fq-subspace generated by its coordinates. This problem is very similar to the Syndrome Decoding problem in the Hamming metric (only the metric and the field of the coefficients are different) and the security of several cryptosystems relies on its hardness, like McEliece-based PKE [2], [3] or IBE [4]. Our attack is in O (n − k) 3 m 3 q w (k+1)m n −m operations in Fq whereas the previous best attacks are in O (n − k) 3 m 3 q (w−1) min (k+1)m n ,k+1 [1], [5]. In particular in the case m ≤ n, our attack permits to obtain an exponential gain in q m(1−R) for R = k/n the rate of the code. We give examples of broken parameters for recently proposed cryptosystems based on LRPC codes or Gabidulin codes. Our attack does not fully break these cryptosystems but implies larger parameters for the same security levels