Summary

A robust family of quantum-resistant cryptographic algorithms based on the assumed computational complexity of decoding random linear code. In particular, certain algorithms, such as Classic McEliece (NIST post-quantum competition finalist), BIKE and HQC (both NIST post-quantum competition alternate finalists).

Cryptographic algorithms from this family are relatively efficient but generate large keys. Besides, they are rather conservative security-wise. Since 1978 cryptanalysts have been failing to significantly reduce the number of operations required to compromise code-based cryptographic systems, provided their parameters were chosen correctly.

More on the topic

Coding theory has always been closely linked to cryptography, so it is not surprising that the best-known code-based cryptographic system, the McEliece system, appeared in 1978 as one of the first public-key systems. But it was not as efficient as RSA, and therefore, did not get the same recognition. Recently, however, along with the rise of quantum computing research and the appearance of Shor's algorithm able to efficiently compromise RSA on a quantum computer, the McEliece system's ability to withstand quantum attacks has again come into focus.

The McEliece system and other systems alike (the Niederreiter cryptosystem) can be implemented using different code classes. The results obtained by Russian mathematicians are well known in this field of research – for example, the famous Russian researcher V.M. Sidelnikov demonstrated the vulnerability of the McEliece system to certain code classes. However, it has been proven that applying Goppa codes to the system allows obtaining its more robust and efficient version. When analyzing any attack on the McEliece system, scientists usually consider how applicable it is to Goppa codes. In particular, the McEliece system based on Goppa codes is the best-studied algorithm among its NIST competitors. Therefore, a new attack able to significantly reduce the robustness of the system is unlikely to emerge any time soon.

Coding theory-based cryptographic systems generally use simple binary operations and can be easily implemented at both software and hardware levels. However, they require a lot of space to store the keys, presented as parity-check matrices of high-dimensional linear codes.Creating an efficient signature scheme based on coding theory problems is both an interesting and important challenge.

How to implement code-based cryptography for business data protection?

The QApp team attaches great significance to studying code-based cryptographic algorithms, including the key encapsulation algorithm Classic McEliece — the NIST post-quantum competition finalist.