Cryptography Reference
In-Depth Information
H
w
. Second, the algorithm is no longer restricted to a fixed value of
w
.Instead,
it allows a range for
w
, and the information extracted from the different sets
H
w
is combined in the end.
In case of an even error detection, the corresponding probabilities
p
w
and
q
w
are given by
even
n
−
t
t
−
1
j
−
1
w
−
j
−
1
j
≤
j
even
n
−
t
even
n
−
t
−
1
=
≤
t
=
≤
t
2
≤
j
j
w
−
j
p
w
j
,
w
j
.
≤
j
even
n
−
t
w
−
j
w
−
j
Consequently,
v
y,w
|{
h
∈
H
w
:
hc
T
=0
=
}|
, and the relative frequency estimates
are given by
1
v
y,w
−
hc
T
(1
mod 2)
h
i
.
h
∈
H
w
Algorithm 2 summarizes the improved algorithm. Note that
v
is defined as
v
=
w
−
b
a
w
v
w
+
w
=
b
a
w
+
B
v
w
+
B
,whereeach
a
i
∈{
0
,
1
}
, i.e. not all partial results
need to be combined in the end.
Algorithm 2.
Overbecks's improved algorithm for binary statistical decoding.
INPUT: Generator matrix
G
for an (
n,k,t
)code
C
,
H
=
w
=
b
H
w
⊆C
⊥
and
c
∈{
0
,
1
}
n
OUTPUT:
m
∈{
0
,
1
}
k
such that wt(
c
−
mG
)
≤
t
Let
1
=(1
,...,
1)
∈{
0
,
1
}
n
for
w
=
b
→
B
do
(
σ
w
)
2
=
p
w
(1
−
p
w
)
v
y,w
(
σ
w
)
2
=
p
w
(1
−
p
w
)
v
y,w
v
w
←
h
∈
H
w
(
hc
T
mod 2)(
h
−
p
w
1
)
/σ
w
∈
R
n
v
w
+
B
←−
h
∈
H
w
(1
−
hc
T
mod 2)(
h
−
p
w
1
)
/σ
w
∈
R
n
end for
for
all binary combinations
v
of the different
v
i
do
Choose
I
=
{
positions of the
k
smallest entries of
v
}
s.t.
G
·
I
is invertible
m
←
c
I
G
−
1
·
I
if
wt(
c
−
mG
)
≤
t
then
Return
m
end if
end for
3.2 Statistical Decoding over
F
q
(for
q>
2)
The first thing to note when considering codes over non-binary fields
F
q
is that
the error positions of the secret vector
e
now take values in
. However,
we are only interested to find
k
error-free positions such that the corresponding
generator matrix
G
·
I
F
q
\{
0
}
is invertible, so we do not have to find those error values.
