Hervé Talé Kalachi

Freddy Lendé Metouké, Hervé Talé Kalachi, Hermann Tchatchiem Kamche et al.

This paper investigates subcodes of lambda-Gabidulin codes, viewed as rank-metric analogues of generalized Reed--Solomon codes, and their applications to compact-ciphertext cryptosystems. We first analyze subspace and generalized subspace subcodes of lambda-Gabidulin codes and relate them to corresponding subcodes of classical Gabidulin codes through coordinate-wise scaling. This relation yields cardinality bounds and structural properties for these families. When the extension degree equals the code length, we further characterize Gabidulin subspace subcodes in terms of linearized polynomials, which gives an explicit description of their encoding and dimension. We also study the matrix images of these subcodes over the base field through their stabilizer and annihilator algebras, showing that subspace restrictions may preserve nontrivial algebraic invariants despite the loss of extension-field linearity. Motivated by these results, we propose a generator-matrix-based construction of random subcodes designed to avoid such invariants. This construction is then used to design McEliece-like and Niederreiter-like encryption schemes in the MinRank setting. Among the parameter sets considered in this work, the most compact ciphertexts are obtained from random subcodes of classical Gabidulin codes. At the 128-, 192-, and 256-bit security levels, the resulting $\mathsf{LGS}$-Niederreiter instances achieve the smallest ciphertext sizes among the compared schemes, while maintaining competitive public-key sizes.

Vlad Dragoi, Hervé Talé Kalachi

This letter presents a cryptanalysis of the modified McEliece cryptosystem recently proposed by Moufek, Guenda and Gulliver [24]. The system is based on the juxtaposition of quasi-cyclic LDPC and quasi-cyclic MDPC codes. The idea of our attack is to find an alternative permutation matrix together with an equivalent LDPC code which allow the decoding of any cipher-text with a very high probability. We also apply a recent technique to determine weak keys [4] for this scheme. The results show that the probability of weak keys is high enough that this variant can be ruled out as a possible secure encryption scheme.

Philippe Gaborit, Ayoub Otmani, Hervé Talé Kalachi

Encryption schemes based on the rank metric lead to small public key sizes of order of few thousands bytes which represents a very attractive feature compared to Hamming metric-based encryption schemes where public key sizes are of order of hundreds of thousands bytes even with additional structures like the cyclicity. The main tool for building public key encryption schemes in rank metric is the McEliece encryption setting used with the family of Gabidulin codes. Since the original scheme proposed in 1991 by Gabidulin, Paramonov and Tretjakov, many systems have been proposed based on different masking techniques for Gabidulin codes. Nevertheless, over the years all these systems were attacked essentially by the use of an attack proposed by Overbeck. In 2005 Faure and Loidreau designed a rank-metric encryption scheme which was not in the McEliece setting. The scheme is very efficient, with small public keys of size a few kiloBytes and with security closely related to the linearized polynomial reconstruction problem which corresponds to the decoding problem of Gabidulin codes. The structure of the scheme differs considerably from the classical McEliece setting and until our work, the scheme had never been attacked. We show in this article that this scheme like other schemes based on Gabidulin codes, is also vulnerable to a polynomial-time attack that recovers the private key by applying Overbeck's attack on an appropriate public code. As an example we break concrete proposed $80$ bits security parameters in a few seconds.

Ayoub Otmani, Hervé Talé Kalachi, Sélestin Ndjeya

We prove that any variant of the GPT cryptosystem which uses a right column scrambler over the extension field as advocated by the works of Gabidulin et al. with the goal to resist to Overbeck's structural attack are actually still vulnerable to that attack. We show that by applying the Frobenius operator appropriately on the public key, it is possible to build a Gabidulin code having the same dimension as the original secret Gabidulin code but with a lower length. In particular, the code obtained by this way correct less errors than the secret one but its error correction capabilities are beyond the number of errors added by a sender, and consequently an attacker is able to decrypt any ciphertext with this degraded Gabidulin code. We also considered the case where an isometric transformation is applied in conjunction with a right column scrambler which has its entries in the extension field. We proved that this protection is useless both in terms of performance and security. Consequently, our results show that all the existing techniques aiming to hide the inherent algebraic structure of Gabidulin codes have failed.