Cryptography Reference
In-Depth Information
distinguished point. Once a distinguished group element is found twice then the DLP can
be solved with high probability.
Exercise 14.2.11
Write down pseudocode for this algorithm.
We stress the most significant difference between this method and the method of the
previous section: the previous method had one long walk with a tail and a cycle, whereas the
new method has many short walks. Note that this algorithm does not require self-collisions
in the walk and so there is no
ρ
shape anymore; the word “rho” in the name of the algorithm
is therefore a historical artifact, not an intuition about how the algorithm works.
Note that, since the group is finite, collisions must eventually occur, and so the algorithm
halts. But the algorithm may fail to solve the DLP (with low probability). Hence, this is a
Monte Carlo algorithm.
In the analysis we assume that we are sampling group elements (we sometimes call them
“points”) uniformly and independently at random. It is important to determine the expected
number of steps before landing on a distinguished point.
Lemma 14.2.12
Let θ be the probability that a randomly chosen group element is a
distinguished point. Then:
1.
the probability that one chooses α/θ group elements, none of which are distinguished,
is approximately e
−
α
when
1
/θ is large;
2.
the expected number of group elements to choose before getting a distinguished point is
1
/θ;
3.
if one has already chosen i group elements, none of which are distinguished, then the
expected number of group elements to further choose before getting a distinguished
point is
1
/θ.
θ
)
i
.So
Proof
The probability that
i
chosen group elements are not distinguished is (1
−
the probability of choosing
α/θ
points, none of which are distinguished, is
θ
)
α/θ
(
e
−
θ
)
α/θ
e
−
α
.
(1
−
≤
=
The second statement is the standard formula for the expected value of a geometric
random variable, see Example
A.14.1
.
For the final statement,
5
suppose one has already sampled
i
points without finding a
distinguished point. Since the trials are independent, the probability of choosing a further
j
points which are not distinguished remains (1
θ
)
j
. Hence, the expected number of extra
−
points to be chosen is still 1
/θ
.
We now make the following assumption. We believe this is reasonable when
r
is suf-
ficiently large,
n
S
>
log(
r
), distinguished points are sufficiently common and specified
5
This is the “apparent paradox” mentioned in footnote 7 of [
423
].
