Cryptography Reference
In-Depth Information
By hypothesis g is the product of its distinct linear factors xr. Therefore
g
q
is the product of the coprime polynomials (xr)
q
, and
P
i
c
i
=(xa
i
) = 0
in k[x]=g
q
; i.e.,
P
i
c
i
=(xa
i
) = 0 inF
q
m
[x]=g
q
. Finally, f is coprime to g
q
, so
P
i
c
i
=(xa
i
) = 0 inF
q
m
[x]=(fg
q
).
t
3AttacksandDefenses
Generic attacks against code-based cryptosystems are those whose hardness de-
pends only on the code parameters q;n;k and the number w of errors. For
q > 2 the most ecient generic attack stated in the literature is the generalized
information-set-decoding attack described in [18]. As far as we know, generic
attacks are the largest threat against the wild McEliece system and the wild
McEliece incognito system, when parameters are chosen sensibly.
The extra factor f described in the previous section allows us to increase the
number of Goppa polynomials so that an attacker cannot enumerate all poly-
nomials f and g of the given degrees in less time than performing information-
set decoding. We actually suggest increasing the number of polynomials to the
square of this, in case there is some square-root attack against the space of poly-
nomials. We also retain the defense used in [6], namely choosing the support as
a secret proper subset ofF
q
m
, again with the number of possibilities being the
square of the cost of information-set decoding.
One might think that the factorizability of fg
q1
is somehow analogous to
the concatenated structure attacked in [20]. However, one cannot even begin
the attack of [20] without finding low-weight words in the dual code. We have
checked in examples of various sizes that the dual code of
q
(a
1
;:::;a
n
;fg
q1
)
does not have words of low weight, so attacks of this type do not apply. Note that
any severe problem with factorizability would also break the original McEliece
system, since every polynomial can be factored over a suitable extension field.
To make structural attacks even harder we suggest using an idea of Berger
and Loidreau [2] which they introduced in an attempt to protect Generalized
Reed-Solomon (GRS) codes, namely to add ` additional rows to the parity-check
matrix. There are
k
`
q
=
(1q
k
)(1q
k
1
)(1q
k
`+1
)
(1q)(1q
2
)(1q
`
)
subspaces of dimension `
in a k-dimensional code overF
q
; this is a very large number even for ` = 1.
Wieschebrink showed in [25] that the structure of GRS can still be detected
despite the extra defense, but the attack relies strongly on properties of GRS
and does not seem to carry over to wild Goppa codes and their close relatives.
We emphasize that these defenses have very low cost, only slightly increasing
the size of the public key compared to pure wild McEliece. The effect of [2] is
that in systematic form the public key has (n k + `)(k `) entries instead
of (nk)k; this is a negligible eect for small `. The small eect of f on the
key size is illustrated with optimized numerical examples in Section 5. There
are even cases (e.g., 2
100
security for q = 31) where the improved granularity of
fg
q1
allowed our computations to ndsmallerkeys for fg
q1
than for g
q1
at
the same security level.
