Cryptography Reference
In-Depth Information
take some work to uncompress. Packing each 129-entry column separately into
478 bits would consume 163954 bits. A standard 4-bit encoding ofF
13
would
consume only slightly more space, 21.6kB.
The generalized information-set-decoding attack introduced by Peters in [18]
will break this challenge in roughly 2
53
bit operations. This is obviously feasible.
As another example, our 40kB \wild McEliece" challenge for q = 31 has
m = 2, n = 666, s = 0, t = 2, k = 546, and w = 31. In this case security
relies critically on the defense suggested in [6]: there are only about 2
19
possible
polynomials g, but there are almost 2
850
possible support sets. Information-set
decoding will break this challenge in roughly 2
89
bit operations.
As a nal example, our 20kB \wild McEliece" challenge for q = 3 has m = 6,
n = 729, s = 0, t = 16, k = 537, and w = 24. In this case there is only 1 possible
set fa
1
;:::;a
729
g, namely all ofF
3
6
, but there are approximately 2
148
possible
polynomials g. Information-set decoding will break this challenge in roughly 2
54
bit operations. Does knowing the support help any attack?
We considered a huge number of possible parameters m;n;s;t for each chal-
lenge, and many parameters for the attack in [18], subject to the key-size con-
straint k(nk) log
2
q 8192K, where K is the specied number of kilobytes in
the key. We assigned a security level 2
b
to (m;n;s;t) according to an approxima-
tion to the cost of the attack in [18]. For the \wild McEliece incognito" challenges
we rejected (m;n;s;t) whenever the number of polynomials was below 2
2b
, and
we also rejected (m;n;s;t) whenever the number of support sets was below 2
2b
.
For the \wild McEliece" challenges we did not require these defenses separately:
we allowed the product of the number of polynomials and the number of support
sets to be as small as 2
2b
. Subject to these constraints we selected (m;n;s;t)
for each challenge to maximize b. This procedure matches how we would expect
parameters to be chosen in practice.
5Parameters
In this section we propose parameters (n;k;s;t) for the McEliece cryptosys-
tem using codes =
q
(a
1
;:::;a
n
;fg
q1
) that provide 2
128
security against
information-set decoding and that have more than 2
256
choices of fg
q1
. Our
parameter search uses the analysis of information-set decoding in [18]. We chose
the code length n, the degree s of f, the degree t of g and the dimension
k = n
log
q
n
(s + (q1)t) of to minimize the key size d(nk)k log
2
qe for
128-bit security when w errors are added. Table 5.1 gives an overview. The last
column of the table shows the \wildness percentage" p, i.e., the contribution of
g
q1
to the Goppa polynomial, measured in terms of how its degree relates to
the overall degree.
Figure 5.1 illustrates for q = 13 that, given a particular key size, higher
wildness percentages generally add extra security against information-set de-
coding. The figure compares Goppa codes with no correction factor (100% wild)
to Goppa codes where the degrees of f and g
q1
are balanced (50% wild), and
to Goppa codes without the wild trick (0% wild). We emphasize that adding our
