Design of New Public Key Encryption Scheme Based on the Polar Coding

Abstract

In this thesis, cryptosystem is proposed where information is transmitted over the insecure channel after encoding plain-text using the public key which is generated using the polar code. That is, the proposed system is a class of the McEliece cryptosystem, the error correcting code based cryptography, whose security is based on the difficulty of decoding of random linear codes. The McEliece cryptography is one of the oldest public key cryptography scheme and McEliece’s original proposal is known to be secure with adequate selections of related parameters even with the intensive efforts of cryptanalyses on that for over 30 years. However, since the secure sizes of public and private keys are too large, it has been considered as less practical suggestion than the other public key cryptographic schemes such as RSA or the elliptic curve cryptography, shortly ECC. Therefore, many researches have been carried to reduce public key size by using other error-correcting codes. Later, Sidelnikov proposed another McEliece cryptosystem which uses the binary Reed Muller (RM) code, also called as Sidelnikov cryptosystem. Although RM code based cryptosystem has smaller size of parameters and more efficient decoding algorithm than McEliece’s original scheme, it was broken using the algebraic structure of the RM code by Minder and Skrollahi. The polar code is a new kind of error correcting code which is information theoretically proved to asymptotically achieve the capacity of the given channels by Arikan and has similar structure to the RM codes. Contrary to the previous error correcting codes, the polar code depends on the given channel and utilizes the channel polarization which can be induced by using channel combining and splitting process. As a result of the channel polarization, some channels turn into good channels and the others into bad channels. While fixed bits are sent through the bad channels, user information is transmitted through good channels. In this thesis, the polar code based public key cryptography is proposed and shown how polar code can be used to encode plaintext message and hide it by adding errors. Decoding method is shown to obtain plaintext from ciphertext using private keys and decoding.