Cryptography Reference
In-Depth Information
5.3 Number of Operations of One Iteration
The complexity of one iteration of Algorithm 1 is
C
(
p, l
)=
C
Gauss
+
C
hash
+
C
check
where
C
Gauss
is the complexity of a Gaussian elimination,
C
hash
is the complexity
of hashing all the
x
1
's and
C
check
is the complexity of checking all the
x
2
is with
the following expressions:
C
Gauss
=
O
(
N
+
k
)(
N
l
)
=
O
(
N
3
)
−
k
)(
N
−
k
−
(24)
C
hash
=
O
(
K
+
k
+
l
)
/
2
p
(25)
C
check
=
O
1
2
l
)
2
(
K
+
k
+
l
)
/
2
p
2
l
(
N
−
K
−
(26)
The last expression giving
C
check
comes from the fact that the algorithm consid-
ers
(
K
+
k
+
l
)
/
2
p
elements
x
2
, and for each of these candidates, we check about
O
2
l
(
K
+
k
+
l
)
/
2
elements
x
1
's, which involves a matrix multiplication in Step
9. Let us note that
l
will be chosen such that
C
hash
and
C
check
are roughly of
the same order, say 2
l
p
≈
(
K
+
k
+
l
)
/
2
p
.
6
Experimental Results
The attack described in Section 4 was implemented in C and was run on a laptop
MacBook Pro with an Intel Core i7 of 2
.
66 GHz to validate the analysis devel-
oped in Section 5. Table 3 presents the average number of iterations that were
necessary to obtain a codeword of weight in the range [
t
1
···
t
2
]. The average is
computed with 4000 tests most of the time, with the exceptions of the penul-
timate entry (only 1000 tests) and the last entry (only 500 tests). The values
of
t
1
and
t
2
are taken from [KKS97] and [BMJ11]. The algorithm halts when-
ever it finds a word in the prescribed set. Note that for [BMJ11], we have taken
t
1
=
n/
2
2
√
n
and
t
2
=
n/
2+
2
√
n
as advocated by the authors. All the codes
that we considered during our simulations were randomly chosen. This setting
does not completely comply with the recommendations made by the authors for
the schemes given in [KKS97]. In one case, it is suggested to use binary BCH
codes of length
n
= 255 and dimension
k
= 48, and in another case a binary
code of length
n
= 180 and dimension
k
= 48 that was constructed by means
of 12 random binary equidistant codes of length 15, dimension 4 and minimum
distance 8. However, we emphasize that these specific constraints are irrelevant
because the attack is generic and only requires public data (
3
−
)andaims
at forging a valid signature. We can see in Table 3 that the number of iterations
are in accordance with the theoretical upper-bound
UpperBound
on the value of
1
P
succ
F
and
H
obtained in the previous section, which is an upper bound on the average
number of iterations.
