Modification of Niederreiter cryptosystem compact version

Abstract

This work proposes a modified compact version of the Niederreiter cryptosystem that eliminates vulnerabilities inherent in a previously suggested compact scheme. The security of the modified cryptographic system is reduced to the  problem of decoding linear codes with an additional step of exhaustive search over error vectors in a subspace of dimension k. It is rigorously proven that the proposed modification preserves cryptographic strength equivalent to the classical Niederreiter cryptosystem while providing a substantial reduction in public key length. The paper provides formal descriptions of key generation, encryption, and decryption algorithms, accompanied by a detailed analysis of their computational complexity. Furthermore, we establish that the modified scheme’s resistance to Information Set Decoding (ISD) attacks exceeds that of the classical Niederreiter cryptosystem. This enhanced security is achieved through the introduction of an additional multiplicative factor of 2 k in the attack complexity, significantly raising the security level against stateof-the-art cryptanalytic techniques