Cryptography Reference
In-Depth Information
ν
(
i
) change sign at least once as
i
goes from 0 to
n/
2. It follows that there exists some
0
≤
i
≤
n/
2 such that
ν
(
i
)
=
0, in which case #(
Y
∩
B
i
)
=
w/
2.
One can run Algorithm
14
for all
n/
2sets
B
in the splitting system
B
of Lemma
13.6.6
.
This gives a deterministic algorithm with running time
O
(
n
n/
2
w/
2
) group operations. Stinson
proposes different splitting systems giving a deterministic algorithm requiring
O
(
w
3
/
2
n/
2
w/
2
)
group operations. A more efficient randomised algorithm (originally proposed by Copper-
smith) is to randomly choose sets
B
from the
n/
2
possible subsets of
{
0
,...,n
−
1
}
of
size
n/
2. Theorem
13.6.9
determines the expected running time in this case.
Lemma 13.6.7
Fix a set Y
⊂{
0
,...,n
−
1
}
such that
#
Y
=
w. The probability that a
⊆{
−
}
=
∩
=
randomly chosen B
0
,...,n
1
having
#
B
n/
2
satisfies
#(
Y
B
)
w/
2
is
w
w/
2
(
n
n
n/
2
.
−
w
)
p
Y,B
=
(
n
−
w
)
/
2
Exercise 13.6.8
Prove Lemma
13.6.7
.
Theorem 13.6.9
The expected running time for the low
H
amming weight DLP when
running Algorithm
14
on randomly chosen sets B is O
(
√
w
n/
2
w/
2
)
exponentiations. The
storage is O
(
n/
2
w/
2
)
group elements.
Proo
f
We expect to re
peat
the algorithm 1
/p
Y,B
times. One can show, using the fact
2
k
/
√
2
k
≤
k/
2
≤
2
k
√
2
/πk
, that 1
/p
Y,B
≤
c
√
w
for some constant (see Stinson [
531
]).
The result follows.
Exercise 13.6.10
As with all BSGS methods, the bottleneck for this method is the storage
requirement. Show how to modify the algorithm for the case where only
M
group elements
of storage are available.
Exercise 13.6.11
Adapt Coppersmith's algorithm to the DLP for low weight signed expan-
sions (e.g., NAFs, see Section
11.1.1
).
All the algorithms in this section have large storage requirements. An approach due
to van Oorschot and Wiener for solving such problems using less storage is presented in
Section
14.8.1
.
13.7 Low Hamming weight product exponents
Let
G
be an algebraic group (or algebraic group quotient) over
F
p
(
p
small) and let
g
p
.
Hoffstein and Silverman [
262
] proposed computing random powers of
g
efficiently by
taking products of low Hamming weight Frobenius expansions.
In particular, for Koblitz elliptic curves (i.e.,
p
g
∈
G
(
F
p
n
) with
n>
1. Let
π
p
be the
p
-power Frobenius on
G
, acting on
G
as
g
→
=
2) they suggested using three sets
and taking
3 to be the set of Frobenius expansions of length
n
and weight
7. The BSGS algorithm in Section
13.5
applies to this problem, but the running time
S
j
for 1
≤
j
≤
