Analysis And Design For Cryptographic Technique Based On Error Correcting Codes

In 1976, Diffie and Hellman firstly proposed the concept "public-key cryptosystem" in a paper entitled "New directions in Cryptography", which plays an important role in the emergence and development of modern cryptography. In 1978, Berlekamp showed that the decoding of the general linear codes is a NPC hard problem. In the same year, according to this fact and the characteristics of Goppa codes, McEliece proposed the first public-key cryptosystem (the McEliece scheme) based on algebraic coding theory, which uncovers the application prospects of error correcting codes in modern cryptography. Considering the development tendency and importance for the combination encrypting with the capability correcting error, this dissertation gives several important applications of error correcting codes in modern cryptography. Detailed contents are listed as follows:1. Researches on public-key cryptosystem based on error correcting codes include:(1) Existing decoding algorithms of algebraic-geometric codes mainly focused on one-point algebraic-geometric code, therefore, Xing gave a decoding algorithm of generalized RS codes. Based on Xing's work, an algorithm of decoding Goppa geometric codes is obtained.in this dissertation. Differed from the traditional decoding algorithm of one-point algebraic-geometric codes, this decoding algorithm is more general. Moreover, the decoding algorithm is easy to understand and implement.(2) By constructing a system of linear equations, computing the inverse of Vandermonde matrices and solving two counting problems, a condition of Xing used to choose specific divisors (using which one can get Goppa geometric codes achieving the Gilbert-Varshamov bound) is improved. Consequently, more Goppa geometric codes achieving the Gilbert-Varshamov bound can be obtained.(3) A public-key cryptosystem based on algebraic geometric codes is proposed. The cryptosystem is a public-key system combined with error correcting capability. Compared with M public-key system and some variants, the performance of the public-key cryptosystem is analyzed. It is shown that the security, information rate, error correcting capability, and probability of correct decipher are improved.2. Researches on private-key cryptosystem based on error correcting codes include: The revised scheme of Rao-Nam's private-key cryptosystem is analyzed and generalized. When the ciphertext is transmitted through interference channels, the revised scheme is generalized and a private-key cryptosystem with error correcting capability is proposed. In addition, the information rate of the revised scheme is improved using the added error vector to carry additional information. It is shown that the generalized scheme is better than the original revised scheme in the security, error correcting capability, information rate, probability of correct decipher, and long keys.3. Researches on digital signature scheme based on error correcting codes include:(1) Aiming at the modified scheme of Xin-mei signature scheme based on error-correcting codes, Deng Yangming presents a new digital signature scheme. In this dissertation, it is shown that there exists a leak in this digital signature scheme:anyone can obtain partial secret key only resorting signatory's public key, therefore, he may successfully forge a signature. Then, as an example of Xin-mei and ECPS2 signature schemes, it points out, for the digital signature schemes whose design of public key is similar to the above proposed scheme, anybody can achieve partial secret key just by employing public key. Long Yonghong had discussed about the security of the two schemes, and proposed a method for forging signature. In this dissertation, we indicate that there are two wrong cognitions in this discussion.(2) Hwang et al. proposed a practical (t,n) threshold proxy signature scheme based on the RSA cryptosystem. However, the scheme has several security weaknesses pointed out by Wang et al. In order to overcome the security issues of the existing threshold proxy signature schemes, we propose an improved (t,n) threshold proxy signature scheme, and demonstrate that our scheme is more secure and effective when compared to Hwang's scheme and others. Moreover, the proposed scheme has an optional capability of fault tolerance to balance the scalability under different situations.4. Researches on secret sharing scheme based on error correcting codes include:Secret sharing on general access structures was studied. A method of constructing generalized-verifiable-dynamic multi-secret sharing was given. The scheme annuls dealer, and thus it can prevent the dealer from cheating. When the secret was being transmitted, the scheme can protect the secret from listener attacking, and the supply of false shares in the process of secret recovery can be prevented. In the scheme, multiple secrets can be shared at the same time in a group of shareholders. In addition, the scheme efficiently resolves the problem of secret renewing. Thus it is efficient and practical.5. Researches on Cartesian authentication codes include:One construction of Cartesian authentication codes from vector space over finite fields is presented and its size parameters are computed. Under the assumption that the chosen of encoding rules and source states obey uniform probability distribution, the probabilities Pl and Ps of a successful impersonation attack and a successful substitution attack of these codes are also computed respectively.