Secure and Compact: A New Variant of McEliece Cryptosystem

Abstract

This paper introduces a variant of the McEliece cryptosystem and employs the $(C_{1}, C_{1} + C_{2})$ -construction to generate a new code from two arbitrary linear codes. We propose an efficient hard-decision decoding algorithm for linear codes derived from the $(C_{1}, C_{1} + C_{2})$ -construction and integrate them into the McEliece framework. The security of the cryptosystem varies based on the specific codes used in the $(C_{1}, C_{1} + C_{2})$ -construction. Our proposed variant achieves a good level of security with approximately the same key size compared to one of the classic McEliece candidates of the National Institute of Standards and Technology (NIST) standardization process. Specifically, we demonstrate a 25% key size reduction for our proposed parameters compared to one of the 256-bit secured classic McEliece parameters.

Keywords

• McEliece cryptosystem
• linear codes
• information-set decoding (ISD)
• IND-CPA