Cryptography Reference
In-Depth Information
This means that we can restrict the precomputed matrix
H
w
to vectors that
are not cyclic shifts of one another, and in the course of running Algorithm 3,
test
h
∈
H
w
as well as all cyclic shifts of
h
against the vector
c
. As a result, while
the run time of the actual algorithm is unchanged, the size of the precomputed
set
H
w
can be decreased by a factor of up to
n
.
Regular words.
Regular words of length
n
and weight
t
are defined as words
consisting of
t
blocks of length
n/t
, where each block has a weight of 1. They
have been used to increase the eciency of some code-based schemes, e.g. the
FSB hash function [1]; Bernstein et al. showed how to improve information set
decoding using the regular words structure [4].
If it is known that the solution is a regular word, the decoding algorithm can
be modified as follows. When choosing the set
I
, we add the additional condition
that
I
must not contain those indices corresponding to a whole block; in other
words, for all
i
with 1
≤
i
≤
t
,
(
i
−
1)
n
+1
,...,
in
t
I.
t
If the values in
v
are such that a this would happen, the largest value of
v
in
this block is ignored and the index of the next smallest value of
v
is added to
I
instead. This modification slightly increaes the chance of decoding successfully,
or to achieve the same success probability with a slightly smaller size of
H
w
.
4 Experimental Results
In this section, we present experimental results of statistical decoding over
F
q
.
In order to estimate the success probability of Algorithm 3, we need to analyze
the required size of the set
H
w
.
In [6], the authors generalize the weight distribution results from [8] to random
codes over
F
q
. Therefore, we have an upper bound for the size of
H
w
:
n
w
(
q
−
1)
w
q
−
k
.
|
H
w
|≤
, there needs to be a value
δ
such
that the following conditions hold (these conditions were introduced in [13]):
In order to compute the success probability
P
1. For every error position
i
:
v
i
>
(
p
++
w
−
δ
)
v
++
.
y,w
2. There are at least
k
non-error positions
j
such that:
v
j
<
(
p
++
w
−
δ
)
v
++
.
y,w
