Information set decoding

Issue #152 resolved
David Lucas repo owner created an issue

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.

Comments (5)

  1. 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 :-)

  2. 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...

  3. Log in to comment