Abstract The public key cryptosystem (PKC) based on rank error correcting codes (the GPT cryptosystem) was proposed in 1991. Use of rank codes in cryptographic applications is advantageous since it is practically impossible to utilize combinatoric decoding. This enabled using public keys of a smaller size. Several attacks against this system were published, including Gibson's attacks and more recently Overbeck's attacks. A few modifications were proposed withstanding Gibson's attack but at least one of them was broken by the stronger attacks by Overbeck. A tool to prevent Overbeck's attack is presented by Gabidulin, which makes the cryptographer define a proper column scrambler matrix over the extension field without violating the standard mode of GPT cryptosystem. In this paper, we apply this tool to another variant of the GPT cryptosystem. Furthermore we increase the security of the proposed system against all known attacks and reduce the public key size to 4 Kbits instead of 10 Kbits. Copyright © 2010 John Wiley & Sons, Ltd.

The concept of Public-key cryptosystem was innovated by McEliece's cryptosystem. The public key cryptosystem based on rank codes was presented in 1991 by Gabidulin -Paramonov-Trejtakov (GPT). The use of rank codes in cryptographic applications is advantageous since it is practically impossible to utilize combinatoric decoding. This has enabled using public keys of a smaller size. Respective structural attacks against this system were proposed by Gibson and recently by Overbeck. Overbeck's attacks break many versions of the GPT cryptosystem and are turned out to be either polynomial or exponential depending on parameters of the cryptosystem. In this paper, we introduce a new approach, called the Smart approach, which is based on a proper choice of the distortion matrix X. The Smart approach allows for withstanding all known attacks even if the column scrambler matrix P over the base field Fq.

The subspace metric is a subject of intensive researche recently. Nevertheless not much is known about codes in this metric in general. In this paper, one class of subspace metric based codes is defined. This class is a generalization of a Koetter-Kshishang-Silva construction, namely, the lifting construction. Also, a quasi-Singleton bound is derived which is tighter than the Koetter-Kschischang bound for large dimensions of subspaces.

In the theory of codes based on Hamming metric, three classes of codes are well known: cyclic codes, shortened cyclic codes and pseudo-cyclic codes. An important result is that the class of linear shortened cyclic codes coincides with the class of linear pseudo-cyclic codes. No similar results are known in the theory of rank-metric based codes. In this paper, we generalize the notion of q-cyclic codes and introduce two new families of codes, namely, shortened q-cyclic codes and pseudo-q-cyclic codes. It is proved that the class of pseudo-q-cyclic codes coincides with the class of shortened q-cyclic codes if the number of positions to shorten is a multiple of the extension degree. The problem is still open for other shortening.

The public key cryptosystem based on rank error correcting codes (the GPT cryptosystem) was proposed in 1991. Use of rank codes in cryptographic applications is advantageous since it is practically impossible to utilize combinatoric decoding. This enabled using public keys of a smaller size. Several attacks against this system were published, including Gibson's attacks and more recently Overbeck's attacks. A few modifications were proposed withstanding Gibson's attack but at least one of them was broken by the stronger attacks by Overbeck. A tool to prevent Overbeck's attack is presented in. In this paper, we apply this approach to other variants of the GPT cryptosystem.

The search for perfect error-correcting codes has received intense interest since the seminal work by Hamming. Decades ago, Golomb and Welch studied perfect codes for the Lee metric in multidimensional torus constellations. In this work, we focus our attention on a new class of four-dimensional signal spaces which include tori as subcases. Our constellations are modeled by means of Cayley graphs defined over quotient rings of Lipschitz integers. Previously unexplored perfect codes of length one will be provided in a constructive way by solving a typical problem of vertices domination in graph theory. The codewords of such perfect codes are constituted by the elements of a principal (left) ideal of the considered quotient ring. The generalization of these techniques for higher dimensional spaces is also considered in this work by modeling their signal sets through Cayley-Dickson algebras.

In [4] a metric for error correction in network coding is introduced. Also constant-dimension codes were introduced and investigated. Nevertheless little is known on codes in this metric in general. In this paper, several classes of codes are defined and investigated.

In order to propose a new metric over QAM constellations, diagonal Gaussian graphs defined over quotients of the Gaussian integers are introduced in this paper. Distance properties of the constellations are detailed by means of the vertex-to-vertex distribution of this family of graphs. Moreover, perfect codes for this metric are considered. Finally, notable subgraphs of diagonal Gaussian graphs are studied which leads to relate the proposed metric to other well-known graph-based metrics such as the Lee distance.

In this paper we consider a broad family of toroidal networks, denoted as Gaussian networks, which include many previously proposed and used topologies. We will define such networks by means of the Gaussian Integers, the subset of the Complex numbers with integer real and imaginary parts. Nodes in Gaussian networks are labeled by Gaussian integers, which confer these topologies an algebraic structure based on quotient rings of the Gaussian integers. In this sense, Gaussian integers reveal themselves as the appropriate tool for analyzing and exploiting any type of toroidal network. Using this algebraic approach, we can characterize the main distance-related properties of Gaussian networks, providing closed expressions for their diameter and average distance. In addition, we solve some important applications, like unicast and broadcast packet routing or the perfect placement of resources over these networks.

Cayley graphs over quotients of the quaternion integers are going to be used to define a new metric over four dimensional lattices. We will consider perfect 1-error correcting codes according to this metric space. We will show that, in some cases, these lattices can be represented as two-dimensional constellations, which allow us to state a relation between the Lee metric and this new Lipschitz metric.

An algebraic methodology for defining new metrics over two-dimensional signal spaces is presented in this work. We have mainly considered quadrature amplitude modulation (QAM) constellations which have previously been modeled by quotient rings of Gaussian integers. The metric over these constellations, based on the distance concept in circulant graphs, is one of the main contributions of this work. A detailed analysis of some degree-four circulant graphs has allowed us to detail the weight distribution for these signal spaces. A new family of perfect codes over Gaussian integers will be defined and characterized by providing a solution to the perfect t-dominating set problem over the circulant graphs presented. Finally, we will show how this new metric can be extended to other signal sets by considering hexagonal constellations and circulant graphs of degree six.

Through the use of F-metrics, a McEliece type public-key cryptosystem based around generalised Reed Solomon codes is constructed and implemented. Using such metrics increases the complexity of the system making it harder to attack allowing for smaller key-sizes. Attacks on such a system are also investigated

We calculate the rank of low-density parity-check (LDPC) matrices based on Vandermonde matrix like constructions. In the case of prime fields the rank is given exactly. We show that LDPC codes based on RS codes are a special case of the Vandermonde based construction, thus also for these LDPC matrix construction, the rank calculation is valid. However, for extension fields the calculation is more sophisticated because of the nilpotent property of the parity check matrix. Therefore we can give presently only a bound for the rank in case of binary extension fields

A new approach is proposed for constructing regular low-density parity-check (LDPC) codes based on tensor product of matrices. In this paper, first a general construction method of regular LDPC codes exploiting permutation matrices is described. Constructed codes have a quasi-cyclic structure with no short cycles of length 4 in their Tanner graph, hence simple encoding while maintaining good performance is achieved. The paper also demonstrates a generalized design, which covers a large family of LDPC codes and number of other construction methods. The new generalized LDPC codes are defined by a small number of parameters and cover a large set of code lengths and rates. Using these codes, LDPC matrices of any column weight and row weight can be constructed. Performance of these codes under iterative decoding compares well with other well-structured as well as random LDPC codes

In this paper we present perfect codes for two-dimensional constellations derived from generalized Gaussian graphs, a family of graphs built over quotient rings of Gaussian integers. Using the generalized Gaussian graphs distance, we solve the problem of finding t-dominating sets and, then, we build new perfect codes over these graphs. The well-known perfect Lee codes can be viewed as a particular subcase of the perfect Gaussian codes introduced in this work

Maximum rank distance codes are the equivalent in rank-metric of Reed-Solomon codes whose subcodes have been widely studied. In this paper we characterize subspace subcodes of MRD codes and we show that it is possible to construct efficient polynomial-time encoding-decoding procedures for these subcodes. In a second part we show that subfield subcodes of maximum rank distance codes can be represented in some sense by the direct sum of maximum rank distance codes of smaller length and same minimum distance. We then derive an algorithm correcting some error-patterns beyond the error-correcting capability of the codes

The only known construction of error-correcting codes in rank metric was proposed in 1985. These were codes with fast decoding algorithm. We present a new construction of rank codes, which defines new codes and includes known codes. This is a generalization of E.M. Gabidulin, 1985. Though the new codes seem to be very similar to subcodes of known rank codes, we argue that these are different codes. A fast decoding algorithm is described

The basis for designing error-correcting codes for two dimensional signal sets is considered in this paper. Both, algebraic and graph-theoretical approaches are employed in this research for establishing the fundamentals of these codes. We give a solution to the t-dominating set problem in a subfamily of degree four circulant graphs which directly provides perfect codes over the Gaussian integers. In order to show the applicability of our results, simple examples for designing different coding schemes are also presented

A polyalphabetic (or mixed) block code is a set of codewords of finite length, where every symbol of a codeword belongs to its own alphabet. In contrast to previous publications we consider a general case, where we do not assume any algebraic structure of the alphabets and the codes. Upper and lower bounds on the cardinality of a polyalphabetic code with given Hamming distance are obtained. Some constructions of polyalphabetic codes are suggested based on known codes. Encoding and decoding of the polyalphabetic codes, obtained in this way, can be done using encoding and decoding algorithms for the mother code. Using this constructions, codes are obtained, that reach the upper Singleton type bound.

A new class of unimodular perfect sequences of length p/sup s/, where p is a prime, is proposed. An explicit secondary construction is provided. This construction includes most of the previously known unimodular perfect sequences of length p/sup s/ as special cases. Also the proposed construction is extended to sequences with autocorrelation over /spl Zopf//sup s//sub p//sup k/, V/sub m2//spl times//spl Zopf//sub p//sup m1/, V/sub k/.

We present a new family of so-called reducible rank codes which are a generalization of rank product codes . This family includes maximal rank distance (MRD) codes for lengths n>N in the field F/sub N/. We give methods for encoding and decoding reducible rank codes. A public key cryptosystem based on these codes and on the idea of a column scrambler is proposed. The column scrambler "mixes" columns of a generator (parity-check) matrix of a code. It makes the system more resistant to structural attacks such as Gibson's attacks. Possible attacks on the system are thoroughly studied. The system is found to be secure against known attacks for public keys of about 16 kbits and greater.

The critical design criterion for space-time codes in asymptotically good channels is the minimum rank between codeword pairs. Rank codes are a two-dimensional matrix code construction where by the rank is the metric of merit. We look at the application of rank codes to space-time code design. In particular, we provide construction methods of full-rank codes over different complex signal constellations, for arbitrary numbers of antennas, and codeword periods. We also derive a Singleton-type bound on the rate of a code for the rank metric, and we show that rank codes satisfy this bound with equality.

The Newton radius of a code is the largest weight of a uniquely correctable error. The covering radius is the largest distance between a vector and the code. Two relations between the Newton radius and the covering radius are given.

A new family of metrics is introduced. Each of these is defined by a spanning set F of linear subspaces of a finite vector space. The norm of a vector is defined as the size of a minimal subset of F whose span contains this vector. Some examples and applications are presented. A-class of Varshamov-Gilbert bound based F-metrics is introduced. Connections with combinatorial metrics are discussed.

It is pointed out that the results in the first four parts of the above-titled paper by R.M. Roth (see ibid., vol.37, no.2, p.328-36, Mar. 1991), which are devoted to the theory of the maximum-rank array codes over finite fields, are not new, but were published previously by the commenter. The author replies that he was not aware of the prior work until very recently. He points out some new results that were contained in the parts in question.>

Infinite families of linear binary codes with covering radius R=2 and minimum distance d=3 and d=4 are given. Using the constructed codes with d=3, R=2, families of covering codes with R>2 are obtained. The parameters of many constructed codes with R>