Cryptography Reference
In-Depth Information
computational problems in
G
if
G
=
G
(unless perhaps
G
is a subgroup of
G
or vice
versa).
∈
Lemma 2.1.19
Let G be a group and let g
G have prime order r. Then the DLP in
g
is random self-reducible.
Proof
First, note that the DLP fits the framework of computational problems in Defini-
tion
2.1.18
. Denote by
X
the set (
g
−{
1
}
)
×
g
.Let(
g,h
)
∈
X
be an instance of the
DLP.
Choose
1
≤
x<r
and
0
≤
y<r
uniformly
at
random
and
consider
the
pair
(
g
x
,h
x
g
xy
)
arises in this way for exactly one pair (
x,y
).
Hence, we have produced a DLP instance uniformly at random.
If
a
is the solution to the new DLP instance, i.e.
h
x
g
xy
∈
X
. Every pair (
g
1
,g
2
)
∈
X
(
g
x
)
a
, then the solution to the
=
original instance is
a
−
y
(mod
r
)
.
This completes the proof.
A useful feature of random self-reducible problems is that if
A
is an algorithm that solves
an instance of the problem in a group
G
with probability (or advantage)
then one can obtain
an algorithm
A
that repeatedly calls
A
and solves any instance in
G
of the problem with
overwhelming probability. This is called
amplifying
the success probability (or advantage).
An algorithm to transform an unreliable oracle into a reliable one is sometimes called a
self-corrector
.
Lemma 2.1.20
Let g have prime order r and let G
. Let Abe an algorithm that solves
the DLP in G with probability at least >
0
. Let
>
0
and define n
=
g
log(1
/
)
/
(where
log
denotes the natural logarithm). Then there is an algorithm A
that solves the
DLP in G with probability at least
1
=
. The running time of A
is O
(
n
log(
r
))
group
operations plus n times the running time of A.
−
Proof
Run
A
on
n
random self-reduced versions of the original DLP. One convenient
feature of the DLP is that one can check whether a solution is correct (this takes
O
(log(
r
))
group operations for each guess for the DLP).
The probability that all
n
trials are incorrect is at most (1
)
n
<
(
e
−
)
log(1
/
)
/
−
=
e
log(
)
. Hence,
A
outputs the correct answer with probability at least 1
.
=
−
2.2 Integer operations
We now begin our survey of efficient computer arithmetic. General references for this topic
are Section 9.1 of Crandall and Pomerance [
150
], Section 3.3 of Shoup [
497
], Section
4.3.1 of Knuth [
308
], Chapter 1 of Brent and Zimmermann [
95
] and von zur Gathen and
Gerhard [
220
].
