New code-based cryptosystems via the IKKR framework

Abstract

One main construct for code-based public key cryptosystems is the McEliece framework that hedges upon the hardness of decoding arbitrary linear codes. Based on Goppa codes, the original McEliece cryptosystem however, suffers from having very large public keys. To alleviate this problem, we define a new problem that is NP-complete and use this assumption of the intractability of the decisional problem to construct a IND-CCA2-secure code-based public key encryption scheme. We consider generalized Reed–Solomon codes in our public-key cryptosystem and show that it resists Sidelnikov and Shestakov’s key recovery attack. Our generalized Reed–Solomon code encryption scheme achieves optimal public key size when compared with other PKE or key encapsulation mechanisms with deterministic decryption or decapsulation, as it requires only 88.1 kilobytes to store public key for schemes achieving 128-bit security level and 399.69 kilobytes to store public key for schemes achieving 256-bit security level. A public key size reduction of nearly 92% is obtained as compared to the classic McEliece PKE, and nearly 53% compared to the Reed–Solomon code-based PKE.