Modified Niederreiter type of GPT cryptosystem based on reducible rank codes

GPT public key cryptosystem was proposed by Gabidulin, Paramonov and Tretjakov in 1991. This cryptosystem is based on rank error correcting codes. The main advantage of using rank codes in cryptography is that, it has smaller key size as compared to other code based public key cryptosystems. Several attacks against this system were published and some modifications were also proposed withstanding these attacks. In this paper, we have proposed a modified Niederreiter type GPT cryptosystem based on reducible rank codes by properly choosing the column scrambler matrix to withstand these attacks. Although, the idea of choosing column scrambler matrix from extension field is not new but the approach proposed in this paper, provides more elements of column scrambler matrix from extension field as compared to any previous modifications which makes system more secure against attacks.     

Generalized Gabidulin codes over fields of any characteristic

We generalize Gabidulin codes to a large family of fields, non necessarily finite, possibly with characteristic zero. We consider a general field extension and any automorphism in the Galois group of the extension. This setting enables one to give several definitions of metrics related to the rank-metric, yet potentially different. We provide sufficient conditions on the given automorphism to ensure that the associated rank metrics are indeed all equal and proper, in coherence with the usual definition from linearized polynomials over finite fields. Under these conditions, we generalize the notion of Gabidulin codes. We also present an algorithm for decoding errors and erasures, whose complexity is given in terms of arithmetic operations. Over infinite fields the notion of code alphabet is essential, and more issues appear that in the finite field case. We first focus on codes over integer rings and study their associated decoding problem. But even if the code alphabet is small, we have to deal with the growth of intermediate values. A classical solution to this problem is to perform the computations modulo a prime ideal. For this, we need study the reduction of generalized Gabidulin codes modulo an ideal. We show that the codes obtained by reduction are the classical Gabidulin codes over finite fields. As a consequence, under some conditions, decoding generalized Gabidulin codes over integer rings can be reduced to decoding Gabidulin codes over a finite field.     

Polynomial-time key recovery attack on the Faure–Loidreau scheme based on Gabidulin codes

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 most of 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 for a range of parameters, this scheme 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 in a few seconds parameters with 80-bit security claim. Our work also shows that some parameters are not affected by our attack but at the cost of a lost of efficiency for the underlying schemes.     

Extension of Overbeck’s attack for Gabidulin-based cryptosystems

Cryptosystems based on codes in the rank metric were introduced in 1991 by Gabidulin, Paramanov, and Tretjakov (GPT) and have been studied as a promising alternative to cryptosystems based on codes in the Hamming metric. In particular, it was observed that the combinatorial solution for solving the rank analogy of the syndrome decoding problem appears significantly harder. Early proposals were often made with an underlying Gabidulin code structure. Gibson, in 1995, made a promising attack which was later extended by Overbeck in 2008 to cryptanalyze many of the systems in the literature. Improved systems were then designed to resist the attack of Overbeck and yet continue to use Gabidulin codes. In this paper, we generalize Overbeck’s attack to break the GPT cryptosystem for all possible parameter sets, and then extend the attack to cryptanalyze particular variants which explicitly resist the attack of Overbeck.     

Severely denting the Gabidulin version of the McEliece Public Key Cryptosystem

Gabidulin has proposed a version of the McEliece Public Key Cryptosystem using what he calls maximum rank distance (MRD) codes in place of Goppa codes. It is shown how to break such a system by finding a trapdoor to it. For the size of code he suggests this can be done in about a week on a fast personal computer. The attack can be thwarted by increasing the size of the code, but the advantages claimed for the Gabidulin version over the McEliece version are then largely lost.     

Certificateless signature: a new security model and an improved generic construction

Certificateless cryptography involves a Key Generation Center (KGC) which issues a partial key to a user and the user also independently generates an additional public/secret key pair in such a way that the KGC who knows only the partial key but not the additional secret key is not able to do any cryptographic operation on behalf of the user; and a third party who replaces the public/secret key pair but does not know the partial key cannot do any cryptographic operation as the user either. We call this attack launched by the third party as the key replacement attack. In ACISP 2004, Yum and Lee proposed a generic construction of digital signature schemes under the framework of certificateless cryptography. In this paper, we show that their generic construction is insecure against key replacement attack. In particular, we give some concrete examples to show that the security requirements of some building blocks they specified are insufficient to support some of their security claims. We then propose a modification of their scheme and show its security in a new and simplified security model. We show that our simplified definition and adversarial model not only capture all the distinct features of certificateless signature but are also more versatile when compared with all the comparable ones. We believe that the model itself is of independent interest.A conventional certificateless signature scheme only achieves Girault’s Level 2 security. For achieving Level 3 security, that a conventional signature scheme in Public Key Infrastructure does, we propose an extension to our definition of certificateless signature scheme and introduce an additional security model for this extension. We show that our generic construction satisfies Level 3 security after some appropriate and simple modification. A preliminary version of the extended abstract of partial results appeared in ACISP 2006 [9].     

Linear codes using skew polynomials with automorphisms and derivations

In this work the definition of codes as modules over skew polynomial rings of automorphism type is generalized to skew polynomial rings, whose multiplication is defined using an automorphism and a derivation. This produces a more general class of codes which, in some cases, produce better distance bounds than module skew codes constructed only with an automorphism. Extending the approach of Gabidulin codes, we introduce new notions of evaluation of skew polynomials with derivations and the corresponding evaluation codes. We propose several approaches to generalize Reed-Solomon and BCH codes to module skew codes and for two classes we show that the dual of such a Reed-Solomon type skew code is an evaluation skew code. We generalize a decoding algorithm due to Gabidulin for the rank metric and derive families of Maximum Distance Separable and Maximum Rank Distance codes.     

Cryptanalysis of Two McEliece Cryptosystems Based on Quasi-Cyclic Codes

We cryptanalyse here two variants of the McEliece cryptosystem based on quasi-cyclic codes. Both aim at reducing the key size by restricting the public and secret generator matrices to be in quasi-cyclic form. The first variant considers subcodes of a primitive BCH code. The aforementioned constraint on the public and secret keys implies to choose very structured permutations. We prove that this variant is not secure by producing many linear equations that the entries of the secret permutation matrix have to satisfy by using the fact that the secret code is a subcode of a known BCH code. This attack has been implemented and in all experiments we have performed the solution space of the linear system was of dimension one and revealed the permutation matrix. The other variant uses quasi-cyclic low density parity-check (LDPC) codes. This scheme was devised to be immune against general attacks working for McEliece type cryptosystems based on LDPC codes by choosing in the McEliece scheme more general one-to-one mappings than permutation matrices. We suggest here a structural attack exploiting the quasi-cyclic structure of the code and a certain weakness in the choice of the linear transformations that hide the generator matrix of the code. This cryptanalysis adopts a polynomial-oriented approach and basically consists in searching for two polynomials of low weight such that their product is a public polynomial. Our analysis shows that with high probability a parity-check matrix of a punctured version of the secret code can be recovered with time complexity O(n ³) where n is the length of the considered code. The complete reconstruction of the secret parity-check matrix of the quasi-cyclic LDPC codes requires the search of codewords of low weight which can be done with about 2³⁷ operations for the specific parameters proposed.     

On transform-domain error and erasure correction by Gabidulin codes

Gabidulin codes are the rank metric analogues of Reed–Solomon codes and have found many applications including network coding. In this paper, we propose a transform-domain algorithm correcting both errors and erasures with Gabidulin codes. Interleaving or the direct sum of Gabidulin codes allows both decreasing the redundancy and increasing the error correcting capability for network coding. We generalize the proposed decoding algorithm for interleaved Gabidulin codes. The transform-domain approach allows to simplify derivations and proofs and also simplifies finding the error vector after solving the key equation.     

Distinguisher-based attacks on public-key cryptosystems using Reed–Solomon codes

Because of their interesting algebraic properties, several authors promote the use of generalized Reed–Solomon codes in cryptography. Niederreiter was the first to suggest an instantiation of his cryptosystem with them but Sidelnikov and Shestakov showed that this choice is insecure. Wieschebrink proposed a variant of the McEliece cryptosystem which consists in concatenating a few random columns to a generator matrix of a secretly chosen generalized Reed–Solomon code. More recently, new schemes appeared which are the homomorphic encryption scheme proposed by Bogdanov and Lee, and a variation of the McEliece cryptosystem proposed by Baldi et al. which hides the generalized Reed–Solomon code by means of matrices of very low rank. In this work, we show how to mount key-recovery attacks against these public-key encryption schemes. We use the concept of distinguisher which aims at detecting a behavior different from the one that one would expect from a random code. All the distinguishers we have built are based on the notion of component-wise product of codes. It results in a powerful tool that is able to recover the secret structure of codes when they are derived from generalized Reed–Solomon codes. Lastly, we give an alternative to Sidelnikov and Shestakov attack by building a filtration which enables to completely recover the support and the non-zero scalars defining the secret generalized Reed–Solomon code.     

Some new non-additive maximum rank distance codes

In this paper, a construction of maximum rank distance (MRD) codes as a generalization of generalized Gabidulin codes is given. The family of the resulting codes is not covered properly by additive generalized twisted Gabidulin codes, and does not cover all twisted Gabidulin codes. When the basis field has more than two elements, this family includes also non-affine MRD codes, and such codes exist for all parameters. Therefore, these codes are the first non-additive MRD codes for most of the parameters.     

List and unique error-erasure decoding of interleaved Gabidulin codes with interpolation techniques

A new interpolation-based decoding principle for interleaved Gabidulin codes is presented. The approach consists of two steps: First, a multi-variate linearized polynomial is constructed which interpolates the coefficients of the received word and second, the roots of this polynomial have to be found. Due to the specific structure of the interpolation polynomial, both steps (interpolation and root-finding) can be accomplished by solving a linear system of equations. This decoding principle can be applied as a list decoding algorithm (where the list size is not necessarily bounded polynomially) as well as an efficient probabilistic unique decoding algorithm. For the unique decoder, we show a connection to known unique decoding approaches and give an upper bound on the failure probability. Finally, we generalize our approach to incorporate not only errors, but also row and column erasures.     

Erasure Decoding for Gabidulin Codes

We present a new approach of the decoding algorithm for Gabidulin Codes. In the same way as efficient erasure decoding for Generalized Reed Solomon codes by using the structure of the inverse of the VanderMonde matrices, we show that, the erasure(t erasures mean that t components of a code vector are erased) decoding Gabidulin code can be seen as a computation of three matrice and an affine permutation, instead of computing an inverse from the generator or parity check matrix. This significantly reduces the decoding complexity compared to others algorithms. For t erasures with t ≤ r, where r = n − k, the erasure algorithm decoding for Gab _{n, k} (g) Gabidulin code compute the t symbols by simple multiplication of three matrices. That requires rt + r(k − 1) Galois field multiplications, t(r − 1) + (t + r)k field additions, r ² + r(k + 1) field negations and t(k + 1) field inversions.     

Secret Sharing Schemes with Detection of Cheaters for a General Access Structure

In a secret sharing scheme, some participants can lie about the value of their shares when reconstructing the secret in order to obtain some illicit benefit. We present in this paper two methods to modify any linear secret sharing scheme in order to obtain schemes that are unconditionally secure against that kind of attack. The schemes obtained by the first method are robust, that is, cheaters are detected with high probability even if they know the value of the secret. The second method provides secure schemes, in which cheaters that do not know the secret are detected with high probability. When applied to ideal linear secret sharing schemes, our methods provide robust and secure schemes whose relation between the probability of cheating and the information rate is almost optimal. Besides, those methods make it possible to construct robust and secure schemes for any access structure.     

Cardinal rank metric codes over Galois rings

In 1985, Gabidulin introduced the rank metric in coding theory over finite fields, and used this kind of codes in a McEliece cryptosystem, six years later. In this paper, we consider rank metric codes over Galois rings. We propose a suitable metric for codes over such rings, and show its main properties. With this metric, we define Gabidulin codes over Galois rings, propose an efficient decoding algorithm for them, and hint their cryptographic application.     

Hierarchical erasure correction of linear codes

Linear codes over finite extension fields have widespread applications in theory and practice. In some scenarios, the decoder has a sequential access to the codeword symbols, giving rise to a hierarchical erasure structure. In this paper we develop a mathematical framework for hierarchical erasures over extension fields, provide several bounds and constructions, and discuss potential applications in distributed storage and flash memories. Our results show intimate connection to Universally Decodable Matrices, as well as to Reed-Solomon and Gabidulin codes.     

On the number of inequivalent Gabidulin codes

Maximum rank-distance (MRD) codes are extremal codes in the space of \(m\times n\) matrices over a finite field, equipped with the rank metric. Up to generalizations, the classical examples of such codes were constructed in the 1970s and are today known as Gabidulin codes. Motivated by several recent approaches to construct MRD codes that are inequivalent to Gabidulin codes, we study the equivalence issue for Gabidulin codes themselves. This shows in particular that the family of Gabidulin codes already contains a huge subset of MRD codes that are pairwise inequivalent, provided that \(2\leqslant m\leqslant n-2\).     

Critique of the related-key attack concept

In a related-key attack, an attacker seeks to discover the secret key by requesting encryptions under keys related to the secret key in a manner chosen by the attacker. We describe a new related-key attack against generic ciphers, requiring just O(1) work to distinguish a cipher from random, and O(key length) to completely recover the secret key. This attack applies within a model which was not previously known to be vulnerable, undermining the theoretical foundation of the related-key attack concept. We propose a new definition of related-key security, which prevents all known generic attacks including this new attack. We discuss the theoretical consequences of this new definition.     

On Extensions of Semilocal Prüfer Domains

One of the most important results of Chevalley's extension theorem states that every valuation domain has at least one extension to every extension field of its quotient field. We state a generalization of this result for Prüfer domains with any finite number of maximal ideals. Then we investigate extensions of semilocal Prüfer domains in algebraic field extensions. In particular, we find an upper bound for the cardinality of extensions of a semilocal Prüfer domain. Moreover, we show that any two extensions of a semilocal Prüfer domain are incomparable (by inclusion) in an algebraic extension of fields.