Cryptography Reference
In-Depth Information
Tabl e 2.
Workfactor estimates and lower bounds for generalized ISD. The code pa-
rameters of the first block of numbers corresponds to encryption, the second to the
CFS digital signature scheme and the third to collision search in the (non-regular)
FSB hash function.
log
2
T
(
p,
1
)
2
(
n, r, w
)
log
2
(WF
ISD
) min
p
(2048
,
352
,
32)
81
.
0
80
.
5
(2048
,
781
,
71)
100
.
7
100
.
1
(4096
,
252
,
21)
80
.
4
80
.
0
(4096
,
540
,
45)
128
.
3
127
.
9
(8192
,
416
,
32)
128
.
8
128
.
4
(2
16
,
144
,
11)
70
.
2
70
.
1
(2
16
,
160
,
12)
79
.
4
79
.
3
(2
18
,
162
,
11)
78
.
9
78
.
8
(2
20
,
180
,
11)
87
.
8
87
.
7
(5
·
2
18
,
640
,
160)
91
.
8
90
.
9
(7
·
2
18
,
896
,
224)
126
.
6
125
.
7
(2
21
,
1024
,
256)
144
.
0
143
.
1
(23
·
2
16
,
1472
,
368)
205
.
9
205
.
0
(31
·
2
16
,
1984
,
496)
275
.
4
274
.
6
4.3 Variations with the Parameter
p
With (8), we have an expression for the optimal, or nearly optimal value
1
(
p
)
of
for a given
n
,
r
,
w
,and
p
. Even though it defines
1
(
p
) implicitly, it gives an
intuition of the significance and variations of
1
. Finding something similar for
p
given
n
,
r
,and
w
(with
=
1
(
p
) of course) seems to be more challenging. How-
ever, we observe that, when
w
is much smaller than the Gilbert-Varshamov dis-
tance (typically for encryption), the value of
T
(
p,
1
(
p
)) varies relatively slowly
with
p
when
p
is close to the optimal.
As an illustration, we give in Table 3 values of
T
(
p,
) (computed with (6))
for various optimal pairs (
p,
) and code parameters.
5D codingOneOutofMany
We assume now that we have to solve CSD(
H
0
,S
0
,w
) for a set of
S
0
of
N
inde-
pendent syndromes which all have a solution. We describe a procedure for that
in Algorithm 4. This algorithm is very similar to Algorithm 1. The differences
are related to the set of syndromes
S
0
. In the block (doom 0) we compute
instead of just
s
=
s
0
U
T
and in the procedure doom loop,
the second loop we run through
W
2
×S
{s
0
U
T
| s
0
∈S
0
}
S
=
instead of
W
2
. It is still optimal to have
W
1
+
W
2
close to
S
k
+
(
0
,p
), but instead of
|W
1
|
=
|W
2
|
in Algorithm 1, it is
better now to choose
|W
1
|
=
|W
2
×S|
=
N|W
2
|
.
