Cryptography Reference
In-Depth Information
and a set
S
=
I
×{
1
,
2
}
. Finally, define
f
:
S
→
S
as
f
(
x,i
)
=
ρ
(
f
i
(
σ
i
(
x
))). Clearly,
f
(
σ
−
2
(
a
2
)
,
2), but
collisions can also arise in other ways (for example, due to collisions in
ρ
). Indeed, since
#
f
2
(
a
2
) can arise from
f
(
σ
−
1
1
the desired collision
f
1
(
a
1
)
=
(
a
1
)
,
1)
=
2
S
=
2
N
one expects there to be roughly 2
N
pairs (
a
1
,a
2
)
∈
S
such that
a
1
=
a
2
but
f
(
a
1
)
f
(
a
2
). In many applications there is only one collision (van Oorschot and Wiener
call it the “golden collision”) that actually leads to a solution of the problem. It is therefore
necessary to analyse the algorithm carefully to determine the expected time until the
problem is solved.
Let
N
P
be the number of clients and let
N
M
be the total number of group elements that
can be stored on the server. Van Oorschot a
nd Wiener g
ive a heuristic argument that the
=
algorithm finds a useful
collision
after 2
.
5
(2
N
)
3
/N
M
/N
P
group operations per client.
This is taking
θ
2
.
25
√
N
M
/
2
N
for the probability of a distinguished point. We refer to
[
423
] for the details.
=
14.8.1 The low Hamming weight DLP
Recall the low Hamming weight DLP: given
g,h,n,w
find
x
of bit-length
n
and Hamming
weight
w
such that
h
=
w
and there is a naive
low storage algorithm running in time
O
(
M
). We stress that the symbol
w
here means the
Hamming weight, rather than its meaning earlier in this chapter.
Section
13.6
g
av
e baby-step-giant-step algorithms for the low Hamming weight DLP
that perform
O
(
√
w
n/
2
g
x
. The number of values for
x
is
M
=
w/
2
)
grou
p operations. Hence, these methods require time and space
roughly proportional to
√
wM
.
To solve the low Hamming weight DLP using parallel collision search one sets
R
=
g
and
S
2
to be sets of integers of binary length
n/
2 and Hamming weight roughly
w/
2.
Define the functions
f
1
(
a
)
S
1
,
g
a
and
f
2
(
a
)
hg
−
2
n/
2
a
so that a collision
f
1
(
a
1
)
=
=
=
f
2
(
a
2
)
solves the problem. Note that there is a unique choice of (
a
1
,a
2
) such that
f
1
(
a
1
)
f
2
(
a
2
),
but when one uses the construction of van Oorschot and Wiener to get a single function
f
then there will be many useless collisions in
f
.Wehave
N
=
w/
2
≈
√
M
and so get an algorithm whose number of group operations is proportional to
N
3
/
2
S
2
≈
n/
2
=
#
S
1
=
#
M
3
/
4
yet requires low storage. This is a significant improvement over the naive low-storage
method, but still slower than baby-step-giant-step.
=
Exercise 14.8.1
Write this algorithm in pseudocode and give a more careful analysis of
the running time.
It remains an open problem to give a low
mem
ory algorithm for the low Hamming
weight DLP with complexity proportional to
√
wM
as with the BSGS methods.
14.9 Pollard rho factoring method
This algorithm was proposed in [
436
] and was the first algorithm invented by Pollard that
exploited pseudorandom walks. As more powerful factoring algorithms exist, we keep the
