Research On QC-MDPC McEliece Cryptosystem

In recent years,because of the rapid development of quantum computers,the research on cryptographic algorithms against quantum computer attacks has become a hot topic in the field of cryptography,one of which is about the McEliece cryptosystem.The McEliece cryptosystem is the earliest proposed public key cryptosystem based on error correction code.Compared with the RSA cryptosystem,it has fast encryption and decryption speed and can resist quantum computer attacks,but it has the disadvantages of large key length and low information rate.The QC-MDPC-McEliece cryptosystem that emerged in the recent American NIST post-quantum standardization project is a new variant that can greatly reduce the key length,but its security is threatened by the reaction attack that is proposed by Guo,Johansson and Stankovski?GJS?.This thesis mainly studies the McEliece cryptosystem based on QC-MDPC code.It deeply studies,analyzes and improves the GJS's attack,and then designs two QC-MDPC-McEliece variants that can against such attacks.The main work of the thesis is summarized as follows:Firstly,the implementation process of GJS's attack is analyzed and improved in detail.The principle of GJS's attack,the error pattern used in the attack process,and the distance spectrum are analyzed.Through the analysis of the attack principle,the shortcomings of the QC-MDPC-McEliece scheme are found out and the direction that the scheme can be improved for the GJS attack is given.The distance spectrum is formulated and a new representation is proposed which saves storage space and saves the search for multiple operations.The number of error patterns is quantized.It is pointed out that the maximum distance of a pair of 1 bit in the error pattern corresponds to a minimum of 2³⁰² elements in the error pattern set,which is sufficient for random selection,but there are also shortcomings in element repetitions between one set and another.Secondly,a QC-MDPC-McEliece cryptosystem is designed to prevent reaction attacks.The cryptosystem proposed relies on the general linear code decoding problem.In the process of key generation,the generator matrix G is left-multiplied by the matrix S and right-multiplied by the matrix M with the specific structure transformed by the elementary matrix,with the aim to hide the generator matrix.The public key matrix G'obtained after hiding operation still maintains a quasi-cyclic characteristic,so the length of the public key is kept small.The matrix M with a specific structure can make the attacker no right to select the error pattern directly corrected by the decoding algorithm,and does not leak the related information between the distance spectrum and the decoding failure probability,and makes the cryptosystem having higher security than the original QC-MDPC scheme.Thirdly,a McEliece variant based on the QC-MDPC+QC-LDPC code is designed.In order to increase the complexity of the structure of the private key,the parity check matrix of the QC-MDPC code is combined with one of the QC-LDPC code as a private key,and appropriate parameters are selected to construct a new concatenated codeword instead of the QC-MDPC code.The scrambling matrix and permutation matrix are also not used in this system,so increasing the codeword and key complexity makes the special structure of the selected error pattern in the GJS's attack ineffective,without adding additional computational operands.At the same time,the decoding algorithm process is simplified,and the number of operations per iteration is reduced by?n-w??r,which improves the decoding efficiency.Compared with the original QC-MDPC scheme,the new scheme has a slightly larger key length,but has higher security and decoding efficiency.