We introduce a new family of rank metric codes: Low Rank Parity Check codes (LRPC), for which we propose an efficient probabilistic decoding algorithm. This family of codes can be seen as the equivalent of classical LDPC codes for the rank metric. We then use these codes to design cryptosystems à la McEliece: more precisely we propose two schemes for key encapsulation mechanism (KEM) and public key encryption (PKE). Unlike rank metric codes used in previous encryption algorithms -notably Gabidulin codes - LRPC codes have a very weak algebraic structure. Our cryptosystems can be seen as an equivalent of the NTRU cryptosystem (and also to the more recent MDPC code-based cryptosystem) in a rank metric context, due to the similar form of the public keys. The present paper is an extended version of the article introducing LRPC codes, with important new contributions. We have improved the decoder thanks to a new approach which allows for decoding of errors of higher rank weight, namely up to$\frac {2}{3}(n-k)$when the previous decoding algorithm only decodes up to$\frac {n-k}{2}$errors. Our codes therefore outperform the classical Gabidulin code decoder which deals with weights up to$\frac {n-k}{2}$. This comes at the expense of probabilistic decoding, but the decoding error probability can be made arbitrarily small. The new approach can also be used to decrease the decoding error probability of previous schemes, which is especially useful for cryptography. Finally, we introduce ideal rank codes, which generalize double-circulant rank codes and allow us to avoid known structural attacks based on folding. To conclude, we propose different parameter sizes for our schemes and we obtain a public key of 3337 bits for key exchange and 5893 bits for public key encryption, both for 128 bits of security.

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 metric based cryptosystems. For H a full-rank (n-k)×n matrix over Fqmand e ∈ Fqnm of small norm r, the RSD problem consists in recovering e from s=HeT. In our case, the norm of a vector over Fqmis 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)3m3qw-⌈((k+1)m)/n]⌉-m) operations in Fqwhereas the previous best attacks are in O((n-k)3m3q(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 qm(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.

In this paper, we introduce a new hard problem opening up the construction for new quantum resistant cryptographic schemes. The latter is called Learning Rank with Errors (LRE) and can be seen as an adaptation of the LPN problem to the rank metric setting. In addition, we describe HBLRE, an HB-like authentication protocol that constitutes an application of the aforementioned problem. We also prove that HTLRE is secure against passive attacks and compare its parameters to those of the initial HB scheme.

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 [11].