Research On Some Coding Problems In Data Security

In recent years,with the vigorous development of the Internet,the digital and networked world has gradually arrived.The resulting massive data has increased the demand for big data storage and information transmission security,especially software such as social networks,self-media,short videos,and video calls,which require realtime storage,access,transmission,and security protection of large amounts of data.On the one hand,in order to ensure data security,improve the data reliability of the storage system and the efficiency of accessing and updating data,and avoid network congestion,it is of great significance to study the reliability technology of storage systems and access data balance for constructing large-scale storage systems.On the other hand,in order to ensure information security and prevent information leakage,it is of great value to study how to transform it so that it will not be stolen or attacked during the information transmission process.Therefore,this dissertation mainly carries out an investigation starts from the point of view of coding theory in three aspects:computational load balancing and update problems in classic storage systems,error-correcting codes for correcting tandem-duplication errors in DNA storage systems,and(generalized)twisted Reed-Solomon codes that can be applied to McEliece cryptosystems.In particular,the first two points are mainly aimed at the research on the reliability of information during storage,and the latter point is the research on the defense measures required to consider the security of information during transmission.The main research work and contributions of this dissertation are listed as follows.1.For the problems of updating and load balance on data computation,we study the sparse and balanced MDS codes.In order to be effectively applied to practical systems,we consider constructing sparse and balanced MDS codes over small finite fields.There are many studies on the existence of sparse and balanced[n,k]q MDS codes,but the size of q needs to be at least n+[k(k-1)/n].In this dissertation,we improve it toq≥n-1.Firstly,given a finite field Fq which satisfies q≥n,a sufficient condition for the existence of a sparse[n,k]q MDS code over Fq characterized by the zero pattern of the generator matrix is provided.This sufficient condition transforms the algebraic problem of constructing an MDS code into a combinatorial problem(that is,constructing a set system that satisfies the conditions(P1)-(P3),see Section 2.4.1 for the specific definition).Based on this condition,we find the binary matrices corresponding to the required set system by designing several algorithms with complexity running in polynomial time in n and k.And then using these matrices,we construct all sparse and balanced[n,k]q MDS codes provided that n≤2k.Further,by extending the coordinates,the demand for field size can be relaxed to q≥n-1.For the case of n>2k,we give some constructions for q=n=ps and k=pem based on sumsets,when e ≤ s-2 and m ≤p-1,or e=s-1 andm<p/2.2.In the DNA-based storage system,data stored in this medium are subject to errors such as tandem duplication arising from various mutations,which need to be corrected to maintain data integrity.In order to restore the original information,we study the error-correcting codes for errors caused by tandem duplications.Constructing this type of error-correcting codes are equivalent to building a set of constant-weight codes with l1 metric over non-negative integers Z≥0 or Iq={0,1,…,q-1}.However,there are few results on the constant weight code problem under l1 metric,especially for the optimal code over Z≥0,the upper and lower bounds for its optimal code size are relatively rough.Thus we have considered them in this dissertation.More specifically,given a constant weight code,we establish a universal necessary condition(the so called UNC condition)and a distance formula for the collection of supports of all codewords,which reveals a connection between packing set systems and l1 metric codes.Therefore,by using group divisible designs and packings in combinatorial design theory,we give constructions of optimal codes over non-negative integers and I3 with l1 weight w≤4 for all possible distances.In general,we also derive the size of the largest ternary code with constant weight w and distance 2w-2 for sufficiently large length n satisfying n≡1,w,-w+2,-2w+3(mod w(w-1)).3.For the problem of(generalized)twisted RS code,we study the properties of(generalized)twisted RS code Cn,k,v(α;t;h;η)and give some constructions.There are many results for twisted RS codes,but most of them concentrate on one twist,that is l=1,and only a fraction of them are related to their structural properties.In this dissertation,we focus on it,especially when all its evaluation points form the root set of a polynomial,and then prove that the code Cn,k,v(α;t;h;η)is closed under duality if the polynomial coefficients have certain distribution,and the corresponding parity check matrix is given.Using this result,we construct the corresponding self-dual code.Especially when l=1,the resulting self-dual codes are either MDS codes or near MDS codes.And when l=3,the minimum distance of the dual code is between n-k-2 and n-k+1.