Research Into Several Issues In Code-based Post-Quantum Public Key Cryptography

Post-Quantum Cryptography is a challenging research topic with an important significance because it will play a central role in ensuring information security in the internet if large quantum computers are built. Based on the significance of the research topic, this thesis mainly investigates several issues in one family of public key cryptosystems that have the potential to resist quantum computers: the code-based post-quantum public key cryptography. We focus on studying the structure of error-correcting code, as well as the methods to construct code-based post-quantum public key encryption scheme, provable security post-quantum public key encryption scheme, and code-based post-quantum signature scheme. The main contributions of the thesis can be enumerated as follows:1. We study repeated-root cyclic codes over Fqd +uFqd +…upa-1Fqd(upa = 0) for length N=psn. To further strengthen the significance of application of repeated-root cyclic code over finite chain ring in the coding theory and cryptology, the structure of cyclic codes and dual codes with length psn, (n prime to p) over the ring Fqd + uFqd+…+upa-1Fqd (upa = 0) are thoroughly studied, when d=1, q=p and p =k, that is, the structure of cyclic codes and dual codes (N=psn) over R=Fp[u]/<uk>. Based on the basic concepts of Fqd +uFqd+…+upa-1Fqd (upa = 0 ), some major properties of Galois ring GR(uk,m) and its extension ring Suk(m,?) are given. Using the definition and properties of torsion code of the ring GR(uk ,m), it is first proved that Torj(c) is an ideal of S = Fpm [?]/<?ps-1>, then it is proved that C=<s0,us1,…, uk-1Sk-1> is the polynomial representation of the corresponding ideals over Suk(m,?) . Finally, an isomorphism?between R[X]/<XN-1> and a direct sum?h?I Suk(mh,?) can be obtained using discrete Fourier transform. The generator polynomial representation of the corresponding ideals over R=Fp[u]/<uk> is calculated via the inverse isomorphism of?, moreover, the structure of dual code is also obtained using discrete Fourier transform. This research is helpful to find the better post-quantum digital signature schemes based on error correcting codes and lattice.2. We show how to construct code-based public key encryption schemes. In terms of F -metric, a new modification of the McEliece and Niederreiter public key cryptosystem based on maximum F-distance codes are proposed. The legal party chooses a random matrix as an extra secret key and adds it to the original public key to produce a new modified public key, which makes this cryptosystem effective makes these cryptosystem are effective for resisting the attack based on getting private keys from known public keys. Moreover, attacks on such a system are also investigated; it is shown that the McEliece and Niederreiter public key cryptosystem based on maximum F-distance codes is secure and feasibile. Moreover, the fast decoding method of maximum F-distance codes is presented in this chapter.3 We show how to construct provable security code-based public-key encryption schemes. By means of reviewing currently known attacks to original Niederreiter public-key encryption schemes and the F-Niederreiter that constructed in chapter 4, we come up with the assumptions that F-Niederreiter and Niederreiter public-key encryption schemes are one-way function. Then, two new F-Niederreiter and one new Niederreiter public-key encryption schemes under the assumption are proposed, and these new public-key encryption schemes can be proven, in the random oracle model, to be security.4. We present how to construct a certificateless digital signature scheme using error correcting codes. To construct a post-quantum digital signature scheme with special proterty, the thesis first deeply study certificateless public key encryption scheme.By adjusting the steps of original certificateless public key encryption scheme (CL-PKE), an efficient certificateless public key encryption scheme against malicious key generation center (KGC) using bilinear maps is put forward. The encryption algotithm only need one power computation and the decryption only need one paring computation. The scheme is more efficient than other exiting scheme. Additionally, the security reach chosen-ciphertext secure in the random oracle model assuming the CDH and p-BDHI problem is difficult. Then, we use certificateless public key cryptography to construct a code-based post-quantum digital signature scheme.