Information set decoding
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)
-
-
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 :-)
-
reporter That's the paper I was reading ;)
-
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...
-
reporter - changed status to resolved
Ready for review in #20138
- Log in to comment
This looks like a good paper describing some basic Information Set decoding algorithms: https://eprint.iacr.org/2009/589.pdf