Cryptography Reference
In-Depth Information
the simulator. We also do not choose the instance of the DLP until the end of the game.
The simulation will be perfect unless a certain bad event happens, and we will analyse the
probability of this event.
Let
S
}
t
log(
r
)
. The simulator begins by uniformly choosing two distinct
σ
1
,σ
2
in
S
and running
A
(
σ
1
,σ
2
). Algorithm
A
assumes that
σ
1
=
={
0
,
1
σ
(
g
) and
σ
2
=
σ
(
h
)forsome
g,h
G
and some encoding function
σ
, but it is not necessary for the simulator to fix
values for
g
and
h
.
It is necessary to ensure that the encodings are consistent with the group operations.
This cannot be done perfectly without choosing
g
and
h
, but the following idea takes care
of “trivial” consistency. The simulator maintains a list of pairs (
σ
i
,F
i
) where
σ
i
∈
∈
S
and
F
i
∈ F
r
[
x
]. The initial values are (
σ
1
,
1) and (
σ
2
,x
). Whenever
A
makes an oracle query
on (
σ
i
,σ
j
) the simulator computes
F
F
j
.If
F
appears as
F
k
in the list of pairs then
the simulator replies with
σ
k
and does not change the list. Otherwise, a
σ
=
F
i
−
S
distinct from
the previously used values is chosen uniformly at random, (
σ,F
) is added to the simulator's
list and
σ
is returned to
A
.
After making at most
m
oracle queries,
A
outputs
b
∈
∈ Z
/r
Z
. The simulator now chooses
a
uniformly at random in
a
.
Let the simulator's list contain precisely
k
polynomials
Z
/r
Z
. Algorithm
A
wins if
b
=
{
F
1
(
x
)
,...,F
k
(
x
)
}
for some
k
≤
m
+
2. Let
E
be the event that
F
i
(
a
)
=
F
j
(
a
) for some pair 1
≤
i<j
≤
k
.The
probability that
A
wins is
Pr(
A
wins
|
E
)Pr(
E
)
+
Pr(
A
wins
|¬
E
)Pr(
¬
E
)
.
(13.3)
For each pair 1
≤
i<j
≤
k
the probability that (
F
i
−
F
j
)(
a
)
=
0is1
/r
by Lemma
13.4.4
.
O
(
m
2
/r
). On the other hand,
if event
E
does not occur then all
A
“knows” about
a
is that it lies in the set
Hence, the probability of event
E
is at most
k
(
k
−
1)
/
2
r
=
X
of possible
m
2
/
2.
values for
a
for which
F
i
(
a
)
=
F
j
(
a
) for all 1
≤
i<j
≤
k
.Let
N
=
#
X
≈
r
−
¬
=
|¬
=
Then Pr(
1
/N
.
Putting it all together, the probability that
A
wins is
O
(
m
2
/r
).
E
)
N/r
and Pr(
A
wins
E
)
Exercise 13.4.6
Prove Theorem
13.4.5
using Maurer's model for generic algorithms. [Hint:
The basic method of proof is exactly the same. The difference is in formulation and analysis
of the success probability.]
Corollary 13.4.7
Let A be a generic algorithm for the DLP. If A succeeds with noticeable
probability
1
/
log(
r
)
c
for some c>
0
then A must make
(
√
r/
log(
r
)
c
)
oracle queries.
13.5 Generalised discrete logarithm problems
A number of generalisations of the discrete logarithm problem have been proposed over
the years. The motivation for such problems varies: sometimes the aim is to enable new
