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 metadatas

Cited literature [12 references]  Display  Hide  Download

https://hal.inria.fr/hal-01957179
Contributor : Jean-Pierre Tillich <>
Submitted on : Monday, December 17, 2018 - 10:45:41 AM
Last modification on : Tuesday, February 26, 2019 - 5:19:32 PM
Long-term archiving on: Monday, March 18, 2019 - 2:29:06 PM

File

GRS+.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

172

Files downloads

559