On the Comparative Study of Recent Information Set Decoding (ISD) Attacks for QC-LDPC Code-Based McEliece Cryptosystem

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 <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$(ISD_{Stern})$</tex> and two recent improvements by Finiasz and Sendrier's ISD <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$(ISD_{FS})$</tex> and May, Meurer and Thomae's ISD <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$(ISD_{MMT})$</tex> 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 <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$ISD_{MMT}$</tex> is lower than the <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$ISD_{Stern}$</tex> and <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$ISD_{FS}$</tex> when applied for LEDAcrypt.