Cryptography Reference
In-Depth Information
It is natural to ask whether one can do better than the naive BSGS algorithms for these
problems, at least for certain values of
l
. The following result shows that the answer in
general turns out to be “no”.
Lemma 13.5.6
Assume l is even and
#
l. A generic algorithm
for the representation problem with noticeable success probability
1
/
log(#
S
j
=
#
S
1
for all
2
≤
j
≤
S
1
)
c
needs
l/
2
1
/
log(#
S
1
)
c/
2
)
group operations.
(#
S
Proof
Suppose
A
is a generic algorithm for the representation problem. Let
G
be a group
of order
r
and let
g,h
g
m
j
r
1
/l
∈
G
. Set
m
=
,
S
j
={
a
∈ Z
:0
≤
a<m
}
and let
g
j
=
g
a
for some
a
for 0
≤
j
≤
l
−
1. If
h
=
∈ Z
then the base
m
-expansion
a
0
+
a
1
m
+···+
a
l
−
1
m
l
−
1
is such that
l
−
1
g
a
j
.
g
a
h
=
=
j
=
0
Hence, if
A
solves the representation problem then we have solved the DLP using a
generic algorithm. Since we have shown that a generic algorithm for the DLP with
success probability 1
/
log(#
S
1
)
c
needs
(
r/
log(#
S
1
)
c
) group operations, the result is
proved.
13.6 Low Hamming weight DLP
Recall that the
Hamming weight
of an integer is the number of ones in its binary expansion.
Definition 13.6.1
Let
G
be a group and let
g
∈
G
have prime order
r
.The
low Hamming
weight DLP
is: given
h
∈
g
and integers
n,w
to find a integer
a
(if it exists) whose binary
≤
≤
=
g
a
.
expansion has length
n
and Hamming weight
w
such that
h
This definition makes sense even for
n>
log
2
(
r
). For example, squaring is faster than
multiplication in most representations of algebraic groups, so it could be more efficient to
compute
g
a
by taking longer strings with fewer ones in their binary expansion.
Coppersmith developed a time/memory tradeoff algorithm to solve this problem. A
thorough treatment of these ideas was given by Stinson in [
531
]. Without loss of generality,
we assume that
n
and
w
are even (just add 1 to them if not).
The idea of the algorithm is to reduce solving
h
g
a
where
a
has length
n
and Hamming
=
weight
w
to solving
hg
−
a
2
g
a
1
=
where
a
1
and
a
2
have Hamming weight
w/
2. One does
this by choosing a set
B
⊂
I
={
0
,
1
,...,n
−
1
}
of size
n/
2. The set
B
is the set of possible
bit positions for the bits of
a
1
and (
I
B
) is the possible bit positions for the bits of
a
2
.
The detailed algorithm is given in Algorithm
14
. Note that one can compactly represent
subsets
Y
−
⊆
I
as
n
-bit strings.
