Cryptography Reference
In-Depth Information
3 A Generalized Information Set Decoding Algorithm
Following other works [19,20], J. Stern describes in [27] an algorithm to solve
CSD. We present in Algorithm 1 a generalized version, similar to the one pre-
sented in [14], which acts on the parity check matrix
H
0
ofthecode(instead
of the generator matrix). The partial Gaussian elimination of
H
0
P
consists in
Algorithm 1.
Generalized ISD algorithm
For any fixed values of
n
,
r
and
w
, the following algorithm uses four pa-
rameters: two integers
p>
0and
>
0andtwosets
W
1
⊂S
k
+
(
0
,p
1
)and
W
2
⊂S
k
+
(
0
,p
2
)where
p
1
and
p
2
are positive integers such that
p
1
+
p
2
=
p
.
procedure
main isd
input
:
H
0
∈{
0
,
1
}
r×n
,
s
0
∈{
0
,
1
}
r
repeat
P ←
random
n × n
permutation matrix
(
H
,H
,U
)
←
PartialGaussElim(
H
0
P
)
(isd 0)
// as in (1)
s ← s
0
U
T
e ←
isd loop(
H
,H
,s
)
while
e
= fail l
return
(
P,e
)
procedure
isd loop
input
:
H
∈{
0
,
1
}
×
(
k
+
)
,
H
∈{
0
,
1
}
(
r−
)
×
(
k
+
)
,
s ∈{
0
,
1
}
r
for all
e
1
∈ W
1
(isd 1)
i ← e
1
H
T
,
s
1
← e
1
H
T
write(
e
1
,s
1
,i
)
// stores (
e
1
,s
1
)atindex
i
for all
e
2
∈ W
2
(isd 2)
i ← s
+
e
2
H
T
,
s
2
← s
+
e
2
H
T
Elts
←
read(
i
) // extracts the elements stored at index
i
for all
(
e
1
,s
1
)
∈
Elts
(isd 3)
if
wt (
s
1
+
s
2
)=
w − p
return
e
1
+
e
2
(success)
return
fail l
(fail) l)
finding
U
and
H
(and
H
,
H
) such that
2
r −
k
+
1
.
.
.
s
T
H
(1)
,s
T
=
Us
0
=
UH
0
P
=
H
=
1
s
T
H
0
2
If the first
r −
columns are dependent, we change
P
.
