Cryptography Reference
In-Depth Information
Table 3.
Parallel CFS quasi-monoidic codes
level
pm
n
k
t
key (bits / KiB)
sigs
δ
sigbits
80
2 15
32580
32400
12
1458000 / 178
2
4
326
80
3 11 177048
176949
9
3085033 / 377
3
2
375
80 13 4
28509
28457
13
421214 /
52
2
4
342
112 2 20 1048332 1048092 12
62885520 / 7677
3
3
636
112 11 6 1771495 1771429 11
36768825 / 4489
3
2
558
112 13 5
371228
371163 13
6867332 /
839
3
3
624
128 2 23 8388324 8388048 12 578775312 / 70652
3
2
684
128 5
8
390495
390375 15
21754145 /
2656
3
4
759
128 13 6 4826731 4826653 13 107164431 / 13082
2
3
514
5
Security Assessment
Decoding attacks.
In estimating
concrete
security (rather than asymptotic be-
havior only), we adopt the following criteria, which were discussed and ana-
lyzed by Finiasz and Sendrier [FS09] and by Peters [Pet11, Observation 6.9] (see
also [BLP11]), whereby directly decoding a code of length
n
,dimension
k
,and
generic error patterns of weight
w
over
F
q
, without using the trapdoor, has a
workfactor
at least WF
q
measured in bit operations. Typically
℘
≈
w/
2and
log
q
k/
2
℘
+
℘
log
q
(
q
−
1):
⎧
⎨
⎫
⎬
k
)
2
(
n
+
k
)+
k/
2
℘
+1+
k/
2
℘
+
k/
2
℘
1
2
(
n
−
−
WF
2
=min
℘,
(2)
2
℘
+1)4
℘
k/
2
℘
k/
2
℘
⎩
⎭
+(
w
−
k
)
2
(
n
+
k
)+
k/
2
℘
+1+
k/
2
℘
+
k/
2
℘
(
q
1)
℘
⎧
⎨
⎫
⎬
(
n
−
−
−
k/
2
℘
k/
2
℘
(
q
2
℘
+1)2
℘
1+
q
WF
q
=min
℘,
−
1)
2
℘
q
−
2
⎩
⎭
+
1
(
w
−
q
−
q
−
1
q
(3)
When it is known beforehand that all errors have equal magnitude and
q>
2,
we simplify Equation 3 accordingly:
k
)
2
(
n
+
k
)+
k/
2
℘
+1+
k/
2
℘
+
k/
2
℘
(
q
1)
⎧
⎨
⎫
⎬
(
n
−
−
−
k/
2
℘
k/
2
℘
(
q
2
℘
+1)2
℘
1+
q
WF
q
=min
℘,
−
1)
q
−
2
⎩
⎭
+
1
(
w
−
q
−
q
−
1
q
(4)
The results of this estimations are provided in Tables 1, 2, and 3 and discussed
in Section 6.
Structural attacks.
Structural attacks against families of codes that yield com-
pact keys McEliece have also been proposed. In [FOPT10a], the idea is to convert
the public code into a multivariate nonlinear system and then trying to solve it
