Is McEliece secure with non-binary Goppa codes?

Question

A binary Goppa code with codewords of length $n$ bits that can fix $t$ errors with a polynomial over $GF(2^m)$ can encode $k = n - mt$ bits long data. That is one needs to add $mt$ check bits to fix $t$ bits. This means at most 1/m-th of the codeword can be filled with errors.

On the other hand if you work in a field of $GF(p)$ where $p$ is some prime, to fix $t$ wrong symbols you need to add only $2t$ more symbols (as the polynomial for the generic case needs to have twice degree). So $k = n - 2t$. And in the most extreme case half of the codeword can be error.

If I understood correctly "information set decoding" relies on finding a $k$ symbol long subset of the the transmitted data that doesn't contain errors. So this means it's an advantage to be able to introduce more errors in the message. And it seems the general Goppa codes are better at doing that.

Is there any particular reason we use binary Goppa codes instead of general Goppa codes? Does binary codes defend better from other kinds of attacks?

EDIT: I'm also interested in the case where the code's polynomial is over $GF(2^m)$, but the codeword's elements are not over $GF(2)$ but also over $GF(2^m)$. It's tempting to use a field like $GF(2^{16})$ so the matrix and polynomial elements are represented by "short words" and the transition to bits part is are omitted so we can do all the stuff within a single field, the generator matrix's elements are also short words. And the input is also processed as 2 byte batches: easier and faster vectorized implementation is possible.

EDIT2:

In information set decoding we are looking for a subset in the ciphertext that are not in error. In an $[n, k, t]$ code. We can pick k elements ${n \choose k}$ way and the number of possible correct guesses is ${n-t \choose k}$. So the chance of stumbling upon an error free sequence is ${n-t \choose k}/{n \choose k}$.

Now let's use a generic Goppa code over $GF(1021)$. Let $n = 725$, $t = 145$ and $k = 725 - 2*145 = 435$

So calculate ${725-145 \choose 435}/{725 \choose 435} \approx 6.953 \cdot 10^{-71}$. Which is about $2^{-233}$. So 233 bits of security.

Elements in $GF(1021)$ can be represented in 10 bits giving us a key size of 3153750 bits or about 400kB.

With binary Goppa-codes more check symbols needed. Consider code over the extension field $GF(2^{13})$ with parameters $n = 5600$, $t = 172$, so $k = 3364$ ${5600-172 \choose 3364}/{5600 \choose 3364} \approx 4.373 \cdot 10^{-71}$. For similar security levels. But the matrix is now larger than 2 MB.

Hence my question.

Answer 1

The problem is that you're only referring to plain information set decoding. Indeed, for plain ISD, the complexity of attacking a Goppa code over $\mathbb F_q$ would scale as one would expect with $q$.

However, Stern's algorithm for ISD does not scale purely with the code size.

Following a geometric distribution, we can express the expected cost of an ISD algorithm as

$$ \mathbb E [\text{cost}] = \frac{\text{cost of one iteration}}{\mathbb P [\text{successful iteration}]}\text. $$

For Stern's algorithm, given parameters $p$ with $0 \le p \le w$ (where $w$ is the weight of the error vector) and $l$ with $0 \le l \le n - k$,

1. The probability of a successful iteration does not depend directly on $q$ and can be expressed as a function of $n$, $k$, $w$, $l$ and $p$.
2. The cost for one iteration is $$ (n - k)^2 (n + k) + ((\kappa - p + 1) + 2 N {(q - 1)}^p)l + \frac{q}{q - 1} (w - 2p + 1) 2p (1 + \frac{q - 2}{q - 1}) \frac{N^2 {(q - 1)}^{2p}}{q^l}\text, $$ where $\kappa = k / {2}$ and $N = \binom{k / {2}}{p}$.

As you can see, the way the algorithm scales with $q$ depends a lot on the parameters $p$ and $l$. Therefore, $p$ is usually chosen to be quite small in order to minimize the effect of going through too many subsets (the ${(q - 1)}^p$ and ${(q - 1)}^{2p}$ terms).

Please see Christiane Peters' thesis, which has an entire chapter devoted to this. It also discusses additional improvements and proposes exact values for $p$ and $l$.

Of course, there are also Goppa codes over $\mathbb F_q$ for which such a cryptosystem would be secure. You can find some proposals and analyses in the thesis, too.