New Code-Based Cryptosystems via the IKKR Framework

Journal of Information Security and Applications. 2023. Vol. 76. Article 103530.

Terry S. C., Ivanov F., Muhammad R. K., Chik H. T., Ji-Jian C., Timothy T. V.

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 IKKR problem that is is NP-complete and use this assumption of the intracability if the decisional IKKR 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.

Keywords: Reed-Solomon codes, code-based cryptography, post-quantum cryptography, McEliece Framework, Public-key Encryption, Syndrome Decoding Problem

Publication based on the results of: Development of algorithms for post-quantum cryptography based on forward error correcting codes for machine-to-machine networks (2022)