1
$\begingroup$

Is there a cryptographic reason for using an irreducible Goppa polynomial $g$ in the McEliece scheme? One doesn't need irreducibility to define a usable code, so I assume there is some structural attack against reducible polynomials? [One caveat is that the presentation I've seen for Patterson decoding uses irreducibility, but one doesn't need to use that algorithm (and it isn't used in e.g. the FPGA implementation here).]

The key generation is already annoying enough without enforcing irreducibility IMHO. The only thing I can think of is that irreducibility definitely ensures that the support $L$ is disjoint from the zeros of $g$ while maintaining uniform distributions on the choice of $g$ and $L$

$\endgroup$

1 Answer 1

2
$\begingroup$

As you note, $g(X)$ cannot have any roots in $L$ and so we must perform at least one polynomial GCD to check this.

For binary Goppa codes, we must also check that $g(X)$ has no repeated roots, else the minimum distance proof may break down. This will require another GCD check.

Irreducibility precludes both of these situations as well as irritating issues with Patterson’s algorithm (I think that Patterson may be asymptotically faster than Sendrier’s Berlekamp-Massey variant, but I am not sure). The complexity of Rabin’s test is not going to be much worse than the tests that we must already do, so for a one-off piece of key generation we might as well do that.

$\endgroup$
1
  • $\begingroup$ I hadn't considered separability (needed for the "boost" in minimum distance) - I could buy that as reason enough (along with the evaluation along $L$). Are there better irreducibility tests than the one to which you linked? ($x^{q^n}-x$ is pretty big or maybe I'm not doing some of the polynomial arithmetic efficiently enough.) The paper I linked to grabs a random element from an appropriate extension and computes the minimal polynomial (hoping for a winner) rather than rejection sampling random polynomials. $\endgroup$ Commented Oct 15, 2021 at 22:16

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.