Information set decoding

[David Lucas]

We don't have such a decoder (yet), and I think it could be interesting to have it, so we would have a probabilistic decoding algorithm working for any code class.

As this algorithm is exponential, a straightforward implementation, while quite easy to do, might not be the best solution. Do you have in mind some optimizations that are not too heavy to implement? In that way, we can have a good compromise speed vs. simplicity.

[Johan Rosenkilde]

This looks like a good paper describing some basic Information Set decoding algorithms: https://eprint.iacr.org/2009/589.pdf

[Johan Rosenkilde]

Implementing Lee-Brickell makes sense. Doing the more advanced stuff would, IMHO, be outside the scope of ACTIS, but go ahead if you feel inspired :-)

[David Lucas]

That's the paper I was reading ;)

[Johan Rosenkilde]

I know Christiane Peters, and she was working with Daniel Bernstein and Tanja Lange at the time. They were reinvestigating information set decoding with the aim of actually carrying out attacks on McEliece. I don't know how much they actually progressed the state-of-the-art, but they did make a paper or two about it...

[David Lucas]

Ready for review in #20138