4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for the paper. But I'm afraid that link can go broken soon. I would also appreciate if you can add some kind of formula for the security level achievable given the parameters of the code, then I can accept this. $\endgroup$ – Calmarius Jul 1 at 20:41
  • $\begingroup$ I added some additional information to the answer. Sorry for taking so long! $\endgroup$ – d125q Jul 2 at 11:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.