On Code-based Cryptosystems using binary codes with large minimum distance

Abstract

Code-Based Cryptography is a branch of the Post-Quantum Cryptography research area. As such, its focus is on developing algorithms that can be used in the current communication systems to secure them against an adversary powered in the (near) future by a quantum computer. A code-based type cryptosystem is a public key cryptosystem that is resistant or slightly reduces its security level against attacks by the known quantum algorithms. The biggest drawback of this otherwise secure cryptosystem is its large public key. This thesis considers a specific type of linear codes, large minimum distance self-dual codes, and punctured codes derived from them that can provide the same security level as the original McEliece system with approximately a 30% smaller public key. Estimation of the bit security level of a cryptosystem using a small example of such a code for its private key confirms that increasing the minimum weight of the code significantly reduces the public key size of the system. Further, we determine the parameters of putative self-dual codes with a large minimum weight providing classical bit security of 80, 128 and 256 bits (quantum 67, 101, and 183 bits), respectively. For the parameters corresponding to the classical 80 bits security of the McEliece Cryptosystem, a particular example of a binary high minimum distance self-dual code is constructed. It is the first code of its type and length. A punctured code of this example is used for the private key of the McEliece cryptosystem. A new decoding algorithm is introduced, which is suitable for the specific construction of the new self-dual code. Moreover, we present a decryption strategy that decodes the complete code instead of the punctured private key. All this results in a McEliece type cryptosystem with 80 bits security classical (68 bits quantum) and reduced public key size of around 38.5% compared to the original system. Reducing the key size makes the quantum safe McEliece Cryptosystem more attractive for practical use.