The variant of post-quantum cryptosystem based on burst-correcting codes and on the complete decoding problem

Информационно-управляющие системы. 2022. No. 3. P. 45–54.

Ovchinnikov A. А.

Introduction: Today the investigations of post-quantum cryptosystems secure against quantum computations is the area of great interest. An important direction here is code-based cryptography utilizing the mathematical problems from error-correcting coding theory. The improvement of existing code-based systems may be achieved both in practical part (reducing the key sizes) and theoretically by using more complicated mathematical code-based tasks. Purpose: The development of public-key code-based cryptosystem using lowdensity parity-check codes with burst correction; the estimation of the parameters of the obtained system. Results: The variant of codebased cryptosystem using random block permutation low-density parity-check codes is proposed. The cryptocomplexity of the system is supposed to be based on the complete decoding problem, which is believed to be a harder mathematical problem than those used in existing systems. With high probability, the analysis of the system by using decoding methods is not possible at all, which both increases the long-term cryptocomplexity of the system and allows to reduce the key size. The evaluation of the underlying code selection is performed, the approaches to the selection of the parameters of the proposed system on the basis of the required level of cryptocomplexity are considered. Practical relevance: The proposed system allows to reduce the public-key size as compared to the classical McEliece system, cryptocomplexity also comparable, with the underlying mathematical problem to be more stable against perspective attacks.

Keywords: Code-based public-key cryptosystems, post-quantum cryptography, low-density parity-check codes, burst error correction