Cryptography Reference
In-Depth Information
g 2F
2
m
[x] for some integer m. For deg(g) = t the code can correct t errors.
Generalizations of the McEliece cryptosystem (or equivalently the Niederreiter
cryptosystem [16]) using Goppa codes over larger eldsF
q
were investigated but
not found to offer advantages for small q, since it was believed that for a code
built from a polynomial g of degree t one could correct only bt=2c errors.
Peters showed in [18] that, despite this reduced error-correction capacity,
codes overF
31
offer advantages in key size compared to codes overF
2
while
maintaining the same security level against all attacks known. However, codes
over smaller fields such asF
3
were still not competitive in key size with codes
overF
2
.
In [6] we introduced the \wild McEliece" cryptosystem, using Goppa codes
overF
q
built on polynomials of the form g
q1
. These codes have a better error-
correction capacity: they can correct up to bqt=2c errors for deg(g) = t. The extra
factor q=(q1) makes \larger tiny elds" attractive and bridges the gap between
F
2
andF
31
. That paper contains cryptosystem parameters that minimize key
size for different finite fields, subject to the requirement of achieving 128-bit
security against information-set-decoding attacks.
This key-size optimization for 128-bit security reduces the number of irre-
ducible polynomials g below 2
128
for q 11, and below 2
30
for q 31. Enu-
merating all possibilities for g thus becomes more ecient than performing
information-set decoding. The parameters were intentionally chosen this way in
[6]; otherwise the key-size benefit of wild McEliece would disappear as q grows.
In McEliece's original proposal, a large space of possibilities for g is the pri-
mary shield against structural attacks. There are secrets other than g, specifi-
cally a random support permutation P and a random invertible matrix S, but
Sendrier's support-splitting algorithm [21] quickly computes both P and S given
g and the public key. The cost of breaking McEliece's system is thus at most a
small multiple of the number of choices of g: the attacker checks each possibility
for g with the support-splitting algorithm.
This attack fails against [6], because there is another shield in [6]: a secret
support set. In McEliece's original proposal, the support set was all ofF
2
m
;
however, one can define Goppa codes using smaller support sets. We chose pa-
rameters in [6] so that there are more than 2
256
possible support sets. There is
no known attack against the McEliece system with secret support sets, even if
the Goppa polynomial ispublished; in particular, the support-splitting algorithm
uses the support set as input.
However, a secret support set has far less history than a secret choice of g,
and therefore cannot inspire as much confidence. One can reasonably worry that
there is a generalization of support-splitting that handles many support sets
more eciently than separately trying each possible support set. Parameters
relying on secret support sets were marked with biohazard symbols in [6].
In this paper we hide the wild codes in two ways, achieving almost all of the
key-size benefit of wild McEliece without sacrificing the confidence provided by a
large space of polynomials. First, we consider codes built on polynomials fg
q1
;
for deg(f) = s and deg(g) = t these codes can correct up to b(s + qt)=2c errors.
