编码的构造与译码问题及其在密码学中的应用

发布时间：2018-08-09 13:23

【摘要】：本论文主要研究代数编码的构造与译码相关问题,及编码理论在密码学中的应用。对于二元非对称错误信道,非对称即发送1接收0的概率远大于发送0接收1的概率,与经典编码理论(基于对称错误信道模型)相比,非对称错误给研究带来极大困难,然而这样的信道又普遍存在,比如光通讯等。本文基于代数曲线构造了一类二元非对称纠错码,取一些特殊的代数曲线,该构造给出的编码的参数在渐进意义下都要优于已有的结果。 Reed-Solomon码是编码理论中最重要的编码之一,它的编码方式很简单,在工程中被广泛应用,所以它的译码问题吸引了大批数学家与计算机学家的兴趣。Cheng和Murray在2007年对于Reed-Solomon码的深洞进行研究,他们发现了一类深洞,并猜想奇特征有限域时对于扩展Reed-Solomon码(即赋值集合为D=Fq),这构成所有的深洞。之后洪绍方教授与他的博士生对于本原Reed-Solomon码使用Fourier变换以及循环码的知识发现了另一类深洞,但是他们的方法只能适用于这类特殊的Reed-Solomon码。本文通过很简单的方法对于一般的Reed-Solomon码发现了新的一类深洞,推广了洪教授他们的结果,Cheng等人最新的结果证明了在一些情形下只有这两类深洞。本文对于偶特征时,除了以上两类深洞外给出了新的一类深洞。另外,本文还研究扩展Reed-Solomon码的k+2次多项式定义的深洞,证明没有k+2次多项式定义的深洞,支持了Cheng和Murray最初的猜想。迭代译码是常见译码方法之一,迭代译码中最重要的两个概念是停止集及其分布,因为它们刻画了迭代译码的效率。对于一些经典的线性码,目前已知停止集分布的也相当的少。本文研究代数几何码的停止集及其分布。我们给出一般代数曲线构造的代数几何码的停止集两个描述：一是使用Riemann-Roch空间的代数描述,二是使用除子(divisor)的几何描述。这时发现存在一个区间(跟代数曲线的亏格有关),大小在这个区间外的停止集很容易得到,但是大小在这个区间内的停止集很难确定。对于最简单的代数几何码—广义Reed-Solomon码,此时不存在这个区间,所以它的停止集及其分布问题非常简单。其次考虑椭圆曲线码,它的停止集及其分布是非平凡的,并且本文用椭圆曲线的有理点群完全刻画出其停止集。这样,停止集及其分布、停止集距离问题都归结到椭圆曲线有理点群上的子集和问题,于是就证明了对于一般的椭圆曲线码,在随机多项式时间归约下计算它的停子集及其分布已经是NP困难问题。对于更高亏格的代数几何码,我们还没有太多结果,猜想它的停止集及其分布问题仍是NP困难问题。编码的极小距离完全刻画了这个纠错码的检错与纠错能力,所以希望构造出具有较大的极小距离的纠错码。对于有限域Fq上线性码[n, k, d], Singleton界告诉我们极小距离d不会超过n-k+1。当d=n-k+1时,称这个线性码为极大距离可分(MDS)码。著名的MDS猜想是说MDS码的码长n不会超过q+l(q为有限域Fq的大小),除了个别情况可以达到q+2。对于一般的线性码,这个猜想是一个纯组合问题,没有太多方法,极其困难。不少学者开始考虑一些特殊的线性码,特别地,代数几何码。对于椭圆曲线构造的代数几何码,利用椭圆曲线的几何性质,MDS猜想已经被证明。而对于高亏格的代数曲线构造的代数几何码,MDS猜想还没有完全被解决。本文对于椭圆曲线构造的代数几何码,利用Li和Wan的筛法,给出一个简单的组合的证明,并且如果对码的维数k做细微的限制,我们证明MDS码的码长n不会超过(2/3+∈)q,这个结果比MDS猜想要强很多。最后,论文给出编码理论在密码学中的一个简单的应用。基于线性码以及密钥分享的思想,我们对于经典多用户通讯构造了一个信息论意义下无条件安全的消息认证体制。
[Abstract]:This paper mainly studies the construction and decoding of algebraic coding, and the application of coding theory in cryptography.
For two element asymmetric error channels, the probability of asymmetric transmission 1 receiving 0 is far greater than the probability of sending 0 to receive 1. Compared with the classical coding theory (based on symmetric error channel model), asymmetric error brings great difficulty to the study. However, such channels are common, such as optical communication. This paper is based on algebraic curves. A class of two element asymmetric error correcting codes is used to obtain some special algebraic curves. The parameters given by this structure are better than those obtained in the progressive sense.
Reed-Solomon code is one of the most important codes in the coding theory. Its encoding method is very simple and widely used in engineering. So its decoding problem attracts a large number of mathematicians and computer scientists' interest.Cheng and Murray in the deep hole of the Reed-Solomon code in 2007. They found a kind of deep hole, and guess strange. The extended Reed-Solomon code (i.e. the assignment set is D=Fq) when the characteristic finite field is characteristic, which makes all deep holes. Then professor Hong Shaofang and his doctoral student find another kind of deep hole for the original Reed-Solomon code using the knowledge of Fourier transform and cyclic code, but their square method can only be applied to this special Reed-Solomon code. In this paper, a new kind of deep hole is found for the general Reed-Solomon code by a simple method. The results of Professor Hong are popularized. The latest results of Cheng et al. Prove that there are only two kinds of deep holes in some cases. In this paper, a new kind of deep hole is given in addition to the two kinds of deep holes for the even characteristics. The deep holes defined by k+2 polynomials of Reed-Solomon codes prove that there is no deep hole defined by k+2 polynomials, which supports the initial conjecture of Cheng and Murray.
Iterative decoding is one of the common decoding methods. The two most important concepts in iterative decoding are the stop set and its distribution, because they characterize the efficiency of iterative decoding. For some classical linear codes, the known stop set distribution is quite small. This paper studies the stop set and its distribution of Algebraic Geometric Codes. Two description of the stop set of Algebraic Geometric Codes constructed by the number curve: one is to use the algebraic description of the Riemann-Roch space and the two is to use the geometric description of the divison (divisor). Then, it is found that there is an interval (related to the genus of algebraic curves), and the stop set size outside this interval is easily obtained, but the size is within this interval. The stop set is difficult to determine. For the simplest algebraic geometry code, generalized Reed-Solomon code, it does not exist at this time, so its stop set and its distribution problem are very simple. Secondly, the elliptic curve code is considered, its stop set and its distribution are nontrivial, and this paper completely portrays its stop by the rational point group of the elliptic curve. In this way, the stop set and its distribution and the stop set distance are all reduced to the subset and the problem on the rational point group of the elliptic curve. Therefore, it is proved that for the general elliptic curve code, it is NP difficult to calculate its stop subset and its distribution under the random polynomial time reduction. Without much result, it is still difficult for NP to guess its stopping set and its distribution.
The coded minimum distance fully portrays the error correction and error correction ability of the error correcting code, so we want to construct a error correcting code with a larger minimum distance. For the linear code [n, K, d], Singleton on the finite field Fq, we tell us that the minimum distance D does not exceed n-k+1. when d=n-k+1, and that this linear code is a maximum distance separable (MDS) code. The MDS conjecture of the name is that the code length n of the MDS code does not exceed the q+l (q is the size of the finite field Fq). In addition to a few cases, the conjecture can reach the general linear code. This conjecture is a pure combinatorial problem. There are not too many methods and extremely difficult. Many scholars begin to consider some special linear codes, especially, algebraic geometry code. For ellipse MDS conjecture has been proved by the geometric properties of the elliptic curve, and the MDS conjecture is not completely solved for the algebraic geometric code constructed by the algebraic curve of the high genus. In this paper, a simple combination of the Algebraic Geometric Codes constructed by the elliptical curve is given by the Li and Wan sieving methods. As for the slight restriction on the dimension k of the code, we prove that the code length of MDS code n will not exceed (2/3+ *) Q, which is much better than that of the MDS conjecture.
Finally, the paper gives a simple application of the coding theory in cryptography. Based on the idea of linear code and key sharing, we construct a message authentication system for unconditional security in the information theory for the classical multiuser communication.
【学位授予单位】：南开大学
【学位级别】：博士
【学位授予年份】：2014
【分类号】：TN918.1

【相似文献】