Algebraic Coding:Constructions And Decoding&Its Applications In Cryptography

The thesis studies constructions and decoding related problems of algebraic codes, and applications of coding theory in cryptography.Coding theory is the study of the properties of codes and their fitness for a spe-cific application. Binary asymmetric error-correcting codes play an important role in communication systems modeled by the binary asymmetric channel. In Chapter2, we study binary asymmetric error-correcting codes and give a general construction for bi-nary asymmetric error-correcting codes. The construction makes an improvement on the lower bounds of binary asymmetric error-correcting codes in [1].Reed-Solomon code is one class of the most important codes in coding theory. It is wildly used in engineering, such as a typical CD, wireless communications, DVD, digital TV, etc. It has an easy encoding algorithm, so it attracts lots of mathematicians and computer scientists to study its decoding algorithms. Deep holes play an important role in the decoding of generalized Reed-Solomon codes. It was firstly studied by Cheng and Murray [2] in2007. Till2011, Wu and Hong [3] found a new class of deep holes for standard Reed-Solomon codes. But their method is only available for standard Reed-Solomon codes. In Chapter3, we give a simple method to obtain a new class of deep holes for generalized Reed-Solomon codes. Together with the class of deep holes discovered by Cheng and Murray, it has been recently proved in [4] that they form all the deep holes for a large subclass of Reed-Solomon codes. In particular, for standard Reed-Solomon codes, we get the new class of deep holes given in [3]. Li and Wan [5] studied deep holes of generalized Reed-Solomon codes GRSk(Fq,D) and characterized deep holes defined by polynomials of degree k+1. They showed that this problem is reduced to be a subset sum problem in finite fields. Using the method of Li and Wan, we obtain some new deep holes for special Reed-Solomon codes over finite fields with even characteristic. Furthermore, we study deep holes of the extended Reed-Solomon code, i.e., D=Fq and characterize the deep holes defined by polynomials of degree k+2. We show polynomials of degree k+2can not define deep holes. The iterative decoding algorithm is one of the most important decoding algo-rithms. Stopping sets and stopping set distribution of a linear code play an important role in the performance analysis of iterative decoding for this linear code. Let C be an [n,k] linear code over Fq with parity-check matrix H, where the rows of H may be dependent. Let [n]={1,2,…,n} denote the set of column indices of H. A stopping set S of C with parity-check matrix H is a subset of [n] such that the restriction of H to S does not contain a row of weight1. The stopping set distribution{Ti(H)}i=0n enumerates the number of stopping sets with size i of C with parity-check matrix H. Denote H*the parity-check matrix consisting of all the non-zero codewords in the dual code C(?). In Chapter4, we study stopping sets and stopping set distributions of some residue algebraic geometry (AG) codes with parity-check matrix H*. First, we give two descriptions of stopping sets of residue AG codes. For the simplest AG codes, i.e., the generalized Reed-Solomon codes, it is easy to determine all the stopping sets. Then we consider AG codes from elliptic curves (ECAG codes). We use the group structure of rational points of elliptic curves to present a complete characterization of stopping sets. Then the stopping sets, the stopping set distribution and the stopping distance of the ECAG code are reduced to the search, counting and decision versions of the subset sum problem in the group of rational points of the elliptic curve, respectively. Finally, for some special cases, we determine the stopping set distributions of ECAG code.Computing the minimum distance of a linear code is one of the fundamental prob-lems in coding theory. Vardy [6] showed that it is an NP-hard problem for general linear codes. Later Cheng [7] proved that it is already NP-hard (under RP-reduction) for ECAG codes. In this special case, computing minimum distance problem is also related to the maximum distance separable codes (MDS) conjecture. In Chapter5, we obtain an asymptotic formula for the subset sum problem over a large subset of the group of rational points on an elliptic curve. Using the asymptotic formula, we de-termine the minimum distance of ECAG codes in the situation that the length is large enough, says≥(2/3+∈)q where q is the size of the ground field and∈is a positive con-stant, and give an elementary proof of the MDS conjecture for ECAG codes. Indeed, what is surprising in this case is that for a large range of k, the length of an MDS ECAG codes should not exceed (2/3+∈)q. This is much tighter than that of the original MDS conjecture for ECAG code.Finally, in Chapter6we consider applications of coding theory in cryptography. We construct an authentication scheme for multi-receivers and multiple messages based on a linear code C. This construction can be regarded as a generalization of the authenti-cation scheme given by Safavi-Naini and Wang [8]. Actually, we notice that the scheme of Safavi-Naini and Wang is constructed with Reed-Solomon codes. The generaliza-tion to linear codes has the similar advantages as generalizing Shamir’s secret sharing scheme to linear secret sharing sceme based on linear codes [9-13]. For a fixed mes-sage base field Fq, our scheme allows arbitrarily many receivers to check the integrity of their own messages, while the scheme of Safavi-Naini and Wang has a constraint on the number of verifying receivers V≤q. We introduce access structure in our scheme. Massey [11] characterized the access structure of linear secret sharing scheme by min-imal codewords in the dual code whose first component is1. We slightly modify the definition of minimal codewords in [11]. Let C be a [V,k] linear code. For any coordi-nate i∈{1,2,…, V}, a codeword c in C is called minimal respect to i if the codeword c has component1at the i-th coordinate and there is no other codeword whose i-th com-ponent is1with support strictly contained in that of c. Then the security of receiver Ri in our authentication scheme is characterized by the minimal codewords respect to i in the dual code C. Examples of ECAG codes for linear codes are given in the last section, in this case, we can use the group of rational points on the elliptic curve to de-termine all the malicious groups that can successfully make a substitution to any fixed receiver.