Skip to Main content Skip to Navigation
Conference papers

A New Algorithm for Solving the Rank Syndrome Decoding Problem

Abstract : In 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.
Complete list of metadata

Cited literature [12 references]  Display  Hide  Download
Contributor : Jean-Pierre Tillich Connect in order to contact the contributor
Submitted on : Monday, December 17, 2018 - 10:45:41 AM
Last modification on : Wednesday, October 20, 2021 - 1:31:23 AM
Long-term archiving on: : Monday, March 18, 2019 - 2:29:06 PM


Files produced by the author(s)




Nicolas Aragon, Philippe Gaborit, Adrien Hauteville, Jean-Pierre Tillich. A New Algorithm for Solving the Rank Syndrome Decoding Problem. ISIT 2018 - IEEE International Symposium on Information Theory, Jun 2018, Vail, United States. pp.2421-2425, ⟨10.1109/ISIT.2018.8437464⟩. ⟨hal-01957179⟩



Record views


Files downloads