Cryptography Reference
In-Depth Information
Algorithm 14
Coppersmith's BSGS algorithm for the low Hamming weight DLP
INPUT:
g,h
G
of order
r
,
n
and
w
OUTPUT:
a
of bit-length
n
and Hamming weight
w
such that
h
∈
g
a
,or
=
⊥
1:
Choose
B
n/
2
2:
Initialise an easily searched structure (such as a binary tree, a heap, or a hash table)
L
3:
for
Y
⊂{
0
,...,n
−
1
}
such that #
B
=
⊆
B
:#
Y
=
w/
2
do
=
j
∈
Y
2
j
and
x
g
b
5:
store (
x,Y
)in
L
ordered according to first coordinate
6:
end for
7:
for
Y
Compute
b
=
4:
⊆
(
I
−
B
):#
Y
=
w/
2
do
=
j
∈
Y
2
j
and
y
hg
−
b
Compute
b
=
8:
if
y
=
x
for some (
x,Y
1
)
∈
L
then
9:
=
j
∈
Y
∪
Y
1
2
j
11:
return
a
12:
end if
13:
end for
14:
return
a
10:
⊥
Exercise 13.6.2
Write down an algorithm, to enumerate all
Y
⊂
B
such that #
Y
=
w/
2,
which requires
O
(
n/
2
w/
2
n
) bit operations.
Lemma 13.6.3
The running time of Algorithm
14
is O
(
n/
2
w/
2
)
group operations and the
algorithm requires O
(
n/
2
w/
2
)
group elements of storage.
Exercise 13.6.4
Prove Lemma
13.6.3
.
Algorithm
14
is not guaranteed to succeed since the set
B
might not exactly correspond
to a splitting of the bit positions of the integer
a
into two sets of Hamming weight
≤
w/
2.
We now give a collection of subsets of
I
that is guaranteed to contain a suitable
B
.
Definition 13.6.5
Fix even integers
n
and
w
.Let
I
={
0
,...,n
−
1
}
.A
splitting system
is a set
B
of subsets of
I
of size
n/
2 such that for every
Y
⊂
I
such that #
Y
=
w
there is a
set
B
∈
B
such that #(
B
∩
Y
)
=
w/
2.
Lemma 13.6.6
For any even integers n and w there exists a splitting system
B
of size n/
2
.
Proof
For 0
≤
i
≤
n
−
1 define
B
i
={
+
≤
≤
−
}
i
j
(mod
n
):0
j
n/
2
1
and let
B
={
B
i
:0
≤
i
≤
n/
2
−
1
}
.
To show
B
is a splitting system, fix any
Y
⊂
I
of size
w
. Define
ν
(
i
)
=
#(
Y
∩
B
i
)
−
#(
Y
∩
(
I
−
B
i
))
∈ Z
for 0
≤
i
≤
n/
2
−
1. One can check that
ν
(
i
) is even, that
ν
(
n/
2)
=
−
ν
(0) and that
ν
(
i
+
1)
−
ν
(
i
)
∈{−
2
,
0
,
2
}
. Hence, either
ν
(0)
=
0, or else the values
