The McEliece-type cryptosystem based on $D$-codes

The $\mathsf{Classic McEliece}$ code–based cryptosystem is one of the contenders for the asymmetric encryption standard selected as part of the NIST PQC competition. This cryptosystem is based on Goppa codes, which constitute a subclass of alternate codes. The main disadvantage of this cryptosystem is very large key size. Attempts to use Reed–Solomon codes, Reed–Muller codes, algebraic-geometric codes, low–density parity–check codes for reducing the key size have not been successful, since structural attacks on the corresponding cryptosystems were found. Therefore the problem of finding other efficiently decodable codes that provide high security of code–based cryptosystems is a relevant problem.
One way to obtain new codes is to use code constructions based on known codes (base codes). We note that the use of such code constructions as the combination of codes, the direct sum of codes, the transition from field extensions to basic fields did not allow to increase the security. Nevertheless, code constructions are promising, since they make it possible to construct new efficiently decodable codes based on known codes. In general, new codes belong to a class that differs from the class of base codes, i.e. have a different structure (algebraic and/or combinatorial), so structural attacks on cryptosystems based on base codes are not directly applicable to cryptosystems based on new codes.
An important example of a code construction is the tensor product codes, as it is widely used in telecommunication for error correction. In this paper, we study a McEliece-type cryptosystem based on $D$–codes, which are one of the generalizations of the tensor product codes. Namely, we consider $D$–codes based on families of Reed–Muller codes. Based on new and earlier results obtained by the authors regarding the properties of $D$-codes, the requirements for $D$-codes (including the tensor product codes) are determined, under which the security of the cryptosystem is guaranteed to structural attacks based on the Schur-Hadamard product as well as to the information set decoding attack. Parameters of $D$-codes based on binary Reed–Muller codes, which correspond to the strong keys of the cryptosystem, are given. We also compare the characteristics of the $\mathsf{Classic McEliece}$ cryptosystem with the corresponding characteristics of the proposed system on $D$–codes, both in the case of using a decoder operating within half the code distance, and in the case of a decoder operating outside these limits. This comparison shows that it is possible using a decoder operating beyond half the code distance to construct a system based on $D$-codes that has either greater security with a comparable key size, or a smaller key size with comparable security.