  We propose two main contributions: first, we revisit the encryption scheme
Rank Quasi-Cyclic (RQC) by introducing new efficient variations, in particular,
a new class of codes, the Augmented Gabidulin codes; second, we propose new
attacks against the Rank Support Learning (RSL), the Non-Homogeneous Rank
Decoding (NHRSD), and the Non-Homogeneous Rank Support Learning (NHRSL)
problems. RSL is primordial for all recent rank-based cryptosystems such as
Durandal (Aragon et al., EUROCRYPT 2019) or LRPC with multiple syndromes
(arXiv:2206.11961), moreover, NHRSD and NHRSL, together with RSL, are at the
core of our new schemes. The new attacks we propose are of both types:
combinatorial and algebraic. For all these attacks, we provide a precise
analysis of their complexity. Overall, when all of these new improvements for
the RQC scheme are put together, and their security evaluated with our
different attacks, they enable one to gain 50% in parameter sizes compared to
the previous RQC version. More precisely, we give very competitive parameters,
around 11 KBytes, for RQC schemes with unstructured public key matrices. This
is currently the only scheme with such short parameters whose security relies
solely on pure random instances without any masking assumptions, contrary to
McEliece-like schemes. At last, when considering the case of Non-Homogeneous
errors, our scheme permits to reach even smaller parameters.
