Reducing the Keysize of McEliece Cryptosystem with Improved Patterson’s Algorithm

McEliece cryptosystem has the advantages of security, fast encryption and decryption, but its key size is too large. Increasing the number of errors can enhance the security level without introducing any additional vulnerable structures. In this paper, we reduce the public key size of McEliece Cryptosystem in a way that increases errors. For the McEliece cryptosystem based on Goppa codes, we prove that directly traversing Patterson’s algorithm is faster than the list decoding algorithms. We also improve the Patterson’s algorithm to reduce the time of each traversal greatly, which makes the new given secure parameter sets not only reduce the public key size well, but also make the decoding time acceptable.