Join Log in
Score:1
avatar Crypto

Use of irreducible Goppa codes in McEliece scheme

in flag
yoyo

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$

68
0 + 0
Score:2
Daniel S avatar Crypto
ru flag
Daniel S

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.

0 + 0
in flag
yoyo
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.
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.