On the Comparative Study of Recent Information Set Decoding (ISD) Attacks for QC-LDPC Code-Based McEliece Cryptosystem
Sourabh Biswas, Indivar Gupta, Debasish Bera · 2024
Code-based cryptography is one of the main candidates in quantum-resistant cryptographic techniques. LEDAcrypt is a code-based cryptographic scheme submitted in the 2nd round to the National Institute of Standards and Technology (NIST) postquantum cryptography contest. Information set decoding (ISD) attacks, first introduced by Eugene Prange, are well-known non-structural attacks used effectively for code-based cryptography. After several improvements of the basic ISD algorithm, Stern's ISD$(ISD_{Stern})$and two recent improvements by Finiasz and Sendrier's ISD$(ISD_{FS})$and May, Meurer and Thomae's ISD$(ISD_{MMT})$draw significant attention. This paper demonstrates a detailed security analysis of key-recovery attacks using ISD and a comparative study of three ISD algorithms concerning the QC-LDPC-based McEliece cryptosystem variant of LEDAcrypt. Additionally, we have updated the LEDAcrypt parameter table from the original submission, incorporating two new parameters based on the ISD analysis. Simulation results show that the computational cost of$ISD_{MMT}$is lower than the$ISD_{Stern}$and$ISD_{FS}$when applied for LEDAcrypt.