Cryptography Reference
In-Depth Information
where
K
0
2
K
2
K
3
2
ε
(
p,
)
.
T
(
p,
)=
(
p,
)
+
(
p,
)
ε
(
p,
)
+
(6)
P
L
Note that when
ε
(
p,
)
k
+
p
<
1, the “min” in (5) is obtained for rightmost term
and
W
1
and
W
2
have (approximatively) the same size. Else
(
p,
) = 1 (which
happens only when
w
is large) and the optimal choice consists in choosing
W
1
smaller than
W
2
.
P
4.1 Lower Bound
Assuming that
K
0
= 0 (we neglect the cost for the Gaussian elimination step),
the cost estimate becomes
2
K
2
K
3
2
ε
(
p,
)
T
(
p,
)=
(
p,
)
ε
(
p,
)
+
(7)
L
and because the first term is increasing and the second is decreasing with
(for
parameters of cryptologic interest), for all
p
we have
T
(
p,
1
)
/
2
≤
min
T
(
p,
)
≤
T
(
p,
1
)where
1
(
p
), or
1
for short, is the unique integer in [0
,r
[ such that the
two terms in
(
p,
) are equal, that is
1
=log
2
K
3
T
(
p,
1
)
=log
2
K
3
2
√
K
1
K
2
P
(
p,
1
)
ε
(
p,
1
)
2
K
2
L
.
(8)
The lower bound is WF
ISD
(
n,r,w
)
≥
min
p
T
(
p,
1
)
/
2 and the various forms of
T
(
p,
1
) give various interpretations of the complexity
2
√
K
1
K
2
(
p,
1
)=
2
K
1
L
(
p,
1
)
2
K
3
2
1
ε
(
p,
1
)
=
2
K
2
T
=
(
p,
)
ε
(
p,
1
)
=
P
(
p,
1
)
L
P
(
p,
)
ε
(
p,
1
)
This bound is very tight if the Gaussian elimination cost is negligible (which is
often the case in practice, see Table 2). Numbers in Table 2 may seem different
from other estimates [5,14]. This difference comes from the fact that we consider
column operations rather than binary operations. In fact they are very close.
4.2 Some Numbers
For Table 3 we will assume that
K
0
=
nr
,
K
1
=
K
2
=1,and
K
3
=2.The
elementary operation being a “column operation”: a column addition or the
computation of a Hamming weight, possibly accompanied by a memory access.
The cost for (isd 1) and (isd 2) can be reduced to 1 by “reusing additions”,
as explained in [5]. The “column” has size
r
bits (
r −
for (isd 3)), however
we need in practice
bits for computing the index in (isd 1) and (isd 2),and
for (isd 3) we only need on average 2(
w − p
) additional bits [5] for deciding
whetherornotwereachthetargetweight. This sets the “practical column size”
to
+2(
w − p
) instead of
r
. We claim that up to a small constant factor, this
measure will give a realistic account for the cost of a software implementation.
