RM Code-Based Post Quantum Cryptosystems

Abstract

In this dissertation, Reed-Muller (RM) code-based cryptosystems and two families of p-ary sequences are considered. Three main contributions are given as follows.

First, McEliece cryptosystems based on punctured RM codes are proposed. It is shown that the already known attacks, such as the Minder-Shokrollahis attack, the Chizhov-Borodins attack, and the square code attack, do not work for the proposed RM code-based McEliece cryptosystems. We find an optimal puncturing scheme to prevent the previously known attacks for the proposed RM code-based cryptosystems in a sense that the exact locations of puncturing positions with the minimum number of punctured columns of the generator matrix should be found for attacking. It is important to carry out the minimum number of puncturing since the modification of codes by puncturing can reduce security level. In addition, the square code attack can also be prevented in the proposed RM code-based McEliece cryptosystems by using both the proposed puncturing and random insertion methods.

Second, a new signature scheme based on a punctured Reed-Muller (RM) code with random insertion is proposed. The proposed signature scheme improves the Goppa code-based signature scheme developed by Courtois, Finiasz, and Sendrier (CFS). The CFS signature scheme has certain drawbacks in terms of scaling of the parameters and a lack of existential unforgeability under adaptive chosen message attacks (EUF-CMA) security proof. Further, the proposed modified RM code-based signature scheme can use complete decoding, which can be implemented using a recursive decoding method and thus syndromes for errors larger than the error correctability can be decoded for signing, which improves the probability of successful signing and reduces the signing time. Using the puncturing and insertion methods, the proposed RM code-based signature scheme can avoid some known attacks for RM code-based cryptosystems. The parameters of the proposed signature scheme such as error weight parameter w and the maximum signing trial N, can be adjusted in terms of signing time and security level and it is also proved that the proposed signature scheme achieves EUF-CMA security.