Information-Set Decoding (ISD)

Information-Set Decoding is the best known attack against the McEliece Cryptosystem. The Classic McEliece system (see also https://classic.mceliece.org/) uses binary codes, thus codes over the finite field F₂.

Related Publications

• [BLP2008] Daniel J. Bernstein, Tanja Lange, Christiane Peters. Attacking and defending the McEliece cryptosystem. In Post-Quantum Cryptography, Lecture Notes in Computer Science, Vol. 5299, pp. 31–46. Springer-Verlag Berlin Heidelberg, 2008. pdf doi bibtex press release

• [BLP2011] Daniel J. Bernstein, Tanja Lange, Christiane Peters. Smaller decoding exponents: ball-collision decoding. In CRYPTO 2011, Lecture Notes in Computer Science, Vol. 6841, pp. 743–760. Springer-Verlag Berlin Heidelberg, 2011. pdf doi bibtex

Iteration count scripts

We use scripts to estimate the complexity of information-set decoding attacks for binary codes and to determine parameters for the McEliece Cryptosystem.

Complexity estimations in [BLP2008]:

• type1.c and type3.c are written in C using the MPFI library.

• isdf2.gp is to be used with the PARI/GP computer algebra system. The counts are a little less precise.

Bounds as in [BLP2011]:

• blp2011-bound.sage is to be used with the open source mathematics software Sage which is largely Python based.